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

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

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

Already have an account? Log in

Get OneClass Notes+

Unlimited access to class notes and textbook notes.

YearlyBest Value
75% OFF
$8 USD/m
Monthly
$30 USD/m
You will be charged $96 USD upfront and auto renewed at the end of each cycle. You may cancel anytime under Payment Settings. For more information, see our Terms and Privacy.
Payments are encrypted using 256-bit SSL. Powered by Stripe.