DEV Community

Cover image for Sorting Algorithms - #4 Quick Sort
sachin26
sachin26

Posted on

Sorting Algorithms - #4 Quick Sort

hi👋Devs,

In the previous one we have learned about the Merge Sort algorithm and in this article, we will discuss the QuickSort algorithm, how its work, time & space complexities and pros & cons.

Quick Sort

Quick Sort algorithm is an in-place sorting algorithm means this algo doesn't require any extra space except temp variables, to perform sorting.
This algo is also based on the divide and conquer approach.

lets understand how quick sort work.

step-1 select a pivot element.
you can choose any element as a pivot from the array

  • first element
  • last element
  • any random element

lets say i choose the first element of the array as pivot

quick sort algorithm

step-2 place the pivot element in its right position.
now in this step we have to place the pivot element to its right position but we have to rearrange the array in such a way that

  • put all smaller elements (which are less than pivot) before pivot element.
  • put all greater elements (which are greater than pivot) after the pivot element.

we also called this step as a partition logic.

quick sort

step-3 divide the array into sub-array.
divide the array into the left sub-array and sub-right array based on the pivot point and apply the same approach for the sub-arrays until sub array size becomes 1

quick sort

implementation

now understand how we can implement this algo pragmatically

Pseudocode for quickSort( arr, start, end)

1. find the pivot index pivotIndex by using partition logic.

pivotIndex = partition( arr, start, end)

quick sort

2. divide the array into sub-arrays using pivotIndex.

quickSort(arr, start, point-1)
quickSort(arr, point+1, end)

quick sort

3. repeat these steps until the sub-array size becomes 1.

Pseudocode for partition( arr, start, end)

step-1 make first element as pivot.

pivot = arr[first]

quick sort

step-2 run a loop while start < end and then,

1. initialise i & j variables.
i = start
j = end

quick sort

2. linearly increase the i while pivot > arr[i]

3. linearly decrease the j while pivot < arr[j]

quick sort

4. swap ith element with jth element ,if i < j

quick sort

step-3 swap pivot element with jth element.

quick sort

quick sort

step-4 return the right pivot index position j

Time & Space Complexity

in average case the time complexity will be nLogn.
this algo does not require any extra space so , the space complexity is O(1).

Pros & Cons

  • it does not require extra memory.
  • pretty fast & efficient in most cases.
  • the worst-case complexity is n^2.
  • use recursion.

Java Implementation

import java.util.Arrays;

class Main{
    public static void main(String[] args){
        int[] arr = new int[] {3,12,90,2,5,16,25,44,70,0};
        System.out.println("unsorted array: "+Arrays.toString(arr));
        qSort(arr,0,9);
        System.out.println("sorted array: "+Arrays.toString(arr));
    }

    private static void qSort(int[] arr,int start,int end){
        if(start < end){

        int p = partition(arr,start,end);
        qSort(arr,start,p-1);
        qSort(arr,p+1,end);
        }
    }

    private static int partition(int[] arr,int s,int e){
        int pivot = arr[s];
                int i = s;
        int j = e;
        while(i < j){

            while(arr[i]<=pivot && i<e) i++;
            while( arr[j]>pivot && j>s ) j--;

            if(i < j)
            swap(arr,i,j);
        }

        swap(arr,s,j);

        return j;

    }

    private static void swap(int[] arr,int i, int j){
        int t = arr[i];
         arr[i] = arr[j];
         arr[j] = t;
    }

}

Enter fullscreen mode Exit fullscreen mode

Thank you for reading this article. save it and share it with your dev friends. if you find any errors let me know in the comment section.

Discussion (0)