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 implement a sorting algorithm. There are different types of sorting methods. In this case, we use a shell sort for sorting elements in an array.
We can say the Shell sort is an extended version of the insertion sort. Both algorithms are comparison-based and in-place sorting algorithms. Shell sort is an efficient sorting algorithm for medium-sized data sets.
Most of the part of shell sort is based on insertion sort. In insertion sort, whenever an element has to be moved far ahead, we move elements only one position ahead and it involved many movements to move an element to a far-away position. It will increase the algorithm's execution time. But in the case of shell sort, It can overcome this drawback of insertion sort. Because shell sort allows the exchange of far items. That means it avoids large shifts as in the case of insertion sort.
In this GO program, we are importing the “fmt” package to include some standard libraries into the 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. After that Main function starts, inside the main, we are doing the whole program.
As we can see, the shell sort algorithm first does sort the elements that are far away from each other, and then it subsequently reduces the gap between them. This gap is called an interval. This interval can be calculated by using Knuth's formula given below,
Knuth’s Formula :
h = h * 3 + 1
where "h" is an interval with an initial value as1
In this program, variable A holds the array elements. Another variable n is used as the size of the array. Read array elements by using for loop. Perform shell sort by calling function shellSort(A, n). Here, the function shellSort(A, n) perform the following things such as Initialize the value of interval, divide the array into smaller sub-array of the equal interval, sort these sub-array using insertion sort and repeat this process until the complete array is sorted.
Given below are the steps that are used in the Go program to implement Shell Sort.
STEP 1: Import the packages 'fmt'.
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 shell sort by calling function shellSort(A, n).
STEP 8: Use for loop to display sorted array.
STEP 9: Exit
STEP 1: Open the first loop to perform shell sort and compare the element at 0 indexes to the element at n/2 index. Here n/2 index is stored in the variable interval.
STEP 2:If the loop condition: element at 0 indexes is greater than the element at interval is true, then do step 3 otherwise, go to step 8.
STEP 3: Open the outer loop for insertion sort by using for loop, which uses the loop variable j by assigning j=interval.
STEP 4: If the outer loop satisfies the condition, jthen it will help you to iterate over the array interval elements from left to right till the end of the array. Otherwise, go to step 7.
STEP 5: If the inner loop satisfies the sorting condition: k >= interval && A[k-interval] > A[k], then swap the values of elements. Otherwise, increment j=j+1 and Go to step 4.
STEP 6: Repeat step 5 by decrement the value of k as k=k-interval.
STEP7: Set interval = interval /2 and go to step 2
STEP 8: Return sorted array A
package main
import "fmt"
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 of the array : ")
for i := 0; i < n; i++ {
fmt.Scan(&A[i])
}
fmt.Println("Sorted array:")
fmt.Println(shellSort(A, n))
}
func shellSort(A []int, n int) []int {
for interval := int(n/2); intervel > 0; interval /= 2 {
for j := interval; j < n; j++ {
for k := j; k >= interval && A[k-intervel] > A[k]; k -= interval {
A[k], A[k-interval] = A[k-interval], A[k]
}
}
}
return A
}
Enter the size of the array 5 Enter elements of the array : 32 24 56 85 13 Sorted array: [13 24 32 56 85]
