Quick Sort/Pseudocode - Revision history

Admin: /* Recursive Quick Sort */

2019-02-01T08:26:43Z

Recursive Quick Sort

← Older revision		Revision as of 08:26, 1 February 2019
Line 22:		Line 22:
	function quicksort( array[] s, int low_index, int high_index ):		function quicksort( array[] s, int low_index, int high_index ):
	// Allocate var for index of partition		// Allocate var for index of partition
	~~int~~ p		p = 0
	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)
	quicksort(s, p+1, hi)		quicksort(s, p+1, hi)

2019-02-01T08:26:22Z

Recursive Quick Sort

← Older revision		Revision as of 08:26, 1 February 2019
Line 18:		Line 18:

	==Recursive Quick Sort==		==Recursive Quick Sort==

			<pre>
			function quicksort( array[] s, int low_index, int high_index ):
			// Allocate var for index of partition
			int p
			if (hi-lo)>0:
			p = partition( s, lo, hi )
			quicksort(s, lo, p-1)
			quicksort(s, p+1, hi)
			</pre>

	==Quick Sort with Heap==		==Quick Sort with Heap==

2019-02-01T08:24:25Z

Quick Sort Algorithm Notes

← Older revision		Revision as of 08:24, 1 February 2019
Line 1:		Line 1:
	==Quick Sort Algorithm Notes==		==Quick Sort Algorithm Notes==

			Nice notes here from Skiena: https://charlesreid1.com/wiki/Quick_Sort#Notes

			Quick sort, like merge sort, requires addressing some topics in the respective language:

			* implement an array or list-like data structure
			* implement a generic type data structure (start simple with integers and strings if it is up to us)
			* implement custom comparator for custom objects
			* random choice of pivot
			* heap (tree) data structure
			* recursion (and recursion limits)

			Split the quicksort operation into two parts:

			* the main quicksort function (recursive)
			* the partition function (rearrange the elements of the array around the pivot, and return the index of the pivot - along with the "pivoted" data)

	==Recursive Quick Sort==		==Recursive Quick Sort==

2019-02-01T08:12:05Z

Created page with "==Quick Sort Algorithm Notes== ==Recursive Quick Sort== ==Quick Sort with Heap== ==Flags== {{QuickSortFlag}}"

New page

==Quick Sort Algorithm Notes==

==Recursive Quick Sort==

==Quick Sort with Heap==

==Flags==

{{QuickSortFlag}}