Quick Sort/Pseudocode: Difference between revisions

Revision as of 08:24, 1 February 2019

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)

@@ Line 1: / Line 1: @@
 ==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==