Quick Sort

Introduction

Quick Sort is an efficient sorting technique used in JAVA extensively to sort data collections in either ascending or descending order. Like the Merge Sort, Quick Sort also applies the technique of breaking up an array into two parts. It then chooses a pivot and operates around it.

How does Quick Sort Work?

The main element of the Quick Sort technique is the pivot of the data structure that is being sorted. Pivot is the centralized element of the collection basing which other elements will be sorted. There are several ways to choose a pivot. There are as follows:

  • Picking the first element as the pivot.
  • Picking the last element as the pivot.
  • Picking a random element as the pivot.
  • Picking the median value of the elements as the pivot.

Algorithm (Choosing the last element as the pivot point)

Let us assume we have an array as follows: arr[] = {10, 50, 40, 30}

We will assume two indices i and j. j will always lead i by one. The pivot here is 30.

  1. The algorithm tries to sort the pivot in the right place such that all elements to the left of the pivot is smaller and to the right of the pivot is larger. (If you are sorting by ascending order.)
  2. Let us start with the first element. 10 is smaller than 30. It is also smaller than the next element 50. So, no swapping takes place.
  3. 50 is larger than the pivot and also larger than the next element 40. Therefore, the pivot is swapped with 50 giving us the following array: arr[] = {10, 30, 40, 50}

Example and Code

class QuickSort {
 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 (arr[j] < pivot) {
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// Swapping terms if required
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}

void sort(int arr[], int low, int high)
{
if (low < high)
{
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}

//To Print out the contents of the array
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}


//This is the main method that will  
public static void main (String args[])
{
int arr[] = {10, 50, 40, 30};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}

 

Output

10
30
40
50

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.