Learn Tech Skills from Scratch @ Scaler EDGE

- Courses
- Programming
- Arrays
- Quicksort Algorithm

TUTORIAL

1. Introduction To Pointers In C/C++

2. Arrays In Programming Fundamentals

3. Pointers And Arrays

4. Pointers And 2 D Arrays

5. Array Implementation Details

6. Sorting Algorithms

7. Insertion Sort Algorithm

8. Merge Sort Algorithm

9. Quick Sort Algorithm

10. Sort Implementation Details

11. Selection Sort

12. Bubble Sort

QuickSort is one of the most efficient sorting algorithms and is based on the splitting of an array into smaller ones. The name comes from the fact that, quick sort is capable of sorting a list of data elements significantly faster than any of the common sorting algorithms. And like Merge sort, Quick sort also falls into the category of divide and conquer approach of problem-solving methodology.

**Quick sort works in the following manner:**

- Taking the analogical view in perspective, consider a situation where one had to sort the papers bearing the names of the students, by name. One might use the approach as follows:
- Select a splitting value, say L. The splitting value is also known as
**Pivot**. - Divide the stack of papers into two. A-L and M-Z. It is not necessary that the piles should be equal.
- Repeat the above two steps with the A-L pile, splitting it into its significant two halves. And M-Z pile, split into its halves. The process is repeated until the piles are small enough to be sorted easily.
- Ultimately, the smaller piles can be placed one on top of the other to produce a fully sorted and ordered set of papers.
- The approach used here is
**recursion**at each split to get to the single-element array. - At every split, the pile was divided and then the same approach was used for the smaller piles.
- Due to these features, quick sort is also called as
*partition exchange sort*.

An example might come in handy to understand the concept.

Consider the following array: 50, 23, 9, 18, 61, 32

**Step 1**: Decide any value to be the pivot from the list (generally the last value). Suppose for two values “Low” and “High” corresponding to the first index, and last index.

In our case low is 0 and high is 5.

Values at low and high are 50 and 32 and Value of pivot is 32.

Hence, call for partitioning, rearranging the array in such a way that pivot (32) comes to its actual position. And to the left of the pivot, the array has all the elements less than it, and to the right greater than it.

In the partition function, we start from the first element and compare it with the pivot. Since 50 is greater than 32, we don’t make any change and move on to the next element 23.

Compare again with the pivot. Since 23 is less than 32, we swap 50 and 23. The array becomes 23, 50, 9, 18, 61, 32.

We move on to the next element 9 which is again less than pivot (32) thus swapping it with 50 makes our array as

23, 9, 50, 18, 61, 32.

Similarly, for next element 18 which is less than 32, the array becomes

23, 9, 18, 50, 61, 32 Now 61 is greater than pivot (32), hence no changes.

Lastly, we swap our pivot with 50 so that it comes to the correct position.

Thus the pivot (32) comes at its actual position and all elements to its left are lesser, and all elements to the right are greater than itself.

**Step 2**: Hence the array after the first step becomes

23, 9, 18, **32**, 61, 50

**Step 3**: Now the list is divided into two parts:

- Sublist before pivot
- Sublist after pivot

Sub-list before and after Pivot

**Step 4**: Repeat the steps for these sublists again.

The final array thus becomes 9, 18, 23, 32, 50, 61.

```
/* 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
}
}
```

Following are C, C++, Java and Python implementations of QuickSort.

```
Implementation of Quick Sort Algorithm in C:
# include <stdio.h>
// to swap two numbers
void swap(int* a, int* b)
{
int t = *a;
*a = *b;
*b = t;
}
int partition (int arr[], int low, int high)
{
int pivot = arr[high]; // selecting last element as pivot
int i = (low - 1); // index of smaller element
for (int j = low; j <= high- 1; j++)
{
// If the current element is smaller than or equal to pivot
if (arr[j] <= pivot)
{
i++; // increment index of smaller element
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
/*
a[] is the array, p is starting index, that is 0,
and r is the last index of array.
*/
void quicksort(int a[], int p, int r)
{
if(p < r)
{
int q;
q = partition(a, p, r);
quicksort(a, p, q-1);
quicksort(a, q+1, r);
}
}
// function to print the array
void printArray(int a[], int size)
{
int i;
for (i=0; i < size; i++)
{
printf("%d ", a[i]);
}
printf("\n");
}
int main()
{
int arr[] = {9, 7, 5, 11, 12, 2, 14, 3, 10, 6};
int n = sizeof(arr)/sizeof(arr[0]);
// call quickSort function
quicksort(arr, 0, n-1);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}
```

```
Quicksort example program in c++:
#include<iostream>
#include<cstdlib>
using namespace std;
// Swapping two values.
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
// Partitioning the array on the basis of values at high as pivot value.
int Partition(int a[], int low, int high)
{
int pivot, index, i;
index = low;
pivot = high;
// Getting index of the pivot.
for(i=low; i < high; i++)
{
if(a[i] < a[pivot])
{
swap(&a[i], &a[index]);
index++;
}
}
// Swapping value at high and at the index obtained.
swap(&a[pivot], &a[index]);
return index;
}
// Random selection of pivot.
int RandomPivotPartition(int a[], int low, int high)
{
int pvt, n, temp;
n = rand();
// Randomizing the pivot value in the given subpart of array.
pvt = low + n%(high-low+1);
// Swapping pivot value from high, so pivot value will be taken as a pivot while partitioning.
swap(&a[high], &a[pvt]);
return Partition(a, low, high);
}
int QuickSort(int a[], int low, int high)
{
int pindex;
if(low < high)
{
// Partitioning array using randomized pivot.
pindex = RandomPivotPartition(a, low, high);
// Recursively implementing QuickSort.
QuickSort(a, low, pindex-1);
QuickSort(a, pindex+1, high);
}
return 0;
}
int main()
{
int n, i;
cout<<"\nEnter the number of data elements to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
QuickSort(arr, 0, n-1);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
```

```
// Java program for implementation of QuickSort
class QuickSort
{
/* 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 */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
```

```
# Python program for Quicksort
# 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
def partition(arr,low,high):
i = ( low-1 ) # index of smaller element
pivot = arr[high] # pivot
for j in range(low , high):
# If current element is smaller than or
# equal to pivot
if arr[j] <= pivot:
# increment index of smaller element
i = i+1
arr[i],arr[j] = arr[j],arr[i]
arr[i+1],arr[high] = arr[high],arr[i+1]
return ( i+1 )
# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index
# Function to do Quick sort
def quickSort(arr,low,high):
if low < high:
# pi is partitioning index, arr[p] is now
# at right place
pi = partition(arr,low,high)
# Separately sort elements before
# partition and after partition
quickSort(arr, low, pi-1)
quickSort(arr, pi+1, high)
# Driver code to test above
arr = [10, 7, 8, 9, 1, 5]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
print ("%d" %arr[i]),
```

- Scaler Academy Review
- System Design Interview Questions
- Google Interview Questions
- Facebook Interview Questions
- Amazon Interview Questions
- Microsoft Interview Questions
- SQL Interview Questions
- Python Interview Questions
- Javascript Interview Questions
- MVC Interview Questions
- React Interview Questions
- Angular Interview Questions
- Directi Interview Questions
- Yahoo Interview Questions
- LinkedIn Interview Questions
- VMware Interview Questions
- eBay Interview Questions
- Flipkart Interview Questions

Log In using

or