Sort algorithms order the elements of an array according to a predefined order.
Quick sort is a divide and conquer algorithm. In a divide and conquer sorting
algorithm the original data is separated into two parts “divide” which are
individually sorted and “conquered” and then combined.

Algorithm:

If the array contains only one element or zero elements than the array is sorted.
If the array contains more than one element than:

  • Select an element from the array. Which is call the “pivot element”. For example select the element in the middle of the array.
  • All the elements which are smaller then the pivot element are place in one array and all elements which are larger are place in another array.
  • Sort both arrays by recursively applying Quick sort to them.
  • Combine the arrays.
  • Quicksort can be implement to sort “in-place”.
  • This means that the sorting takes place in the array and that no additional array needs to be created.

Program: Java program for implementation of Quick Sort

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-1; 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();
}
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);
}
}

Output:

Sorted array:
1 5 7 8 9 10
Rich results on Google's SERP when searching for 'Quick Sort'

There are other sorting algorithms are available like Bubble sort, Insertion Sort, Merge sort, etc.

Leave a Reply

Your email address will not be published. Required fields are marked *

Back to Top