Data Structures & Algorithms – Sorting algorithms (e.g. quicksort, mergesort)
Sorting algorithms are a set of methods and techniques used to organize and rearrange a collection of items in a specific order. There are many different sorting algorithms with varying time and space complexities, and each one is suited to different types of data and use cases.
Two of the most well-known and widely used sorting algorithms are quicksort and mergesort.
Quicksort is a divide-and-conquer algorithm that works by partitioning an array into two sub-arrays, and then recursively sorting the sub-arrays. The basic idea is to choose a “pivot” element from the array, partition the other elements into two groups, one less than the pivot and one greater than the pivot, and then recursively sort the sub-arrays. The pivot can be chosen in various ways like picking the first element, the last element, or a random element from the array. The time complexity of quicksort is O(n log n) on average and O(n^2) in worst case.
Here is an example of quicksort implemented in Python:
def quicksort(arr):
if len(arr) <= 1:
return arr
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)
print(quicksort([3,6,8,10,1,2,1])) # [1, 1, 2, 3, 6, 8, 10]
Mergesort is a divide-and-conquer algorithm that divides an array into two sub-arrays, recursively sorts the sub-arrays, and then merges the sorted sub-arrays back together. The time complexity of mergesort is O(n log n).
Here is an example of mergesort implemented in Python:
def merge_sort(arr):
if len(arr) <= 1:
return arr
middle = len(arr) // 2
left = merge_sort(arr[:middle])
right = merge_sort(arr[middle:])
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
print(merge_sort([3,6,8,10,1,2,1])) # [1, 1, 2, 3, 6, 8, 10]
Here is an example of quicksort implemented in JavaScript:
function quickSort(arr) {
if (arr.length <= 1) {
return arr;
}
let pivot = arr[arr.length - 1];
let left = [];
let right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
console.log(quickSort([3, 6, 8, 10, 1, 2, 1])); // [1, 1, 2, 3, 6, 8, 10]
Here is an example of mergesort implemented in JavaScript:
function merge_sort(arr) {
if (arr.length <= 1) {
return arr;
}
var middle = Math.floor(arr.length / 2);
var left = arr.slice(0, middle);
var right = arr.slice(middle);
return merge(merge_sort(left), merge_sort(right));
}
function merge(left, right) {
var result = [];
while (left.length && right.length) {
if (left[0] < right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
return result.concat(left, right);
}
console.log(merge_sort([3,6,8,10,1,2,1])); // [1, 1, 2, 3, 6, 8, 10]
Here is an example of quicksort implemented in Java:
import java.util.Arrays;
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex);
quickSort(arr, pivotIndex + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
int i = low - 1;
int j = high + 1;
while (true) {
do {
i++;
} while (arr[i] < pivot);
do {
j--;
} while (arr[j] > pivot);
if (i >= j) {
return j;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
public static void main(String[] args) {
int[] arr = {3,6,8,10,1,2,1};
quickSort(arr, 0, arr.length-1);
System.out.println(Arrays.toString(arr)); // [1, 1, 2, 3, 6, 8, 10]
}
}
Here is an example of mergesort implemented in Java:
import java.util.Arrays;
public class MergeSort {
public static void mergeSort(int[] arr, int l, int r) {
if (l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
public static void merge(int[] arr, int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int[] L = new int[n1];
int[] R = new int[n2];
for (int i = 0; i < n1; i++) {
L[i] = arr[l + i];
}
for (int j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
}
int i = 0, j = 0;
int k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
}
k++;
}
while (i < n1) {
arr[k] = L[i];
i++;
k++;
}
while (j < n2) {
arr[k] = R[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {3, 6, 8, 10, 1, 2, 1};
mergeSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr)); // [1, 1, 2, 3, 6, 8, 10]
}
}
Here is an example of quicksort implemented in Rust:
fn quick_sort(arr: &mut [i32], low: usize, high: usize) {
if low < high {
let pivot_index = partition(arr, low, high);
quick_sort(arr, low, pivot_index);
quick_sort(arr, pivot_index + 1, high);
}
}
fn partition(arr: &mut [i32], low: usize, high: usize) -> usize {
let pivot = arr[low];
let mut i = low - 1;
let mut j = high + 1;
loop {
i += 1;
while arr[i] < pivot {
i += 1;
}
j -= 1;
while arr[j] > pivot {
j -= 1;
}
if i >= j {
return j;
}
arr.swap(i, j);
}
}
fn main() {
let mut arr = [3, 6, 8, 10, 1, 2, 1];
quick_sort(&mut arr, 0, arr.len() - 1);
println!("{:?}", arr); // [1, 1, 2, 3, 6, 8, 10]
}
Here is an example of mergesort implemented in Rust:
fn merge_sort(arr: &mut[i32], l: usize, r: usize) {
if l < r {
let m = (l + r) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
fn merge(arr: &mut[i32], l: usize, m: usize, r: usize) {
let n1 = m - l + 1;
let n2 = r - m;
let mut L = Vec::with_capacity(n1);
let mut R = Vec::with_capacity(n2);
for i in 0..n1 {
L.push(arr[l + i]);
}
for j in 0..n2 {
R.push(arr[m + 1 + j]);
}
let mut i = 0;
let mut j = 0;
let mut k = l;
while i < n1 && j < n2 {
if L[i] <= R[j] {
arr[k] = L[i];
i += 1;
} else {
arr[k] = R[j];
j += 1;
}
k += 1;
}
while i < n1 {
arr[k] = L[i];
i += 1;
k += 1;
}
while j < n2 {
arr[k] = R[j];
j += 1;
k += 1;
}
}
fn main() {
let mut arr = [3,6,8,10,1,2,1];
merge_sort(&mut arr, 0, arr.len()-1);
println!("{:?}", arr); // [1, 1, 2, 3, 6, 8, 10]
}
As you can see, the basic structure of the quicksort and mergesort algorithms are similar in all four languages. The main differences are in the syntax and the way that functions are called. It’s worth noting that the quicksort has a worst case time complexity of O(n^2) due to the pivot selection. To avoid the worst case scenario, we can use a more sophisticated pivot selection method like median of three or random pivot selection.