Quicksort is based on a divide and conquer approach like merge sort. In quick sort, we divide the array into two parts such that one part is lesser than some specific number (known as pivot element) and another part is greater than pivot till each part contains a single element. In quick sort, we use the partition method to decide how to partition the array into two parts. The partition method gives us the index of the pivot element then we call the quick sort recursively on each part. Note pivot element is not included in any part, this is how the arrays start getting sorted from the pivot element.
Partition Method approach: Partition method takes three argument, pointer to an array, start and last index of array, and it places the pivot element into appropriate place such that the element present before pivot is lesser and equal to pivot element and elements places after pivot are greater than pivot, the it returns the index of pivot element.
Here is an example of working of quick sort:
Here is Quick sort implemetation in golang:
package main
import "fmt"
func Quick_sort(A *[]int ,p int, r int){
if p<r{
pivot_pos:=Partition(A,p,r)
fmt.Printf("pivot_pos is returned :%d\n",pivot_pos)
PrintArr(A)
Quick_sort(A, p ,pivot_pos-1)
Quick_sort(A, pivot_pos+1,r)
}
}func Partition(A *[]int, start int,last int)(j int){
// let's take last element as pivot
pivot:=(*A)[last]
j=start-1
for i:=start;i<(last);i++{
/*if (*A)[i]<=pivot then increment j and swap(*A)[j] with (*A)[i]*/
if (*A)[i]<=pivot{
j++
(*A)[j], (*A)[i] = (*A)[i], (*A)[j]
}
}
j++
(*A)[j],(*A)[last] = pivot, (*A)[j]
return j
}
func PrintArr(A *[] int){
for i:=0; i<len(*A);i++{
fmt.Printf("A[%d]:%d\n", i ,(*A)[i])
}
}
func main(){
A:=[]int{8,4,3,1,6,7,11,9,2,10,5}
Quick_sort(&A,0,10)
fmt.Println("Array After Quick Sort Algorithm---->")
PrintArr(&A)
}
Time Complexity of Quick Sort:
Average Case: θ(nlogn), as partition takes O(n) and partition is called log(n) times if array is partitioned into two almost equal parts.
Worst Case: O(n²), When given array is either sorted or unsorted, and last element or first element is chosen as pivot then one partition contains no elements and another contains (n-1) elements, In this case quick sort behaves like insertion sort. To overcome this, before applying quick sort, we can randomly select any element as pivot instead of chosing last element as pivot.
Space complexity of Quick sort is O(1).
