Cортировка

Сортировка - один из фундаментальных алгоритмов в компьютерных науках. В
этой статье рассмотрим основные алгоритмы сортировки, их временную и
пространственную сложность, а также реализацию на языке Go (Golang).

1. Сортировка пузырьком (Bubble Sort)

Сложность:

• В худшем случае: O(n²)
• В лучшем случае (улучшенная версия): O(n)
• Средний случай: O(n²)

Пространственная сложность: O(1)

go

func bubbleSort(arr []int) {

n := len(arr)
for i := 0; i < n-1; i++ {

swapped := false
for j := 0; j < n-i-1; j++ {

if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = true
}
}

if !swapped {
break
}

}
}

2. Сортировка выбором (Selection Sort)

Сложность:

• Все случаи: O(n²)

Пространственная сложность: O(1)

go

func selectionSort(arr []int) {

n := len(arr)
for i := 0; i < n-1; i++ {

minIdx := i
for j := i + 1; j < n; j++ {

if arr[j] < arr[minIdx] {
minIdx = j
}
}

arr[i], arr[minIdx] = arr[minIdx], arr[i]
}

}

3. Сортировка вставками (Insertion Sort)

Сложность:

• В худшем случае: O(n²)
• В лучшем случае: O(n)
• Средний случай: O(n²)

Пространственная сложность: O(1)

go

func insertionSort(arr []int) {

n := len(arr)
for i := 1; i < n; i++ {

key := arr[i]
j := i - 1
for j >= 0 && arr[j] > key {

arr[j+1] = arr[j]
j--
}

arr[j+1] = key
}
}

4. Быстрая сортировка (Quick Sort)

Сложность:

• В худшем случае: O(n²)
• В среднем случае: O(n log n)

Пространственная сложность: O(log n) (из-за рекурсии)

go

func quickSort(arr []int) {

if len(arr) <= 1 {
return
}

pivot := arr[len(arr)/2]
left := make([]int, 0)
right := make([]int, 0)
equal := make([]int, 0)

for _, v := range arr {

switch {
case v < pivot:
left = append(left, v)
case v > pivot:
right = append(right, v)
default:
equal = append(equal, v)
}

}

quickSort(left)
quickSort(right)

copy(arr, append(append(left, equal...), right...))
}

5. Сортировка слиянием (Merge Sort)

Сложность:

• Все случаи: O(n log n)

Пространственная сложность: O(n)

go

func mergeSort(arr []int) []int {

if len(arr) <= 1 {
return arr
}

mid := len(arr) / 2
left := mergeSort(arr[:mid])
right := mergeSort(arr[mid:])

return merge(left, right)
}

func merge(left, right []int) []int {

result := make([]int, 0, len(left)+len(right))
i, j := 0, 0

for i < len(left) && j < len(right) {

if left[i] < right[j] {

result = append(result, left[i])
i++
} else {

result = append(result, right[j])
j++
}
}

result = append(result, left[i:]...)
result = append(result, right[j:]...)

return result
}

6. Пирамидальная сортировка (Heap Sort)

Сложность:

• Все случаи: O(n log n)

Пространственная сложность: O(1)

go

func heapSort(arr []int) {

n := len(arr)

// Построение max-heap
for i := n/2 - 1; i >= 0; i-- {

heapify(arr, n, i)
}

// Извлечение элементов из кучи
for i := n - 1; i > 0; i-- {

arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
}
}

func heapify(arr []int, n, i int) {

largest := i
left := 2*i + 1
right := 2*i + 2

if left < n && arr[left] > arr[largest] {

largest = left
}

if right < n && arr[right] > arr[largest] {

largest = right
}

if largest != i {

arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
}
}

Когда какой алгоритм использовать?

1. Для небольших массивов (n < 100): сортировка вставками или выбором
2. Для средних массивов (100 < n < 10000): быстрая сортировка или сортировка слиянием
3. Для больших массивов (n > 10000): сортировка слиянием или пирамидальная
4. Когда важна стабильность: сортировка слиянием или вставками
5. Когда важна память: сортировка выбором или пирамидальная

В
стандартной библиотеке Go используется гибридный алгоритм на основе
быстрой сортировки, который переключается на сортировку вставками для
небольших подмассивов. Это реализовано в пакете sort.