For a better understanding of this example, we always recommend you to learn the basic topics of Golang programming listed below:
Here we are explaining how to write a GO program to sort a list of elements from an array. There are different types of sorting algorithms. In this case, we use a Quick Sort for sorting array elements. Quicksort is one of the most efficient sorting algorithms which is commonly used in production sorting implementations. As the name implies, we can say it is the fastest sorting algorithm, but you should give attention and care to the sorting implementation otherwise your speed can drop quickly. So it's not an efficient algorithm for large data sets.
It works on the principle of the divide and conquers class of algorithms. Here it divides an array into smaller chunks which will help you to sort elements fast and easily.
Here we use a specified value is called a pivot. A large unsorted array is partitioned into two sub-arrays based on the pivot position. One of the arrays holds values smaller than the pivot value, based on which the partition is made and another array holds values greater than the pivot value. Then perform the sort operation recursively on both sides of the pivot till there are no more sub-arrays existing.
In this GO program, we accept the user's values using the 'fmt.scanln()' and 'fmt.println()' methods which are defined under the fmt package. In order to use these functions, we need to import the “fmt” package. To convert string type into int type, we use Atoi() function which is equivalent to ParseInt(str string, base int, bitSize int). You need to import the "strconv" Package in your program to access Atoi() function.
Here variable A holds the array elements. Other variables n and pivot are used as the size of the array and pivot index element respectively. Use for loop to read array elements. Use two variables low and high to store the lowest and highest index position except for the pivot element. Quick Sort algorithm is developed using the divide and conquer approach and it works under the comparison algorithm category.
Here we mainly use two functions, the main quickSort() function as well as the partition() function. The partition() function is used to find the pivot value and is responsible for moving everything to the correct side of the pivot. The quickSort() function is used to handle the recursive nature of the algorithm.
Given below are the steps which are used in the Go program to implement QuickSort.
STEP 1: Import the packages 'fmt' and 'strconv'
STEP 2: Open the main() to start the program, GO program execution starts with the main()
STEP 3: Declare the variable n.
STEP 4: Read the size of the array as n
STEP 5: Define the array A[]
STEP 6: Read the A[] array elements by using a 'for loop'.
STEP 7: Perform quick sort by calling function quickSort(arr, 0, len(arr) - 1)
STEP 8: Use for loop to display sorted array.
STEP 9: Exit
STEP 1: Check if low < high, then find the pivot index of a lower bound of an array by calling partition(A, low, high)
STEP 2: Apply Divide and conquer strategy to sort the left side array respective to the pivot position by calling quickSort(A, low, pivot)
STEP 3: Sort the right side array respective to the pivot position by calling quickSort(A, pivot + 1, high)
STEP 1: Pick a lowest bound element as a pivot value pivot
STEP 2: Declare two variables low and high (i.e. pointer) to store the lowest and highest index position except for the pivot element.
STEP 3: Assign i=low, j=high.
STEP 4: Using for loop, move the left side pointer towards the right by incrementing the index value of 'i' until the value of the pointer A[i] is less than or equal to the pivot element.
STEP 5: Using for loop, move the right side pointer towards the left by decrementing the index value of 'j' until the value of the pointer is greater than the pivot element.
STEP 6: Interchange the values of the present in the index i and j of an array only if i is less than j
STEP 7: Interchange the element in j'th position to the lower bound of an array and place the Pivot element to the j's position
STEP 8: Finally return the appropriate index position of the pivot element
package main
import (
"fmt"
"strconv"
)
func quickSort(A []int, low, high int) {
if low < high {
// Find the pivot index of an lower bound of an array
var pivot = partition(A, low, high)
// Apply Divide and conquer strategy
// to sort the left side and right side of an array
// respective to the pivot position
// Left hand side array
quickSort(A, low, pivot)
// Right hand side array
quickSort(A, pivot + 1, high)
}
}
func partition(A []int, low, high int) int {
// Pick a lowest bound element as an pivot value
var pivot = A[low]
var i = low
var j = high
for i < j {
// Increment the index value of "i"
// till the left most values should be less than or equal to the pivot value
for A[i] <= pivot && i < high {
i++;
}
// Decrement the index value of "j"
// till the right most values should be greater than to the pivot value
for A[j] > pivot && j > low {
j--
}
// Interchange the values of present
// in the index i and j of an array only if i is less than j
if i < j {
var temp = A[i]
A[i] = A[j]
A[j] = temp
}
}
// Interchange the element in j's poisition to the lower bound of an array
// and place the Pivot element to the j's position
A[low] = A[j]
A[j] = pivot
// Finally return the appropriate index position of the pivot element
return j
}
func main() {
fmt.Println("Enter the size of the array")
var n int
fmt.Scan(&n)
A := make([]int, n, 100)
fmt.Println("Enter elements : ")
for i := 0; i < n; i++ {
fmt.Scan(&A[i])
}
quickSort(A, 0, len(A) - 1)
fmt.Print("After Sorting: ")
for i := 0; i < n; i++ {
fmt.Print(strconv.Itoa(A[i]) + " ")
}
}
Enter the size of the array 5 Enter elements: 81 60 73 52 95 After Sorting: 52 60 73 81 95
