CSC 2200 Lecture Notes - Lecture 23: Quicksort, Sorting Algorithm, Pseudocode
7 views3 pages
19 Jul 2018
School
Department
Course
Professor
CSC 2200 Lecture 23
Quick Sort
• Quick sort
o Highly efficient sorting algorithm and is based on portioning of array into smaller
arrays
o A large array is portioned into two arrays
▪ One of which holds values smaller than specific value (pivot), based on
the partition is made
▪ Another array holds values greater than pivot value
o Partitions array and then calls itself recursively twice to sort the two resulting
subarrays
o Worst case complexity are O(n^2)
▪ Where is the number of items
• Quick sort pivot algorithm
Step 1 − Choose the highest index value has pivot
Step 2 − Take two variables to point left and right of the list excluding pivot
Step 3 − left points to the low index
Step 4 − right points to the high
Step 5 − while value at left is less than pivot move right
Step 6 − while value at right is greater than pivot move left
Step 7 − if both step 5 and step 6 does not match swap left and right
Step 8 − if left ≥ right, the point where they met is new pivota