Algorithm
Quicksort is a widely used sorting algorithm that follows the divide-and-conquer paradigm. It was developed by Tony Hoare in 1960. The basic idea of quicksort is to select a pivot element from the array and partition the other elements into two sub-arrays according to whether they are less than or greater than the pivot. The sub-arrays are then recursively sorted.
Here's a high-level overview of the quicksort algorithm:
-
Choose a Pivot: Select a pivot element from the array. The choice of the pivot can be done in various ways, such as selecting the first element, the last element, or a random element. The pivot's choice can affect the algorithm's performance.
-
Partitioning: Rearrange the array elements such that elements less than the pivot are on the left, and elements greater than the pivot are on the right. The pivot itself is in its final sorted position. This step is often implemented using the two-pointer approach.
-
Recursion: Recursively apply the quicksort algorithm to the sub-arrays on the left and right of the pivot until the base case is reached (i.e., sub-arrays of size 1 or 0).
Code Examples
#1 Quicksort Algorithm implement in Python
Code -
Python Programming
def quicksort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
# Example usage:
my_list = [3, 6, 8, 10, 1, 2, 1]
sorted_list = quicksort(my_list)
print(sorted_list)
#3 Quicksort Algorithm implement in C
Code -
C Programming
#include <stdio.h>
// Function to swap two elements in an array
void swap(int* a, int* b) {
int temp = *a;
*a = *b;
*b = temp;
}
// Function to partition the array and return the pivot index
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // Choose the last element as the pivot
int i = low - 1; // Index of smaller element
for (int j = low; j < high; j++) {
// If the current element is smaller than or equal to the pivot
if (arr[j] <= pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
// Swap the pivot element with the element at (i + 1), which is the correct position for the pivot
swap(&arr[i + 1], &arr[high]);
return i + 1; // Return the pivot index
}
// Quicksort function
void quicksort(int arr[], int low, int high) {
if (low < high) {
// Partition the array and get the pivot index
int pivotIndex = partition(arr, low, high);
// Recursively sort the sub-arrays on either side of the pivot
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
// Function to print an array
void printArray(int arr[], int size) {
for (int i = 0; i < size; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}
// Driver program to test the Quicksort algorithm
int main() {
int arr[] = {12, 7, 11, 8, 5, 2, 6, 9};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: ");
printArray(arr, n);
quicksort(arr, 0, n - 1);
printf("Sorted array: ");
printArray(arr, n);
return 0;
}
#4 Quicksort Algorithm implement in C++
Code -
C++ Programming
#include <iostream>
#include <vector>
template < typename T>
int partition(std::vector<T> &arr, int low, int high) {
T pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; ++j) {
if (arr[j] < pivot) {
++i;
std::swap(arr[i], arr[j]);
}
}
std::swap(arr[i + 1], arr[high]);
return i + 1;
}
template < typename T>
void quicksort(std::vector<T> &arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quicksort(arr, low, pivotIndex - 1);
quicksort(arr, pivotIndex + 1, high);
}
}
int main() {
std::vector<int> arr = {12, 4, 5, 6, 7, 3, 1, 15};
int n = arr.size();
std::cout << "Original array: ";
for (const auto &element : arr) {
std::cout << element << " ";
}
std::cout << std::endl;
quicksort(arr, 0, n - 1);
std::cout << "Sorted array: ";
for (const auto &element : arr) {
std::cout << element << " ";
}
std::cout << std::endl;
return 0;
}
#4 Quicksort Algorithm implement in Java
Code -
Java Programming
public class QuickSort {
public static void main(String[] args) {
int[] array = {12, 4, 5, 6, 7, 3, 1, 15};
System.out.println("Original array: " + Arrays.toString(array));
quickSort(array, 0, array.length - 1);
System.out.println("Sorted array: " + Arrays.toString(array));
}
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
// Find the partition index such that elements smaller than pivot are on the left
// and elements greater than pivot are on the right
int partitionIndex = partition(array, low, high);
// Recursively sort the sub-arrays
quickSort(array, low, partitionIndex - 1);
quickSort(array, partitionIndex + 1, high);
}
}
private static int partition(int[] array, int low, int high) {
// Choose the rightmost element as pivot
int pivot = array[high];
// Index of smaller element
int i = low - 1;
// Traverse through the array and rearrange elements
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
// Swap array[i] and array[j]
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
// Swap array[i+1] and array[high] (pivot)
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
// Return the partition index
return i + 1;
}
}
Demonstration
Quicksort Data Structure and Algorithm