Skip to content

Instantly share code, notes, and snippets.

@schadokar
Created March 3, 2020 05:32
Show Gist options
  • Save schadokar/354a4a1114b29a83f633c5c8424145e0 to your computer and use it in GitHub Desktop.
Save schadokar/354a4a1114b29a83f633c5c8424145e0 to your computer and use it in GitHub Desktop.
Quicksort Implementation in golang
/**
* ********************************** Quick Sort ***********************************************
* UNSORTED ARRAY [3, 7, 8, 5, 2, 1, 9, 6, 4]
* pivot ^
* pivot: 3 arr: [ 2, 1, 3, 5, 8, 7, 9, 6, 4 ]
* [2, 1] [5, 8, 7, 9, 6, 4 ]
* pivot ^ ^
* pivot: 2 arr: [ 1, 2 ]
* pivot: 5 arr: [ 4, 5, 7, 9, 6, 8 ]
* [ 4] [7, 9, 6, 8 ] --> Array with single element is sorted
* pivot ^
* pivot: 7 arr: [ 6, 7, 9, 8 ]
* [ 6] [9, 8 ]
* pivot ^
* pivot: 9 arr: [ 8, 9 ]
*
* SORTED ARRAY [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
* *********************************************************************************************
*
* Worst-case Performance: O(n^2)
* Best-cae Performance: O(n log n)
* Average Performance: O(n log n)
*
* ********************************** Quick Sort ***********************************************
*/
// playground https://play.golang.org/p/SgQRJNt7eyM
package main
import (
"fmt"
)
func main() {
arr := []int{3, 7, 8, 5, 2, 1, 9, 6, 4}
fmt.Printf("Sorted Array - %v", quicksort(arr))
}
func quicksort(arr []int) []int {
// return the array if array length is 1 or less than 1
if len(arr) <= 1 {
return arr
}
// make the first element as pivot
pivot := arr[0]
// i will move in right direction (away from pivot) from index position 1
i := 1
// j will move in left direction (towards pivot) from the last element of the array
j := len(arr) - 1
// iterate till i and j are not passed each other
for i < j {
// find the value which is larger than pivot
for (arr[i] < pivot) && (i < len(arr)) {
i++
}
// find the value which is lesser than pivot
for (arr[j] > pivot) && j > 0 {
j--
}
// if i is less than j
// swap the value at i and j index
// swap the larger value at i with lesser value at j
if i < j {
arr[i], arr[j] = arr[j], arr[i]
}
}
// Swap the value at j with pivot
// j index is the sorted position of the pivot
// everything to its left is lesser and larger to its right.
arr[j], arr[0] = arr[0], arr[j]
fmt.Printf("pivot: %v, arr: %v\n", pivot, arr)
// left side of the pivot will be a new subarray
left := arr[:j]
// if the length of the subarray is greater than 1
// then quicksort the subarray
if len(left) > 1 {
left = quicksort(left)
}
// right side of the pivot will be a new subarray
right := arr[j+1:]
// if the length of the subarray is greater than 1
// then quicksort the subarray
if len(right) > 1 {
right = quicksort(right)
}
// concat all the elements of the array
// left pivot and right
// return the sorted array
left = append(left, pivot)
return append(left, right...)
}
/**
* OUTPUT
*
* pivot: 3, arr: [ 2 1 3 5 8 7 9 6 4 ]
* pivot: 2, arr: [ 1 2 ]
* pivot: 5, arr: [ 4 5 7 9 6 8 ]
* pivot: 7, arr: [ 6 7 9 8 ]
* pivot: 9, arr: [ 8 9 ]
*
* SORTED ARRAY - [ 1 2 3 4 5 6 7 8 9 ]
*/
@fatalitirar1
Copy link

Check out negative nubers, it's falling in error, or use uint to show sort working only with positive numbers

@khansalmaan
Copy link

Failed for this input
6, 3, 5, 7, 4, 24, 6, 8, 5, 3, 1, 4, 67, 8, 53, 10

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment