AlphaCodingSkills

Quick Sort


Advertisements

Previous Page Next Page

Quick sort is a divide and conquer algorithm. It is based on the idea of choosing one element as a pivot and partitioning the array around the pivot with left side of the pivot containing all elements less than the pivot and right side of the pivot containing all elements greater than the pivot. There are many ways to choose the pivot. Few of them are mentioned below:

  • First element of the array
  • Last element of the array
  • Random element of the array
  • Median index element of the array

The quick sort has less space complexity as compared to merged sort because it do not use auxiliary array.

Example:

To understand the quick sort, lets consider an unsorted array [-4, 1, 25, 50, 8, 10, 23] and discuss each step taken to sort the array in ascending order.

Quick Sort

In the implementation of this example, the last element of the array is chosen as the pivot element. At the start of the partition process, variables i and j are created which are the same initially. As the partition progresses the value of i and j becomes different. i signifies the boundary between elements less than the pivot and elements greater than pivot. j signifies the boundary between elements greater than pivot and unpartitioned array.

Quick Sort Diagram

After partition, it generates two partition with left side partition contains elements less than pivot and right side partition contains elements greater than pivot. The both partition are again partitioned with the same logic and this process continues till a partition has zero or one element. The final outcome of this process will be a sorted array.

Implementation of Quick Sort



# function for quick sort which calls partition function 
# to arrange and split the list based on pivot element
# quicksort is a recursive function
def quicksort(MyList, left, right):
  if left < right:
    pivot = partition(MyList, left, right)
    quicksort(MyList, left, pivot-1)
    quicksort(MyList, pivot+1, right)   

# partition function arrange and split the list 
# into two list based on pivot element
# In this example, last element of list is chosen 
# as pivot element
# one list contains all elements less than the pivot element
# another list contains all elements greater than the pivot element
def partition(MyList, left, right):
  i = left
  pivot = MyList[right]
  for j in range(left, right):
    if(MyList[j] < pivot):
      MyList[i], MyList[j] = MyList[j], MyList[i]
      i = i + 1
  MyList[i], MyList[right] = MyList[right], MyList[i]
  return i

# test quick sort code                 
MyList = [-4, 1, 25, 50, 8, 10, 23]
n = len(MyList)
print("Original List")
for i in MyList:
  print(i, end=" ")
print("\n")

quicksort(MyList, 0, n-1)
print("Sorted List")
for i in MyList:
  print(i, end=" ")

Output

Original List
-4 1 25 50 8 10 23 

Sorted List
-4 1 8 10 23 25 50 



public class MyClass {
  // function for quick sort which calls partition function 
  // to arrange and split the list based on pivot element
  // quicksort is a recursive function
  static void quicksort(int Array[], int left, int right) 
  {
    if (left < right)
    { 
      int pivot = partition(Array, left, right);
      quicksort(Array, left, pivot-1);
      quicksort(Array, pivot+1, right);
    }
  }

  // partition function arrange and split the array
  // into two array based on pivot element
  // In this example, last element of array is chosen 
  // as pivot element
  // one array contains all elements less than the pivot element
  // another array contains all elements greater than the pivot element
  static int partition(int Array[], int left, int right) 
  {
    int i = left;
    int pivot = Array[right];
    int temp;
    for(int j = left; j <=right; j++)
    {
      if(Array[j] < pivot)
      {
        temp = Array[i];
        Array[i] = Array[j];
        Array[j] = temp;
        i++;
      }
    }
    temp = Array[right];
    Array[right] = Array[i];
    Array[i] = temp;
    return i;
  }

  // function to print array
  static void PrintArray(int Array[]) 
  { 
    int n = Array.length; 
    for (int i=0; i<n; i++) 
    {  
      System.out.print(Array[i] + " "); 
    }
    System.out.println(); 
  } 

  // test quick sort code
  public static void main(String[] args) {
    int[] MyArray = {-4, 1, 25, 50, 8, 10, 23};
    int n = MyArray.length;
    System.out.println("Original Array");
    PrintArray(MyArray);

    quicksort(MyArray, 0, n-1);
    System.out.println("\nSorted Array");
    PrintArray(MyArray); 
  }
}

Output

Original Array
-4 1 25 50 8 10 23 

Sorted Array
-4 1 8 10 23 25 50  



#include <iostream>
using namespace std;

static void quicksort(int Array[], int left, int right);
static int partition(int Array[], int left, int right);
static void PrintArray(int Array[], int n);

  // function for quick sort which calls partition function 
  // to arrange and split the list based on pivot element
  // quicksort is a recursive function
  static void quicksort(int Array[], int left, int right) 
  {
    if (left < right)
    { 
      int pivot = partition(Array, left, right);
      quicksort(Array, left, pivot-1);
      quicksort(Array, pivot+1, right);
    }
  }

  // partition function arrange and split the array
  // into two array based on pivot element
  // In this example, last element of array is chosen 
  // as pivot element
  // one array contains all elements less than the pivot element
  // another array contains all elements greater than the pivot element
  static int partition(int Array[], int left, int right) 
  {
    int i = left;
    int pivot = Array[right];
    int temp;
    for(int j = left; j <=right; j++)
    {
      if(Array[j] < pivot)
      {
        temp = Array[i];
        Array[i] = Array[j];
        Array[j] = temp;
        i++;
      }
    }
    temp = Array[right];
    Array[right] = Array[i];
    Array[i] = temp;
    return i;
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
      {  
        cout<<Array[i]<<" "; 
      }
    cout<<"\n"; 
  } 

 //  test quick sort code
 int main (){
    int MyArray[] = {-4, 1, 25, 50, 8, 10, 23};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    cout<<"Original Array\n";
    PrintArray(MyArray, n);

    quicksort(MyArray, 0, n-1);
    cout<<"\nSorted Array\n";
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
-4 1 25 50 8 10 23 

Sorted Array
-4 1 8 10 23 25 50  



#include <stdio.h>

static void quicksort(int Array[], int left, int right);
static int partition(int Array[], int left, int right);
static void PrintArray(int Array[], int n);

  // function for quick sort which calls partition function 
  // to arrange and split the list based on pivot element
  // quicksort is a recursive function
  static void quicksort(int Array[], int left, int right) 
  {
    if (left < right)
    { 
      int pivot = partition(Array, left, right);
      quicksort(Array, left, pivot-1);
      quicksort(Array, pivot+1, right);
    }
  }

  // partition function arrange and split the array
  // into two array based on pivot element
  // In this example, last element of array is chosen 
  // as pivot element
  // one array contains all elements less than the pivot element
  // another array contains all elements greater than the pivot element
  static int partition(int Array[], int left, int right) 
  {
    int i = left;
    int pivot = Array[right];
    int temp;
    for(int j = left; j <=right; j++)
    {
      if(Array[j] < pivot)
      {
        temp = Array[i];
        Array[i] = Array[j];
        Array[j] = temp;
        i++;
      }
    }
    temp = Array[right];
    Array[right] = Array[i];
    Array[i] = temp;
    return i;
  }

  // function to print array
  static void PrintArray(int Array[], int n) 
  { 
    for (int i=0; i<n; i++) 
    {  
      printf("%i ",Array[i]); 
    }
    printf("\n"); 
  } 

 //  test quick sort code
 int main (){
    int MyArray[] = {-4, 1, 25, 50, 8, 10, 23};
    int n = sizeof(MyArray) / sizeof(MyArray[0]); 
    printf("Original Array\n");
    PrintArray(MyArray, n);

    quicksort(MyArray, 0, n-1);
    printf("\nSorted Array\n");
    PrintArray(MyArray, n);
    return 0;
 }

Output

Original Array
-4 1 25 50 8 10 23 

Sorted Array
-4 1 8 10 23 25 50 



using System;

namespace MyApplication { 
   class MyProgram {
  // function for quick sort which calls partition function 
  // to arrange and split the list based on pivot element
  // quicksort is a recursive function
  static void quicksort(int[] Array, int left, int right) 
  {
    if (left < right)
    { 
      int pivot = partition(Array, left, right);
      quicksort(Array, left, pivot-1);
      quicksort(Array, pivot+1, right);
    }
  }

  // partition function arrange and split the array
  // into two array based on pivot element
  // In this example, last element of array is chosen 
  // as pivot element
  // one array contains all elements less than the pivot element
  // another array contains all elements greater than the pivot element
  static int partition(int[] Array, int left, int right) 
  {
    int i = left;
    int pivot = Array[right];
    int temp;
    for(int j = left; j <=right; j++)
    {
      if(Array[j] < pivot)
      {
        temp = Array[i];
        Array[i] = Array[j];
        Array[j] = temp;
        i++;
      }
    }
    temp = Array[right];
    Array[right] = Array[i];
    Array[i] = temp;
    return i;
  }
       
  // function to print array
   static void PrintArray(int[] Array) 
   { 
      int n = Array.Length; 
      for (int i=0; i<n; i++) 
      {  
        Console.Write(Array[i] + " "); 
      }
      Console.Write("\n"); 
   } 

  // test quick sort code
  static void Main(string[] args) {
   int[] MyArray = {-4, 1, 25, 50, 8, 10, 23};
   int n = MyArray.Length;
   Console.Write("Original Array\n");
   PrintArray(MyArray);

   quicksort(MyArray, 0, n-1);
   Console.Write("\nSorted Array\n");
   PrintArray(MyArray);  
  }
 }
}

Output

Original Array
-4 1 25 50 8 10 23 

Sorted Array
-4 1 8 10 23 25 50 

Time Complexity:

The time complexity of quick sort is O(N²) in worst case and the time complexity in best and average cases are O(NLogN).


Previous Page Next Page