You cannot select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
70 lines
1.5 KiB
Go
70 lines
1.5 KiB
Go
// ====================================================
|
|
// Data-Structures-with-Go Copyright(C) 2017 Furkan Türkal
|
|
// This program comes with ABSOLUTELY NO WARRANTY; This is free software,
|
|
// and you are welcome to redistribute it under certain conditions; See
|
|
// file LICENSE, which is part of this source code package, for details.
|
|
// ====================================================
|
|
|
|
package main
|
|
|
|
import "fmt"
|
|
|
|
func Swap(a *int, b *int) {
|
|
t := *a
|
|
*a = *b
|
|
*b = t
|
|
}
|
|
|
|
func Partition(arr []int, start, end int) int {
|
|
|
|
pivot := arr[end]
|
|
|
|
//Index of smaller element
|
|
var i int = (start - 1)
|
|
|
|
for j := start; j <= end-1; j++ {
|
|
//If current element is smaller than or equal to pivot
|
|
if arr[j] <= pivot {
|
|
i++
|
|
Swap(&arr[i], &arr[j])
|
|
}
|
|
}
|
|
|
|
Swap(&arr[i+1], &arr[end])
|
|
|
|
return (i + 1)
|
|
}
|
|
|
|
/*The main function that implements QuickSort
|
|
arr[] -> Array to be sorted
|
|
start -> Starting index
|
|
end -> Ending index
|
|
*/
|
|
func QuickSort(arr []int, start, end int) {
|
|
if start < end {
|
|
//pi is partitioning index, arr[p] is now at right place
|
|
var pi int = Partition(arr, start, end)
|
|
|
|
//Separately sort elements before partition and after partition
|
|
QuickSort(arr, start, pi-1)
|
|
QuickSort(arr, pi+1, end)
|
|
}
|
|
}
|
|
|
|
func PrintArray(arr []int, size int) {
|
|
for i := 0; i < size; i++ {
|
|
fmt.Printf("%d ", arr[i])
|
|
}
|
|
fmt.Printf("\n")
|
|
}
|
|
|
|
func main() {
|
|
arr := []int{10, 7, 8, 9, 1, 5}
|
|
var n int = len(arr)
|
|
|
|
QuickSort(arr, 0, n-1)
|
|
|
|
fmt.Println("Sorted array is: ")
|
|
PrintArray(arr, n)
|
|
}
|