Quick Sort - Revision history

Admin: /* Flag */

2019-02-01T08:11:52Z

Flag

← Older revision		Revision as of 08:11, 1 February 2019
Line 68:		Line 68:

	=Flag=		=Flag=

			{{QuickSortFlag}}

	{{AlgorithmsFlag}}		{{AlgorithmsFlag}}

	~~[[Category:Sort]]~~
	~~[[Category:Sorting]]~~
	~~[[Category:Quick Sort]]~~

Admin: /* Notes */

2019-02-01T08:08:08Z

Notes

@@ Line 13: / Line 13: @@
 However, in the worst case (which should happen very infrequently), quicksort is O(N^2).
-Here is a C implementation of quicksort:
+==Implementation==
 <pre>

Admin: /* Algorithm */

2017-08-07T10:19:34Z

Algorithm

← Older revision		Revision as of 10:19, 7 August 2017
Line 21:		Line 21:
	{		{
	int p; // index of partition		int p; // index of partition
	if(hi-lo)>0) {		if((hi-lo)>0) {
	p = partition(s, lo, hi);		p = partition(s, lo, hi);
	quicksort(s, lo, p-1);		quicksort(s, lo, p-1);
Line 38:		Line 38:
	int firsthigh; // divider position for pivot element		int firsthigh; // divider position for pivot element

	p = h;		// pivot equals s at hi
			p = hi;

	firsthigh = 1;		firsthigh = 1;
	for(i = 1; i < h; i++) {		for(i = 1; i < hi; i++) {
	if(s[i] < s[p]) {		if(s[i] < s[p]) {
	wswap(&s[i], &s[firsthigh]);		wswap(&s[i], &s[firsthigh]);

Admin: /* Algorithm */

2017-08-07T04:13:33Z

Algorithm

← Older revision		Revision as of 04:13, 7 August 2017
Line 20:		Line 20:
	quicksort(item_type s[], int lo, int hi)		quicksort(item_type s[], int lo, int hi)
	{		{
	int p; /// index of partition		int p; // index of partition
	if(hi-lo)>0) {		if(hi-lo)>0) {
	p = partition(s, lo, hi);		p = partition(s, lo, hi);

Admin: /* Skiena Chapter 4 */

2017-08-07T04:13:15Z

Skiena Chapter 4

@@ Line 3: / Line 3: @@
 ==Skiena Chapter 4==
-Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting.
+===Overview===
 Quick sort is a ''random'' algorithm. Whenever we deal with a random algorithm, we always want to think about what the worst case scenario is, and what we can do to avoid it. In the case of quicksort, the worst case scenario consists of bad choices for each pivot - namely, each pivot that is chosen happens to be right next to the prior pivot, so we are continually sorting things one at a time, making quick sort equivalent to [[Insertion Sort]].
 In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).
 =Flag=

Admin: /* Skiena Chapter 4 */

2017-08-07T03:40:51Z

Skiena Chapter 4

← Older revision		Revision as of 03:40, 7 August 2017
Line 8:		Line 8:

	In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).		In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).


	=Flag=		=Flag=

Admin at 03:07, 7 August 2017

2017-08-07T03:07:47Z

← Older revision		Revision as of 03:07, 7 August 2017
Line 1:		Line 1:
			=Notes=

			==Skiena Chapter 4==

	Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting.		Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting.

Line 4:		Line 8:

	In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).		In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).


			=Flag=

			{{AlgorithmsFlag}}

			[[Category:Sort]]
			[[Category:Sorting]]
			[[Category:Quick Sort]]

Admin at 03:01, 7 August 2017

2017-08-07T03:01:44Z

← Older revision		Revision as of 03:01, 7 August 2017
Line 1:		Line 1:
	Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on ~~one~~ side of the pivot.		Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on either side of the pivot. The real savings of quicksort come from the fact that, once we partition all elements into a high and low pile, we can now sort these piles independently. Thus, like merge sort, we are progressively reducing the size of the piles of things we are sorting.

			Quick sort is a ''random'' algorithm. Whenever we deal with a random algorithm, we always want to think about what the worst case scenario is, and what we can do to avoid it. In the case of quicksort, the worst case scenario consists of bad choices for each pivot - namely, each pivot that is chosen happens to be right next to the prior pivot, so we are continually sorting things one at a time, making quick sort equivalent to [[Insertion Sort]].

			In the average case, quicksort is O(N log N) - in other words, it is as good as, or better than, heap sort or merge sort (our two "old faithful" O(N log N) search algorithms).

Admin: Created page with "Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on one side of the pivot."

2017-08-07T02:50:27Z

Created page with "Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on one side of the pivot."

New page

Quick sort - also known as partition-exchange sort - is based on the idea of picking a random pivot, and sorting things on one side of the pivot.