Почему возникла ошибка при сортировке?

Question

[Евгений Усачев]

Я переписываю быструю сортировку с JS на Go. Код такой:

type number interface {
	int | int8 | int16 | int32 | int64 | float32 | float64 | uint | uint8 | uint16 | uint32 | uint64
}

type compareTypes interface {
	number | string | byte | rune
}
func qSort[T compareTypes](array []T) []T {

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

	pivot := array[0]
	var left []T
	var right []T
	length := len(array)
	for i := length - 1; i >= 0; i-- {
		if array[i] < pivot {
			left = append(left, array[i])
		} else {
			right = append(right, array[i])
		}
	}

	return append(qSort(left), qSort(right)...)
}

Если вызвать код со слайсом без повторяющихся значений, код отработает правильно.
Но со слайсом, например: []int8{127, 1, 0, 100, 2, 33, 123, 12, -123, -12, 21, -32, 1} -
вдруг ошибка:

fatal error: stack overflow

И указатель на строку: return append(qSort(left), qSort(right)...).
В чём ошибка?

Comments

[mayton2019]

Зачем здесь append?

array = append(qSort(left), qSort(right)...)

Answer 1

[Denkuwus]

Вот пример того, как вы можете изменить функцию qSort, чтобы использовать итеративный подход и обрабатывать случай, когда элемент сводки уже отсортирован:

func qSort[T compareTypes](array []T) []T {
	if len(array) <= 1 {
		return array
	}

	left := make([]T, 0)
	right := make([]T, 0)

	for len(array) > 0 {
		pivot := array[0]
		array = array[1:]

		for _, x := range array {
			if x.Compare(pivot) < 0 {
				left = append(left, x)
			} else {
				right = append(right, x)
			}
		}

		if len(left) == 0 {
			array = right
			right = nil
		} else if len(right) == 0 {
			array = left
			left = nil
		} else {
			array = append(qSort(left), qSort(right)...)
			left = nil
			right = nil
		}
	}

	return array
}

Этот код использует итеративный подход для сортировки массива, что позволяет избежать возможности переполнения стека. Он также обрабатывает случай, когда опорный элемент уже отсортирован, проверяя, пуст ли левый или правый срез, и продолжая цикл с другим срезом, если он пуст.

Обратите внимание, что для того, чтобы этот код работал, вам необходимо определить метод Compare для каждого типа, который вы хотите использовать с функцией qSort. Например, если вы хотите использовать qSort со значениями int8, вам нужно определить метод Compare для типа int8, который принимает другое значение int8 в качестве аргумента и возвращает целое число, указывающее, является ли первое значение меньше, равно или больше. чем второе значение.

Надеюсь, это поможет!

Answer 2

[jcmvbkbc]

В чём ошибка?

В том, что функция qSort при попытке сортировки массива одинаковых значений все их сносит в массив right, оставляя массив left пустым. Циклический алгоритм на этом месте зациклился бы, а рекурсивный с не-хвостовой рекурсией выходит за ограничение размера стека.