Quiz Comment Box

Sorts

Quick Sort

Quick sortQuicksort is a divide and conquer algorithm. It first divides the input array into two smaller sub-arrays: the low elements and the high elements. It then recursively sorts the sub-arrays.

Example :

Algorithm - Quick sort

                       
 Algorithm Quicksort [A (0..n-1)]
 
    // Sort a given array by Quick sort.
    // Input : An array A(0,n-1) of orderable elements.
    // Output : Array A [0,n-1] sorted in non- decreasing order .
    
    if low < high then
        p := partition(A, low, high)
        quicksort(A, low, p - 1)
        quicksort(A, p + 1, high)

Algorithm partition(A, low, high)
    pivot := A[high]
    i := lo
    for j := low to high do
        if A[j] < pivot then
            swap A[i] with A[j]
            i := i + 1
    swap A[i] with A[hi]
    return i


                                                     
                             
                

Following are the implementation of Quick sort into programs

                        
#include< stdio.h>
void quicksort(int number[25],int first,int last){
   int i, j, pivot, temp;
   if(first< last){
      pivot=first;
      i=first;
      j=last;
      while(i< j){
         while(number[i]<=number[pivot]&&i< last)
         i++;
         while(number[j] >number[pivot])
         j--;
         if(i< j){
            temp=number[i];
            number[i]=number[j];
            number[j]=temp;
         }
      }
      temp=number[pivot];
      number[pivot]=number[j];
      number[j]=temp;
      quicksort(number,first,j-1);
      quicksort(number,j+1,last);
   }
}
int main(){
   int i, count, number[25];
   printf("How many elements are u going to enter?: ");
   scanf("%d",&count);
   printf("Enter %d elements: ", count);
   for(i=0;i< count;i++)
   scanf("%d",&number[i]);
   quicksort(number,0,count-1);
   printf("Order of Sorted elements: ");
   for(i=0;i< count;i++)
   printf(" %d",number[i]);
   return 0;
}

       
                        
                         Code 
                    
                        
import java.util.*;
class QuickSort { 
    //selects last element as pivot, pi using which array is partitioned. 
    int partition(int intArray[], int low, int high) { 
        int pi = intArray[high];  
        int i = (low-1); // smaller element index   
        for (int j=low; j< high; j++) { 
            // check if current element is less than or equal to pi 
            if (intArray[j] <= pi) { 
                i++; 
                // swap intArray[i] and intArray[j] 
                int temp = intArray[i]; 
                intArray[i] = intArray[j]; 
                intArray[j] = temp; 
            } 
        } 
        // swap intArray[i+1] and intArray[high] (or pi) 
        int temp = intArray[i+1]; 
        intArray[i+1] = intArray[high]; 
        intArray[high] = temp; 
        return i+1; 
    } 
  //routine to sort the array partitions recursively
    void quick_sort(int intArray[], int low, int high) { 
        if (low < high) { 
            //partition the array around pi=>partitioning index and return pi
            int pi = partition(intArray, low, high); 
  
            // sort each partition recursively 
            quick_sort(intArray, low, pi-1); 
            quick_sort(intArray, pi+1, high); 
        } 
    } 
}
class Main{
    public static void main(String args[]) {
        //initialize a numeric array, intArray
        int intArray[] = {4,-1,6,8,0,5,-3}; 
        int n = intArray.length; 
        //print the original array
        System.out.println("Original Array: " + Arrays.toString(intArray));
        //call quick_sort routine using QuickSort object
        QuickSort obj = new QuickSort(); 
        obj.quick_sort(intArray, 0, n-1); 
        //print the sorted array
        System.out.println("\nSorted Array: " + Arrays.toString(intArray)); 
    } 
}


    
                        
                         Code 
                    
                        
# divide function
def partition(arr,low,high):
   i = ( low-1 )
   pivot = arr[high] # pivot element
   for j in range(low , high):
      # If current element is smaller
      if arr[j] <= pivot:
         # increment
         i = i+1
         arr[i],arr[j] = arr[j],arr[i]
   arr[i+1],arr[high] = arr[high],arr[i+1]
   return ( i+1 )
# sort
def quickSort(arr,low,high):
   if low < high:
      # index
      pi = partition(arr,low,high)
      # sort the partitions
      quickSort(arr, low, pi-1)
      quickSort(arr, pi+1, high)
# main
arr = [2,5,3,8,6,5,4,7]
n = len(arr)
quickSort(arr,0,n-1)
print ("Sorted array is:")
for i in range(n):
   print (arr[i],end=" ")



                        
                         Code 
                    

Sample Output

Before sorting array

5 3 2 5 8 7 6

Sorted array is

2 3 4 5 5 6 7 8

Time Complexity

best case, average case, worst case

Visualized

Note: For better Visualized Understanding visit our algorithm Visualizer

Visualize
Previous

Shell sort