Быстрая сортировка (какой еблан додумался сказать что n^2 это быстро?) - EcsFlash/DataTypes GitHub Wiki

Суть:

Основная идея базируется на парадигме «разделяй и властвуй».

Выбирается опорный элемент (например, посередине массива).
Массив просматривается слева-направо и производится поиск ближайшего элемента, больший чем опорный.
Массив просматривается справа-налево и производится поиск ближайшего элемента, меньший чем опорный.
Найденные элементы меняются местами.
Продолжается одновременный двухсторонний просмотр по массиву с последующими обменами в соответствии с пунктами 2-4. В конце концов, просмотры слева-напрво и справа-налево сходятся в одной точке, которая делит массив на два подмассива. К каждому из двух подмассивов рекурсивно применяется "Быстрая сортировка".

Так должно быть в идеале - но это оч заебно как по мне и я совместно с L. Wagner предлагаю следующее:

Выбирается опорный элемент (например, крайний правый для нашего "кусочка").
```
pivot := arr[high]
```
Массив просматривается слева-направо по принципу:
- запоминаем индекс i - в начале он равен "старту" массива
```
i := low
```
- просматриваем массив по j, стартуя с i - если arr[j] < опорного - меняем arr[i] и arr[j] местами, увеличиваем i на единицу
```
for j := low; j < high; j++ {
        if arr[j] < pivot {
    	        arr[i], arr[j] = arr[j], arr[i]
                i++
        }
}
```
- в конце меняем arr[i] с опорным
```
arr[i], arr[high] = arr[high], arr[i]
```
- таким образом получается условная сортировка - элементы, меньшие чем опорный смещаются влево, большие - вправо.
- индекс i становится точкой условного разбиения
Рекурсивно вызываем тот же алгоритм для полученного(условно отсортированного) массива - один вызов для части, меньшей чем опорная, один для большей чем опорная

                arr, p = partition(arr, low, high)
		arr = quickSort(arr, low, p-1)
		arr = quickSort(arr, p+1, high)

Картиночка

Псевдокод

func partition(arr []int, low, high int) ([]int, int) {
	pivot := arr[high]
	i := low
	for j := low; j < high; j++ {
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	arr[i], arr[high] = arr[high], arr[i]
	return arr, i
}

func quickSort(arr []int, low, high int) []int {
	if low < high {
		var p int
		arr, p = partition(arr, low, high)
		arr = quickSort(arr, low, p-1)
		arr = quickSort(arr, p+1, high)
	}
	return arr
}

func QuickSort(arr []int) []int {
	return quickSort(arr, 0, len(arr)-1)
}

Cложность

┌────────────┬────────────────┬──────────────────┬────────────────┐
│ Сложность  │ Лучший случай  │ Средний случай   │ Худший случай  │
├────────────┼────────────────┼──────────────────┼────────────────┤
│   Время    │   O(n log n)   │    O(n log n)    │     O(n²)      │
├────────────┼────────────────┼──────────────────┼────────────────┤
│  Память    │    O(log n)    │    O(log n)      │     O(n)       │
└────────────┴────────────────┴──────────────────┴────────────────┘