Быстрая сортировка, QuickSort.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 | #include <iostream> #include <algorithm> using namespace std; void quickSort(int *arr, int left, int right) { int i = left, j = right; int middle = arr[(left + right) / 2]; do { while(arr[i] < middle) i++; while(arr[j] > middle) j--; if(i <= j) { swap(arr[i], arr[j]); i++; j--; } } while (i <= j); if(i < right) quickSort(arr, i, right); if(left < j) quickSort(arr, left, j); } int main() { int arrSize = 20; int arr[arrSize]; for(int i(0); i < arrSize; ++i) arr[i] = rand() % 200 - 100; quickSort(arr, 0, arrSize - 1); for(int i(0); i < arrSize; ++i) cout << i << ": "<< arr[i] << endl; return 0; } |
9 строка: выбираем опорный элемент (центральный элемент массива)
13 строка: пока значение указателя меньше опорного, переходим к следующему элементу массива, запоминаем положение, если нарушается условие переходим к следующему вайлу.
14 строка: пока значение указателя больше опорного, переходим к предыдущему элементу массива, запоминаем положение указателя, если не совпадает условие переходим к условию.
22 строка: левый счётчик не должен выходить за пределы правого счётчика.
24 строка: если левый указатель меньше правой стартовой позиции то запускаем функцию рекурсивно, передаём в неё массив, стартовую позицию, конечную позицию.
26 строка: если правый указатель больше левой стартовой позиции, то запускаем функцию рекурсивно.
0 коммент.:
Отправить комментарий