Quick Sort Program with Explanation and Code

2025-11-01 quick sort sorting algorithms divide and conquer fast sorting method recursion logical programs algorithm explanation array sorting python quicksort c quicksort javascript quick sort php sorting program csharp quicksort data structure programs

Quick Sort is one of the fastest and most widely used sorting algorithms. This guide explains how Quick Sort works with step-by-step logic and includes complete program code in Python, C, JavaScript, PHP, and C#. Perfect for students and interview preparation.

Program Explanation

What is Quick Sort?

Quick Sort is a highly efficient divide-and-conquer sorting algorithm. It works by selecting a pivot element, partitioning the array around the pivot, and then recursively sorting the left and right sub-arrays.

Steps to Solve

  1. Select a pivot element from the array.
  2. Partition the array: place all smaller elements to the left and larger ones to the right.
  3. Recursively apply Quick Sort on the left sub-array.
  4. Recursively apply Quick Sort on the right sub-array.
  5. Combine results to form a fully sorted array.
  6. Base case: when array size is 0 or 1, it's already sorted.

Key Points

  • Quick Sort is one of the fastest sorting algorithms.
  • Average time complexity: O(n log n).
  • Worst-case time complexity: O(n²) (when pivot is poorly chosen).
  • Uses recursion heavily.
  • Not a stable sort.
  • In-place algorithm: uses minimal extra memory.
  • Pivot selection is crucial for performance.

Program Code


def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

arr = list(map(int, input("Enter numbers: ").split()))
print("Sorted array:", quick_sort(arr))
      

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }

    swap(&arr[i + 1], &arr[high]);
    return i + 1;
}

void quickSort(int arr[], int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

int main() {
    int n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter numbers: ");
    for (int i = 0; i < n; i++) scanf("%d", &arr[i]);

    quickSort(arr, 0, n - 1);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);

    return 0;
}
      

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

  let pivot = arr[Math.floor(arr.length / 2)];
  let left = arr.filter(x => x < pivot);
  let middle = arr.filter(x => x === pivot);
  let right = arr.filter(x => x > pivot);

  return [...quickSort(left), ...middle, ...quickSort(right)];
}

let arr = prompt("Enter numbers:").split(" ").map(Number);
console.log("Sorted array:", quickSort(arr));
      

using System;
using System.Linq;

class Program {

    static void QuickSort(int[] arr, int low, int high) {
        if (low < high) {
            int pi = Partition(arr, low, high);

            QuickSort(arr, low, pi - 1);
            QuickSort(arr, pi + 1, high);
        }
    }

    static int Partition(int[] arr, int low, int high) {
        int pivot = arr[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (arr[j] < pivot) {
                i++;
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }

        int temp2 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp2;

        return i + 1;
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Console.ReadLine().Split().Select(int.Parse).ToArray();

        QuickSort(arr, 0, arr.Length - 1);

        Console.Write("Sorted array: ");
        foreach (int num in arr)
            Console.Write(num + " ");
    }
}
      

<?php

function quickSort($arr) {
    if (count($arr) <= 1)
        return $arr;

    $pivot = $arr[floor(count($arr) / 2)];
    $left = $middle = $right = [];

    foreach ($arr as $x) {
        if ($x < $pivot) $left[] = $x;
        elseif ($x == $pivot) $middle[] = $x;
        else $right[] = $x;
    }

    return array_merge(quickSort($left), $middle, quickSort($right));
}

$arr = explode(" ", readline("Enter numbers: "));
$result = quickSort($arr);

echo "Sorted array: " . implode(" ", $result);

?>
1