COSC 130: Data Structures
Sorting Algorithms
QuickSort Demonstration Instructions:
Right-click on a bubble to turn it red.
Right-click twice to turn it black and fix it in place.
Right-click a black bubble again to turn it blue and make it movable again.
Left-click a bubble to select it.
Select two bubbles and press SPACE to swap their positions.
Drag the left and right pointers to move them.
Click anywhere or press any key to begin.
QuickSort
QuickSort is a divide-and-conquer sorting algorithm that works by:
Dividing the array into subarrays using a pivot.
Recursively sorting the subarrays.
Steps of QuickSort
Base Case: If the array or subarray has one or zero elements, it is already sorted. Simply return.
Recursive Case:
Choose a pivot element from the array (commonly the last element, first element, or a randomly chosen element).
Call the partition function to:
Place the pivot in its correct sorted position.
Rearrange elements so that:
All elements smaller than the pivot are on its left.
All elements larger than the pivot are on its right.
Recursively apply QuickSort to the left and right subarrays.
Partition Function The partition function divides the array into two parts and returns the index of the pivot in its correct position.
Input: An array, start index (low), and end index (high).
Output: The index of the pivot element after partitioning.
Steps:
Select a pivot element (commonly array[high]).
Initialize a pointer i to track the boundary of smaller elements.
Iterate through the array using a pointer j:
If array[j] < pivot, swap array[i] and array[j], then increment i.
After the loop, swap the pivot element with the element at index i to place the pivot in its correct position.
Return i.
Complexity Analysis
Best/Average Case: O(nlogn)O(n \log n)O(nlogn) when the pivot divides the array into two nearly equal parts.
Worst Case: O(n2)O(n^2)O(n2) when the pivot is always the smallest or largest element.
Space Complexity: O(logn)O(\log n)O(logn) for recursive stack calls.