# 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