Posted on by Kalkicode
Code Stack

Quicksort using stack in golang

Go program for Quicksort using stack. Here more information.

package main
import "fmt"
/*
    Go program for
    Quicksort using stack
*/
type Boundary struct {
	s int
	e int
}
func getBoundary(s int, e int) * Boundary {
	// return new Boundary
	return &Boundary {
		s,
		e,
	}
}

// Swap the array element
func swap(arr[] int, i int, j int) {
	var temp int = arr[i]
	arr[i] = arr[j]
	arr[j] = temp
}
func partition(arr[] int, low int, high int) int {
	// Set the high index element to its 
	// proper sorted position
	var pv int = arr[high]
	var i int = low - 1
	for j := low ; j < high ; j++ {
		if arr[j] < pv {
			i++
			swap(arr, i, j)
		}
	}
	// Set the high index value to its sorted position
	swap(arr, i + 1, high)
	// Returns the next sorting  element location
	return i + 1
}
func quickSort(arr[] int, n int) {
	var record = make([]*Boundary, 0)
	var s int = 0
	var e int = n - 1
	// Add first boundary location of given array
	record = append(record, getBoundary(s, e))
	for (len(record) > 0 ) {
		// Get top Boundary value
		s = record[len(record) - 1].s
		e = record[len(record) - 1].e
		// Remove the top element of stack
		record = record[: len(record) - 1]
		// Get pivot and arrange elements
		var pv int = partition(arr, s, e)
		if pv - 1 > s {
			// Add the subarray of boundary position
			// from s to pv-1
			record = append(record, getBoundary(s, pv - 1))
		}
		if pv + 1 < e {
			// Add the subarray of boundary position
			// from pv + 1 to e
			record = append(record, getBoundary(pv + 1, e))
		}
	}
}
// Display array elements
func displayArray(arr[] int, n int) {
	for i := 0 ; i < n ; i++ {
		fmt.Print("  ", arr[i])
	}
	fmt.Print("\n")
}
func main() {
	
	// Testing elements
	var arr = [] int {
		3,
		7,
		1,
		-2,
		5,
		7,
		6,
		2,
		1,
		6,
		6,
		2,
		9,
		8,
	}
	// Get the number of elements in array
	var n int = len(arr)
	fmt.Println("Before Sort :")
	displayArray(arr, n)
	// Perform quick sort
	quickSort(arr, n)
	fmt.Println("After Sort :")
	displayArray(arr, n)
}

Output

Before Sort :
  3  7  1  -2  5  7  6  2  1  6  6  2  9  8
After Sort :
  -2  1  1  2  2  3  5  6  6  6  7  7  8  9

Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

New Comment