Algorithms

Algorithms

Quick Sort

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

# function to print list
def PrintList(MyList):
  for i in MyList:
    print(i, end=" ")
  print("\n")
  
# test the code                 
MyList = [-4, 1, 25, 50, 8, 10, 23]
n = len(MyList)
print("Original List")
PrintList(MyList)

quicksort(MyList, 0, n-1)
print("Sorted List")
PrintList(MyList)

The above code will give the following 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 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
  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 the 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); 
  }
}

The above code will give the following 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 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
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 the 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;
}

The above code will give the following 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 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
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 the 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;
}

The above code will give the following output:

Original Array
-4 1 25 50 8 10 23 

Sorted Array
-4 1 8 10 23 25 50

using System;

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 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
  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 the 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);  
  }
}

The above code will give the following output:

Original Array
-4 1 25 50 8 10 23 

Sorted Array
-4 1 8 10 23 25 50

<?php
// function for quick sort which calls partition function 
// to arrange and split the list based on pivot element
// quicksort is a recursive function
function quicksort(&$Array, $left, $right) {
  if ($left < $right) { 
    $pivot = partition($Array, $left, $right);
    quicksort($Array, $left, $pivot-1);
    quicksort($Array, $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
function partition(&$Array, $left, $right) {
  $i = $left;
  $pivot = $Array[$right];

  for($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
function PrintArray($Array, $n) { 
  for ($i = 0; $i < $n; $i++) 
    echo $Array[$i]." "; 
  echo "\n"; 
} 

// test the code
$MyArray = array(-4, 1, 25, 50, 8, 10, 23);
$n = sizeof($MyArray); 
echo "Original Array\n";
PrintArray($MyArray, $n);

quicksort($MyArray, 0, $n-1);
echo "\nSorted Array\n";
PrintArray($MyArray, $n);
?>

The above code will give the following 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 Θ(N²) in worst case and the time complexity in best and average cases are Θ(NlogN).

AlphaCodingSkills

AlphaCodingSkills Android App

AlphaCodingSkills is a online learning portal that provides tutorials on Python, Java, C++, C, C#, PHP, R, Ruby, Rust, Scala, Swift, Perl, SQL, Data Structures and Algorithms. Tutorials, examples, references and content of the website are reviewed and simplified continuously to improve comprehensibility and eliminate any possible error. We use cookies to ensure best browsing experience on our website. While using this website, you acknowledge to have read and accepted our cookie and privacy policy.