Quicksort in Data Structure

Suppose you ran out of groceries. You run to a grocery store with a list of items with their priority numbers written alongside.

For a small list, you can just see and find out the order but for a list of more than 100 items, you need to sort the list according to priority. The fastest way to do that is to select any item in the list and arrange the remaining items above or below it by comparing their priorities.

This is how quicksort works. Quicksort is the fastest sorting algorithm, based on the divide and conquer technique.

Quicksort in Data Structure

Just like merge sort, quick sort is also based on the divide and conquer technique. The dataset is divided into sub-datasets and items are arranged around a pivot element. There are many ways a pivot element is selected:

• By Choosing the first element as the pivot element
• Or By Choosing the last element as the pivot element
• Or Choose a random element as the pivot element
• Choose the median as the pivot element

Quick Sort Procedure

• Choose a pivot element. Arrange the elements smaller than the pivot before it and elements larger than the pivot after it.
• Repeat this process recursively, every time choosing pivot from each sub-array
• Combine the final sorted subarrays.

Quick Sort Algorithm

QUICKSORT (array A, int x, int y)   
 Step 1:  if (y > x)   then   
              i ← a random index from [x,y]   
 Step 2: swap A [i] with A[x]   
 Step 3: j ← COMBINE (A, x, y)   
 Step 4: QUICKSORT (A, x, j - 1)  
              QUICKSORT (A, j + 1, y)  
COMBINE (array Ar, int m, int n)   
 Step 5: x ← Ar[m]   
             o ← m   
 Step 6: repeat for p ← m + 1 to n  
              do if (Ar[p] < x)   
                    then o ← o + 1   
               swap Ar[o] with Ar[p]  
               swap Ar[m] with Ar[o]   
             [end of for]
  return o

Quicksort Pseudocode

function combineFunc(low, high, pivot)
   lowPointer = low
   highPointer = high - 1

   while True do
      while A[++lowPointer] < pivot do
                    
      end while
    
      while highPointer > 0 && A[--highPointer] > pivot do
                 
      end while
    
      if lowPointer >= highPointer
         break
      else                
         swap lowPointer,highPointer
      end if
    
   end while 
  
   swap lowPointer,high
   return lowPointer
  
end function

Working of quicksort

Let’s sort the characters in the word “DATAFLAIR” by the bubble sort technique.

Let us select the middle element as the pivot element every time.

Iteration 1:

Iteration 2: Swap pivot with the last element

Iteration 3:

Iteration 4

Iteration 5

Iteration 6

Iteration 7

Iteration 8

Iteration 9

Iteration 10

Iteration 11

Iteration 12

Iteration 13

Array implementation in C

#include <stdio.h>

void swap(int *x, int *y) 
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

int partition(int arr[], int low, int high) 
{
  int pivot = arr[high];
  int i = (low - 1);
  for (int j = low; j < high; j++) 
  {
    if (arr[j] <= pivot) 
    {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return (i + 1);
}

void quickSort(int array[], int low, int high) 
{
  if (low < high) 
  {
    int piv = partition(array, low, high);
    quickSort(array, low, piv - 1);
    quickSort(array, piv + 1, high);
  }
}

int main() 
{
  int dataset[] = {81, 75, 22, 15, 4, 98, 62, 38,49,51};
  
  int size = sizeof(dataset) / sizeof(dataset[0]);
  quickSort(dataset, 0, size - 1);
  
  printf("Sorted array \n");
  for (int i = 0; i < size; ++i)
  {
    printf("%d ", dataset[i]);
  }
}

Quick Sort Array implementation in C++

#include <iostream>
using namespace std;
void swap(int *x, int *y) 
{
  int temp = *x;
  *x = *y;
  *y = temp;
}

int partition(int arr[], int low, int high) 
{
  int pivot = arr[high];
  int i = (low - 1);
  for (int j = low; j < high; j++) 
  {
    if (arr[j] <= pivot) 
    {
      i++;
      swap(&arr[i], &arr[j]);
    }
  }
  swap(&arr[i + 1], &arr[high]);
  return (i + 1);
}

void quickSort(int array[], int low, int high) 
{
  if (low < high) 
  {
    int piv = partition(array, low, high);
    quickSort(array, low, piv - 1);
    quickSort(array, piv + 1, high);
  }
}

int main() 
{
  int dataset[] = {81, 75, 22, 15, 4, 98, 62, 38,49,51};
  
  int size = sizeof(dataset) / sizeof(dataset[0]);
  quickSort(dataset, 0, size - 1);
  
  cout << "Sorted array" ;
  for (int i = 0; i < size; ++i)
  {
    cout << " " <<dataset[i];
  }
}

Array implementation of Quick Sort in Java

public class Quicksort 
{
  static int partition(int arr[], int low, int high) 
  {
    int piv = arr[high];
    int i = (low - 1);
    for (int j = low; j < high; j++) 
    {
      if (arr[j] <= piv) 
      {
        i++;
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
      }

    }
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return (i + 1);
  }

  static void quickSort(int arr[], int low, int high) 
  {
    if (low < high) 
    {
      int piv = partition(arr, low, high);
      quickSort(arr, low, piv - 1);
      quickSort(arr, piv + 1, high);
    }
  }
  public static void main(String args[]) 
  {

    int data[] = { 81, 75, 22, 15, 4, 98, 62, 38,49,51 };

    int size = data.length;
    Quicksort.quickSort(data, 0, size - 1);

    System.out.println("Sorted Array in Ascending Order: ");
    for(int i=0;i<size;i++)
    System.out.print(data[i]+" ");
  }
}

Quick Sort Array implementation in Python

def partition(arr, low, high):
  piv = arr[high]
  i = low - 1
  
  for j in range(low, high):
      
    if arr[j] <= piv:
        
      i = i + 1
      (arr[i], arr[j]) = (arr[j], arr[i])
      
      
  (arr[i + 1], arr[high]) = (arr[high], arr[i + 1])
  return i + 1

def quickSort(arr, low, high):
  
  if low < high:
      
    piv = partition(arr, low, high)
    quickSort(arr, low, piv - 1)
    quickSort(arr, piv + 1, high)


data = [81, 75, 22, 15, 4, 98, 62, 38,49,51]
size = len(data)

quickSort(data, 0, size - 1)

print('Sorted Array:')
print(data)

Linked list implementation in C++

#include <cstdio>
#include <iostream>
using namespace std;

struct Node 
{
  int data;
  struct Node* next;
};

void push(struct Node** head, int newData)
{
  struct Node* newNode = new Node;

  newNode->data = newData;

  newNode->next = (*head);

  (*head) = newNode;
}

struct Node* getTail(struct Node* current)
{
  while (current != NULL && current->next != NULL)
    current = current->next;
  return current;
}

struct Node* partition(struct Node* head, struct Node* end,struct Node** Head,struct Node** newEnd)
{
  struct Node* pivot = end;
  struct Node *previous = NULL, *current = head, *tail = pivot;

  while (current != pivot) {
    if (current->data < pivot->data) 
    {
      if ((*Head) == NULL)
        (*Head) = current;

      previous = current;
      current = current->next;
    }
    else 
    {
        
      if (previous)
        previous->next = current->next;
      struct Node* temp = current->next;
      current->next = NULL;
      tail->next = current;
      tail = current;
      current = temp;
    }
  }

  if ((*Head) == NULL)
    (*Head) = pivot;

  (*newEnd) = tail;

  return pivot;
}

struct Node* quickSortRecursive(struct Node* head,struct Node* end)
{
  if (!head || head == end)
    return head;

  Node *newHead = NULL, *newEnd = NULL;

  struct Node* pivot = partition(head, end, &newHead, &newEnd);

  if (newHead != pivot) 
  {
    struct Node* tmp = newHead;
    while (tmp->next != pivot)
      tmp = tmp->next;
    tmp->next = NULL;

    newHead = quickSortRecursive(newHead, tmp);

    tmp = getTail(newHead);
    tmp->next = pivot;
  }

  pivot->next = quickSortRecursive(pivot->next, newEnd);

  return newHead;
}

void quickSort(struct Node** headRef)
{
  (*headRef) = quickSortRecursive(*headRef, getTail(*headRef));
  return;
}

int main()
{
  struct Node* a = NULL;
  push(&a, 81);
  push(&a, 75);
  push(&a, 22);
  push(&a, 15);
  push(&a, 4);
  push(&a, 98);
  push(&a, 62);
  push(&a, 38);
  push(&a, 49);
  push(&a, 51);

  quickSort(&a);

  cout << "sorted list: ";
  while (a != NULL) 
  {
    cout <<" ”<<a->data;
    a = a->next;
  }

  return 0;
}

Quick Sort Linked List Implementation in Java

public class QuickSortLinkedList 
{
    static class Node 
    {
        int data;
        Node next;
 
        Node(int d)
        {
            this.data = d;
            this.next = null;
        }
    }
 
    Node head;
 
    void addNode(int data)
    {
        if (head == null) {
            head = new Node(data);
            return;
        }
 
        Node current = head;
        while (current.next != null)
            current = current.next;
 
        Node newNode = new Node(data);
        current.next = newNode;
    }
 
    void printList(Node n)
    {
        while (n != null) {
            System.out.print(n.data);
            System.out.print(" ");
            n = n.next;
        }
    }
 
    Node paritionLast(Node start, Node end)
    {
        if (start == end || start == null || end == null)
            return start;
 
        Node pivot_prev = start;
        Node current = start;
        int pivot = end.data;
 
        while (start != end) 
        {
            if (start.data < pivot) 
            {
                pivot_prev = current;
                int temp = current.data;
                current.data = start.data;
                start.data = temp;
                current = current.next;
            }
            start = start.next;
        }
 
        int temp = current.data;
        current.data = pivot;
        end.data = temp;
 
        return pivot_prev;
    }
 
    void sort(Node start, Node end)
    {
        if(start == null || start == end|| start == end.next )
            return;
 
        Node pivot_prev = paritionLast(start, end);
        sort(start, pivot_prev);
 
        if (pivot_prev != null && pivot_prev == start)
            sort(pivot_prev.next, end);

        else if (pivot_prev != null
                 && pivot_prev.next != null)
            sort(pivot_prev.next.next, end);
    }
 
public static void main(String[] args)
    {
        QuickSortLinkedList list
            = new QuickSortLinkedList();
        list.addNode(81);
        list.addNode(75);
        list.addNode(22);
        list.addNode(15);
        list.addNode(4);
        list.addNode(98);
        list.addNode(62);
        list.addNode(38);
        list.addNode(49);
        list.addNode(51);
 
        Node n = list.head;
        while (n.next != null)
            n = n.next;
 
        list.sort(list.head, n);
 
        System.out.println("sorted list");
        list.printList(list.head);
    }
}

Linked list implementation in Python

class Node:
  def __init__(self, val):
    self.data = val
    self.next = None

class QuickSortList:

  def __init__(self):
    self.head=None

  def addNode(self,data):
    if (self.head == None):
      self.head = Node(data)
      return

    current = self.head
    while (current.next != None):
      current = current.next

    newNode = Node(data)
    current.next = newNode

  def printList(self,n):
    while (n != None):
      print(n.data, end=" ")
      n = n.next
      
  def paritionLast(self,start, end):
    if (start == end or start == None or end == None):
      return start

    pivot_prev = start
    current = start
    pivot = end.data

    while (start != end):
      if (start.data < pivot):
      
        pivot_prev = current
        temp = current.data
        current.data = start.data
        start.data = temp
        current = current.next
      start = start.next

    temp = current.data
    current.data = pivot
    end.data = temp

    return pivot_prev

  def sort(self, start, end):
    if(start == None or start == end or start == end.next):
      return

    pivot_prev = self.paritionLast(start, end)
    self.sort(start, pivot_prev)

    if(pivot_prev != None and pivot_prev == start):
      self.sort(pivot_prev.next, end)

    elif (pivot_prev != None and pivot_prev.next != None):
      self.sort(pivot_prev.next.next, end)

if __name__ == "__main__":
  ll = QuickSortList()
  ll.addNode(81)
  ll.addNode(75)
  ll.addNode(22)
  ll.addNode(15)
  ll.addNode(4)
  ll.addNode(98)
  ll.addNode(62)
  ll.addNode(38)
  ll.addNode(49)
  ll.addNode(51)

  n = ll.head
  while (n.next != None):
    n = n.next

  ll.sort(ll.head, n)

  print("sorted list: ");
  ll.printList(ll.head)

Complexity of Quick Sort

Best Case Complexity:

When the pivot element is the middle element or near to the middle element.

Worst Case Complexity:

when pivot element is either largest or smallest number.

Average Case Complexity:

when the condition of best and worst-case, both don’t occur.

Advantages of Quicksort

• Quicksort does not require any extra memory, unlike merge sort. This makes Quicksort faster since it does not require allocation and deallocation of memory.
• Less time and space complexity.
• Most implementation is in randomized order and quick sort works better for randomized version.

Disadvantages of Quicksort

• Merge sort can be implemented without extra memory in a linked list. Therefore, merge sort is preferred over quick sort
• Quicksort requires random access of elements which is not possible in a linked list. For these reasons, quicksort is not preferable in a linked list.

Applications of Quicksort in Data Structure

• Used for sorting in commercial computing since it is the fastest.
• Most algorithms that are efficiently developed, use priority queues. This makes the implementation of quicksort easy.
• Quicksort is a cache-friendly algorithm.
• It is used in event-driven simulations and to implement primitive type methods

Conclusion

Quicksort is the fastest sorting algorithm. Based on the Divide and Conquer algorithm technique, quick sort uses priority queues for sorting. Quicksort is also used as a better search technique.

Quicksort, when implemented efficiently can beat most of the sorting algorithms including heap sort and merge sort.