# CSC 2200 Lecture Notes - Lecture 23: Quicksort, Sorting Algorithm, Pseudocode

7 views3 pages
School
Course
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
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
Unlock document

This preview shows page 1 of the document.
Unlock all 3 pages and 3 million more documents.