Quicksort - Revision history

Savoundg at 05:56, 14 June 2018

2018-06-14T05:56:49Z

← Older revision		Revision as of 05:56, 14 June 2018
Line 1:		Line 1:
	Quicksort is an exchange sorting algorithm.		Quicksort is an exchange sorting algorithm.

	The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.		The goal is at each iteration to select a pivot (that can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.

	There are two main partition ~~scheme~~:		There are two main partition schemes:
	* Lomuto partition scheme		* Lomuto partition scheme
	* Hoare partition scheme		* Hoare partition scheme
Line 10:		Line 10:
	This partition scheme involves the concepts of pivot and wall.		This partition scheme involves the concepts of pivot and wall.

	For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all ~~his~~ smaller elements on the left and the bigger elements on the right.		For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all the smaller elements on the left and the bigger elements on the right.

	Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All ~~element~~ bigger than the pivot will be swapped with the closest element of the wall from the left, then the wall should be shifted on the left.		Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All elements bigger than the pivot will be swapped with the closest element of the wall from the left, then the wall should be shifted on the left.

	=== Hoare partition scheme ===		=== Hoare partition scheme ===
	Given a pivot number in the array, the partition algorithm looks, from the left of the array, to first element greater or equal than the pivot and, from the right of the array, the first element less or equal than the pivot and switch them. Then, it continues to look for an element greater than the pivot from the left and smaller than the pivot from the right to switch them. The partition stops when the left and right ~~cursor~~ meet. The partition scheme is recursively applied on the left and the right side of the array. The delimitation of the right and left side is determined by the index of the ~~chosen pivot~~.		Given a pivot number in the array, the partition algorithm looks, from the left of the array, to the first element greater or equal than the pivot and, from the right of the array, the first element less or equal than the pivot and switch them. Then, it continues to look for an element greater than the pivot from the left and smaller than the pivot from the right to switch them. The partition stops when the left and right cursors meet. The partition scheme is recursively applied on the left and the right side of the array. The delimitation of the right and left side is determined by where the index where the cursors meet.

	==Resources==		==Resources==

Savoundg at 05:12, 11 June 2018

2018-06-11T05:12:36Z

← Older revision		Revision as of 05:12, 11 June 2018
Line 1:		Line 1:
	Quicksort is an exchange sorting algorithm.		Quicksort is an exchange sorting algorithm.

	~~The Quicksort involves the concepts of pivot and wall.~~

	The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.		The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.
Line 10:		Line 8:

	=== Lomuto partition scheme ===		=== Lomuto partition scheme ===
			This partition scheme involves the concepts of pivot and wall.

	For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.		For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.

	Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All element bigger than the pivot will be swapped with the closest element of the wall from the left, then the wall should be shifted on the left.		Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All element bigger than the pivot will be swapped with the closest element of the wall from the left, then the wall should be shifted on the left.

			=== Hoare partition scheme ===
			Given a pivot number in the array, the partition algorithm looks, from the left of the array, to first element greater or equal than the pivot and, from the right of the array, the first element less or equal than the pivot and switch them. Then, it continues to look for an element greater than the pivot from the left and smaller than the pivot from the right to switch them. The partition stops when the left and right cursor meet. The partition scheme is recursively applied on the left and the right side of the array. The delimitation of the right and left side is determined by the index of the chosen pivot.

	==Resources==		==Resources==

Savoundg at 03:37, 11 June 2018

2018-06-11T03:37:43Z

← Older revision		Revision as of 03:37, 11 June 2018
Line 5:		Line 5:
	The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.		The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.

			There are two main partition scheme:
			* Lomuto partition scheme
			* Hoare partition scheme

			=== Lomuto partition scheme ===
	For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.		For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.

Savoundg at 00:47, 11 June 2018

2018-06-11T00:47:04Z

← Older revision		Revision as of 00:47, 11 June 2018
Line 3:		Line 3:
	The Quicksort involves the concepts of pivot and wall.		The Quicksort involves the concepts of pivot and wall.

	The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.		The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot on the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.

	For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.		For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.

	Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All element bigger than the pivot will be swapped with the closest element of the wall from the left, ~~the~~ the wall should be shifted on the left.		Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All element bigger than the pivot will be swapped with the closest element of the wall from the left, then the wall should be shifted on the left.

	==Resources==		==Resources==

Savoundg at 21:59, 3 June 2018

2018-06-03T21:59:49Z

← Older revision		Revision as of 21:59, 3 June 2018
Line 13:		Line 13:
	!		!
	\|-		\|-
	\|		\|https://www.youtube.com/watch?v=SLauY6PpjW4
			\|-
			\|https://en.wikipedia.org/wiki/Quicksort
	\|}		\|}

Savoundg at 06:07, 1 June 2018

2018-06-01T06:07:22Z

← Older revision		Revision as of 06:07, 1 June 2018
Line 3:		Line 3:
	The Quicksort involves the concepts of pivot and wall.		The Quicksort involves the concepts of pivot and wall.

	The goal is at each iteration to select a pivot (~~always in the same direction~~) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot the right.		The goal is at each iteration to select a pivot (can be randomly chosen) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot the right. Then, we have to run the algorithm again in both left and right sub-arrays around the pivot.

	For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.		For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.
Line 13:		Line 13:
	!		!
	\|-		\|-
	\|~~https://www.youtube.com/watch?v=aQiWF4E8flQ~~		\|
	\|}		\|}

Savoundg at 04:56, 1 June 2018

2018-06-01T04:56:51Z

← Older revision		Revision as of 04:56, 1 June 2018
Line 1:		Line 1:
	Quicksort is an exchange sorting algorithm.		Quicksort is an exchange sorting algorithm.

			The Quicksort involves the concepts of pivot and wall.

			The goal is at each iteration to select a pivot (always in the same direction) and to rebuild the array with all the elements smaller that the pivot on the left and all the elements bigger that the pivot the right.

			For instance, if we always choose the rightmost element of the array as the pivot, the wall starts before the leftmost element, each element smaller than the pivot should be swapped with the closest element from the right of the wall, then the wall should be shifted to one element on the right to get that smaller element on the left side of the wall. Eventually, swap the pivot with the element just on the right side of the wall. What you will get is an array with the pivot that has all his smaller elements on the left and the bigger elements on the right.

			Now, let's do the same thing on the opposite direction: we want to choose the pivot from the left. Therefore, the wall will start on the right. All element bigger than the pivot will be swapped with the closest element of the wall from the left, the the wall should be shifted on the left.

	==Resources==		==Resources==

Savoundg at 04:09, 1 June 2018

2018-06-01T04:09:39Z

← Older revision		Revision as of 04:09, 1 June 2018
Line 1:		Line 1:
	Quicksort is an exchange sorting algorithm.		Quicksort is an exchange sorting algorithm.

			==Resources==
			{\| class="wikitable"
			!
			\|-
			\|https://www.youtube.com/watch?v=aQiWF4E8flQ
			\|}

Savoundg: Created page with "Quicksort is an exchange sorting algorithm."

2018-05-28T04:51:11Z

Created page with "Quicksort is an exchange sorting algorithm."

New page

Quicksort is an exchange sorting algorithm.