Sorting Algorithm Assignment: Quicksort
Description
This assignment implements the quicksort algorithm to sort an array of integers. The array
contains 21 randomly ordered items. Quicksort is chosen for this assignment due to its
efficient average-case performance compared to other algorithms such as insertion sort.
How Quicksort Works
Quicksort is a divide-and-conquer algorithm that works as follows:
1. Pivot Selection:
○ A pivot element is chosen from the array. This pivot can be the first element,
last element, a random element, or the median of the array.
2. Partitioning:
○ The array is partitioned into two sub-arrays: elements less than the pivot are
moved to its left, and elements greater than the pivot are moved to its right.
3. Recursive Sorting:
○ The quicksort algorithm is then recursively applied to the left and right sub-
arrays until the base case is reached, where the sub-arrays have one or zero
elements.
4. Combining the Results:
○ After partitioning and recursive sorting, the combined result is a fully sorted
array.
Quicksort Implementation in Java
public class QuicksortExample {
// Method to perform the quicksort algorithm
public static void quicksort(int[] array, int low, int high,
int[] exchangeCount) {
if (low < high) {
int pi = partition(array, low, high, exchangeCount);
quicksort(array, low, pi - 1, exchangeCount);
quicksort(array, pi + 1, high, exchangeCount);
}
}
// Method to partition the array and keep track of the number of
exchanges
public static int partition(int[] array, int low, int high,
int[] exchangeCount) {
int pivot = array[high];
int i = (low - 1);
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
// Swap elements and increment exchange count
int temp = array[i];
array[i] = array[j];
array[j] = temp;
exchangeCount[0]++;
}
}
// Swap pivot to its correct position
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
exchangeCount[0]++;
return i + 1;
}
public static void main(String[] args) {
int[] arr1 = {12, 9, 4, 99, 120, 1, 3, 10, 23, 45, 75, 69,
31, 88, 101, 14, 29, 91, 2, 0, 77};
int[] exchangeCount = {0};
[Link]("Printing unsorted array before
Quicksort");
for (int i : arr1) {
[Link](i + " ");
}
[Link]();
quicksort(arr1, 0, [Link] - 1, exchangeCount);
[Link]("Printing sorted array after Quicksort");
for (int i : arr1) {
[Link](i + " ");
}
[Link]();
[Link]("Number of exchanges required: " +
exchangeCount[0]);
}
}
Asymptotic Analysis
● Best Case: O(n log n)
○ Occurs when the pivot divides the array into two nearly equal halves.
● Average Case: O(n log n)
○ On average, the pivot selection yields two sub-arrays of similar size.
● Worst Case: O(n^2)
○ Occurs when the pivot is the smallest or largest element, leading to highly
unbalanced partitions (e.g., already sorted or reverse-sorted array).
Efficiency Comparison
● Insertion Sort Exchanges: 114
● Quicksort Exchanges: The number of exchanges will vary based on the input and
pivot selection but is generally expected to be lower than the insertion sort for large
arrays due to more efficient partitioning and fewer overall comparisons and
exchanges.
Expected Output
For the given array, the quicksort implementation will sort the array and display the sorted
list along with the number of exchanges required to complete the sort. The expected number
of exchanges should be less than that of the insertion sort due to the more efficient nature of
quicksort.
Jeliot Output:
Conclusion
Quicksort is chosen for its superior average-case performance compared to insertion sort. It
effectively reduces the number of exchanges and comparisons needed to sort an array,
making it a more efficient choice for large datasets. The implementation provided
demonstrates the key steps of quicksort and confirms its efficiency through both theoretical
analysis and practical output.