2 min read

Quick Sort Algorithm in Data Structures

Quicksort is the fastest algorithm so it is widely used as a better way of searching. It is used everywhere where a stable sort is not needed. It is more efficient and works faster than merge sort in case of smaller array size or datasets.
Quick Sort Algorithm in Data Structures

QuickSort is a Divide and Conquer algorithm like merge sort. It picks an element as pivot and partitions the given array around the picked pivot. There are many different versions of quickSort that pick pivot in different ways.

  1. Always pick first element as pivot.
  2. Always pick last element as pivot (implemented below)
  3. Pick a random element as pivot.
  4. Pick median as pivot.

The key process in quickSort is partition(). Target of partitions is, given an array and an element x of array as pivot, put x at its correct position in sorted array and put all smaller elements (smaller than x) before x, and put all greater elements (greater than x) after x. All this should be done in linear time.

https://www.geeksforgeeks.org/wp-content/uploads/gq/2014/01/QuickSort2.png

/* low  --> Starting index,  high  --> Ending index */

quickSort(arr[], low, high)

{ if (low < high)

{ /* pi is partitioning index, arr[pi] is now at right place */ pi = partition(arr, low, high);

quickSort(arr, low, pi - 1);  //Before pi

 quickSort(arr, pi + 1, high); // After pi } }

Pseudo code for partition()

/* This function takes last element as pivot, places the pivot element at its correct position in sorted array, and places all smaller (smaller than pivot) to left of pivot and all greater elements to right of pivot */

partition (arr[], low, high)

{ // pivot (Element to be placed at right position) pivot = arr[high];

i = (low - 1)  // Index of smaller element and indicates the

// right position of pivot found so far

for (j = low; j <= high- 1; j++) { // If current element is smaller than the pivot

if (arr[j] < pivot) {

i++;    // increment index of smaller element

swap arr[i] and arr[j]

}

}

swap arr[i + 1] and arr[high])

return (i + 1) }

QuickSort - GeeksforGeeks
A computer science portal for geeks. It contains well written, well thought and well explained computer science and programming articles, quizzes and practice/competitive programming/company interview Questions.
https://www.geeksforgeeks.org/quick-sort/

#QuickSort #Algorithm #DivideandConquer #Probyto #probytoAI

Subscribe and follow us for latest news in Data Science and Machine learning and stay updated!
Facebook: https://facebook.com/probyto
Twitter: https://twitter.com/probyto
LinkedIn: https://linkedin.com/company/probyto
Instagram: https://instagram.com/probyto