Быстрая сортировка на Golang, почему правая сторона не сортируется?

Question

[grrrinch]

Изучаю книжку "Грокаем алгоритмы", сейчас застопорился на быстрой сортировке.
Ниже код на голанг, почему-то правая сторона не сортируется.

// пример алгоритма быстрой сортировки с применением рекурсии
//
package main

import "fmt"

func quickSort(A []int, b int, k int) []int {
	left, right := b, k-1 // определяем нижние и верхние границы массива
	p := A[k/2]           // опорный элемент
	for left <= right { // пока нижняя и верхняя границы массива не пересеклись
		for A[left] < p { // если первый элемент в нижнем массиве меньше опорного - переодим к следующему
			left++
		}
		for A[right] > p {
			right--
		}
		if left >= right {
			break
		}
		if A[left] > A[right] {
			A[left], A[right] = A[right], A[left]
		}
	}
	if right > 0 {
		quickSort(A, b, right)
	}
	if left > k {
		quickSort(A, left, k)
	}
	return A
}

func main() {
	unsortArr := []int{44, 14, 2, 4, 66, 54, 72, 34, 1, 3, 5, 8, 99, 12}
	fmt.Println(quickSort(unsortArr, 0, len(unsortArr)))
}

Comments

[di]

Потому что массив изменяется

Answer 1

[grrrinch]

сейчас заметил, в конце у меня условие не верно
сделал так, но попадаю в го рутину
if k > left {
quickSort(A, left, k)
}

Answer 2

[Wataru]

Еще ошибка в этой строчке:
p := A[k/2]

Вам надо выбрать какой-то (видимо, средний) элемент между b и k. Если b достаточно большое, то k/2 вылезет за границу сортируемого куска. Для среднего надо писать (b+k)/2.

Comments

[grrrinch]

для аргумента k в функции main передается значение len(A) - длина массива
дальше я эту длину разбиваю на 2 - выбираю средний элемент
если я буду делать по вашему примеру (b+k)/2 - то это будет ДЛИНА МАССИВА + НИЖНЯЯ ГРАНИЦА МАССИВА. при таком варианте я точно вылезу за границы
кроме того, аргумент b я передаю в left и затем при поиске инкрементирую

for A[left] < p {
left++
}

и при рекурсии в аргумент b передаю left
if left > k {
quickSort(A, left, k)
}

именно эта рекурсия и создает рутину

[Wataru]

Вы посмотрите, что у вас в рекурсии передается в параметрах и подумайте, какой смысл у параметров. Почему вы передаете right в рекурсии, если у вас последний аргумент - длина массива? У вас передаются начало и конец сортируемого куска массива. И да, для первого вызова правильно передается длина массива, потому что кусок-то с начала сортируется.

Почитайте описание алгоритма еще раз - в качестве pivot надо выбрать любой элемент сортируемого куска. Если вы будете делать (b+k)/2, то это будет среднее между k-ым и b-ым элементами - началом и концом сортируемого куска. Как раз середина этого куска.

Это не основная проблема, на самом деле - работать у вас сортировка будет, но медленно, потому что pivot почти всегда будет меньше любого элемента на сортируемом куске - а значит вся сортировка будет работать за квадратичную сложность.

[grrrinch]

Спасибо большое за ответы
Я обязательно гляну, просто сейчас загружен работой