@grrrinch

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

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

// пример алгоритма быстрой сортировки с применением рекурсии
//
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)))
}
  • Вопрос задан
  • 128 просмотров
Пригласить эксперта
Ответы на вопрос 2
@grrrinch Автор вопроса
сейчас заметил, в конце у меня условие не верно
сделал так, но попадаю в го рутину
if k > left {
quickSort(A, left, k)
}
Ответ написан
wataru
@wataru
Еще ошибка в этой строчке:
p := A[k/2]

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

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы