Quick sort

Quick Sort

Normal
Generate Random Numbers
L R

How to use ?

Enter an array separated by commas as : 16,15,15,10,1 or just press the hand icon to generate a random array then press enter or Sort button. Sorting will start and you can watch each pass as it gets sorted. When it shows green it means the two of them are being compared when red shows, it means the left number is greater than right number so it needs swapping The blue color means the number is at its correct position and thus sorted it will continue to check other numbers until it reaches end.

Quick Sort Overview

History

Quick sort was developed by Tony Hoare in 1960. It is a divide-and-conquer algorithm that is efficient for large datasets. Quick sort has become one of the most widely used sorting algorithms due to its performance in practice and its ability to sort in place.

Current Uses

  • General Purpose: Used in a variety of applications, including databases and memory sorting.
  • Libraries: Often implemented in standard libraries for programming languages due to its efficiency.
  • Embedded Systems: Commonly used in systems with limited resources for efficient sorting.

Time and Space Complexity

Time Complexity

  • Best Case: O(n log n) – When the pivot divides the array into nearly equal halves.
  • Average Case: O(n log n) – The average case performance is efficient.
  • Worst Case: O(n2) – Occurs when the smallest or largest element is always chosen as the pivot.

Space Complexity

Space Complexity: O(log n) – Due to the recursive stack space used during the algorithm's execution.

Pseudo Code

function quickSort(arr, low, high):
    if low < high:
        pi = partition(arr, low, high)
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)

function partition(arr, low, high):
    pivot = arr[high]
    i = low - 1
    for j from low to high - 1:
        if arr[j] <= pivot:
            i = i + 1
            swap arr[i] and arr[j]
    swap arr[i + 1] and arr[high]
    return i + 1

Key Characteristics

  • In-Place: Quick sort requires minimal additional storage space.
  • Not Stable: The algorithm is not stable due to the way it swaps elements.

Summary

Quick sort is a highly efficient sorting algorithm that utilizes the divide-and-conquer strategy. Despite its worst-case time complexity of O(n2), it is widely used due to its average-case efficiency and practical performance.

Quick Sort Code Implementation