Quicksort

Definition

Definition

Quicksort is a highly efficient sorting algorithm that works by partitioning an array into smaller sub-arrays, then recursively sorting each sub-array. It follows the divide-and-conquer strategy, making it particularly effective for large datasets

Explanation

Selecting a 'pivot' element from the array and partitioning 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. This process continues until the entire array is sorted

Guidance

• Choose a pivot element from the array (commonly the last element)
• Partition the array into two sub-arrays
  • elements less than the pivot
  • elements greater than the pivot
• Recursively apply the above steps to the sub-arrays until the base case (sub-array size is 1 or 0) is reached
• Concatenate the sorted sub-arrays to obtain the sorted array

Tips

• always try to choose a pivot that helps in evenly dividing the array. Common choices include the first, last, or middle element
• implementing a technique like the 'median of three' to choose a pivot can improve performance, especially for nearly sorted arrays
• quicksort can be implemented in-place, reducing the need for additional memory allocation

Practice

Practice

quicksort(array, low, high):
  if low < high:
    // Partition the array and get the pivot index
    pivot_index = partition(array, low, high)
    // Recursively sort the sub-arrays
    quicksort(array, low, pivot_index - 1)
    quicksort(array, pivot_index + 1, high)

partition(array, low, high):
  // Choose the pivot (here, we choose the last element)
  pivot = array[high]
  // Index of the smaller element
  smaller_index = low - 1

  // Iterate through the array from low to high
  for j = low to high - 1:
    // If current element is smaller than or equal to pivot
    if array[j] <= pivot:
      // Increment index of smaller element
      smaller_index = smaller_index + 1
      // Swap smaller element with current element
      swap(array, smaller_index, j)

  // Swap pivot with element at smaller_index + 1
  swap(array, smaller_index + 1, high)
  // Return the partitioning index
  return smaller_index + 1

swap(array, i, j):
  // Swap elements at indices i and j in the array
  temp = array[i]
  array[i] = array[j]
  array[j] = temp

Solution

package main

func quicksort(arr []int) []int {
    if len(arr) <= 1 {
        return arr
    }

    pivot := arr[0]
    var left, right []int

    for _, v := range arr[1:] {
        if v <= pivot {
            left = append(left, v)
        } else {
            right = append(right, v)
        }
    }

    left = quicksort(left)
    right = quicksort(right)

    return append(append(left, pivot), right...)
}

import java.util.Arrays;

public class QuickSort {

  public static int[] quicksort(int[] arr) {
    if (arr.length <= 1) {
      return arr;
    }

    int pivot = arr[0];
    int[] left = Arrays.stream(arr).skip(1).filter(x -> x <= pivot).toArray();
    int[] right = Arrays.stream(arr).skip(1).filter(x -> x > pivot).toArray();

    left = quicksort(left);
    right = quicksort(right);

    int[] result = new int[left.length + right.length + 1];
    System.arraycopy(left, 0, result, 0, left.length);
    result[left.length] = pivot;
    System.arraycopy(right, 0, result, left.length + 1, right.length);

    return result;
  }
}

function quicksort(arr) {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[0];
  const left = [];
  const right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quicksort(left), pivot, ...quicksort(right)];
}

fun quicksort(arr: IntArray): IntArray {
    if (arr.size <= 1) return arr

    val pivot = arr[0]
    val left = arr.drop(1).filter { it <= pivot }.toIntArray()
    val right = arr.drop(1).filter { it > pivot }.toIntArray()

    val leftSorted = quicksort(left)
    val rightSorted = quicksort(right)

    return leftSorted + pivot + rightSorted
}

def quicksort(arr):
    if len(arr) <= 1:
        return arr

    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]

    return quicksort(left) + [pivot] + quicksort(right)

fn quicksort(arr: &mut [i32]) {
    if arr.len() <= 1 {
        return;
    }

    let pivot = arr[0];
    let (mut left, mut right): (Vec<_>, Vec<_>) = arr[1..]
        .iter()
        .partition(|&x| x <= &pivot);

    quicksort(&mut left);
    quicksort(&mut right);

    arr.copy_from_slice(&[left, vec![pivot], right].concat());
}

function quicksort(arr: number[]): number[] {
  if (arr.length <= 1) {
    return arr;
  }

  const pivot = arr[0];
  const left: number[] = [];
  const right: number[] = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] <= pivot) {
      left.push(arr[i]);
    } else {
      right.push(arr[i]);
    }
  }

  return [...quicksort(left), pivot, ...quicksort(right)];
}