Comb Sort Algorithm

The Comb Sort Algorithm is an advanced sorting technique that builds upon the basic concepts of the Bubble Sort Algorithm. It is an efficient, in-place, comparison-based sorting algorithm, invented by Wlodzimierz Dobosiewicz and Artur Borowy in 1980, and later optimized by Stephen Lacey and Richard Box in 1991. The fundamental idea behind comb sort is to eliminate small values toward the end of the list and large values toward the beginning of the list, referred to as "turtles" and "rabbits" respectively, which cause the Bubble Sort algorithm to be slow. To achieve this, Comb Sort uses a variable gap between elements to be compared, which is gradually reduced to 1 as the algorithm progresses, ultimately becoming a simple Bubble Sort. During the execution of the Comb Sort Algorithm, the list is traversed, and elements that are separated by the gap are compared and swapped if they are in the wrong order. The gap is initially set to a large value, typically the list length divided by a shrink factor (usually 1.3), and is reduced by the shrink factor in each iteration until it reaches 1. At this point, the algorithm turns into a conventional Bubble Sort, and the final step of the process is to iterate through the list, comparing and swapping adjacent elements as necessary. The Comb Sort algorithm is particularly effective for sorting lists that are partially ordered or have a small number of inversions, as it takes advantage of the existing order to quickly sort the data. While it is not as fast as more advanced algorithms like QuickSort or MergeSort, Comb Sort is an improvement over the basic Bubble Sort, offering better performance for large lists and partially ordered data.
package CombSort

import (
	"math/rand"
	"sort"
	"testing"
	"time"
)

func CombSort(array []int) {
	gapValue := len(array)
	swapCount := 1
	for gapValue >= 1 && swapCount != 0 {
		if gapValue != 1 {
			gapValue = int(float64(gapValue) / float64(1.3))
		}
		swapCount = 0
		firstItem := 0
		secondItem := gapValue
		for secondItem != len(array) {
			if array[firstItem] > array[secondItem] {
				array[firstItem], array[secondItem] = array[secondItem], array[firstItem]
				swapCount += 1
			}
			firstItem += 1
			secondItem += 1
		}
	}
}

func TestCombSort(t *testing.T) {
	random := rand.New(rand.NewSource(time.Now().UnixNano()))
	array1 := make([]int, random.Intn(100-10)+10)
	for i := range array1 {
		array1[i] = random.Intn(100)
	}
	array2 := make(sort.IntSlice, len(array1))
	copy(array2, array1)
	CombSort(array1)
	array2.Sort()
	for i := range array1 {
		if array1[i] != array2[i] {
			t.Fail()
		}
	}
}

LANGUAGE:

DARK MODE: