Sorting Algorithms - #4 Quick Sort
Tags: programming, beginners, computerscience, webdev
Published: 2022-02-02 09:41:37

hi👋Devs,

_In the previous one we have learned about the [**Merge Sort**](https://dev.to/sachin26/sorting-algorithms-3-merge-sort-1eog) 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l4zu2zzkyiyxycckdvjr.png)


**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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qwrsdkvzomju59266l2g.png)

**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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/9ux7q83b7knc7xdg7klv.png)

> 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/8rz7vqlxwawvw1eqq3e1.png)

**2.** divide the array into sub-arrays using `pivotIndex`.
   > quickSort(arr, start, point-1)
   > quickSort(arr, point+1, end)


![quick sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/x1haoy2b9p6mghpeun2p.png)


**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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dvf0koo4vqsd6cjezkvm.png)


**step-2** run a loop while `start < end` and then,
  > **1.** initialise `i` & `j` variables.
         i = start
         j = end

![quick sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q6bvvfchmj6kj7l96pru.png)

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

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


![quick sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sbhkvki966at6vsewx8k.png)

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

![quick sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/zwvavj6c7pc9dhpu0xd0.png)

**step-3** swap pivot element with `jth` element.

![quick sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/wq0kf5jtyzf8eow4puzv.png)

![quick sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/umpm50bwqdowxowqrkr7.png)

**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

```java
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;
	}

}
		
```
  

---

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.