Реферат: Сортировка данных в массиве
scanUp++;
После позиционирования scanUp индекс scanDown продвигается вниз по списку, пока не встретится элемент, меньший или равный центральному.
|
while (pivot < A[scanDown]) scanDown--; |
По окончании этого цикла (и при условии что scanUp < scanDown) оба индекса адресуют два элемента, находящихся не в тех подсписках. Эти элементы меняются местами.
| Swap(A[scanUp], A[scanDown]); |
Обмен элементов прекращается, когда scanDown становится меньше, чем scanUp. В этот момент scanDown указывает начало левого подсписка, который содержит меньшие или равные центральному элементы. Индекс scanDown становится центральным. Взять центральный элемент из A[low]:
| Swap(A[low], A[scanDown]); |
Для обработки подсписков используется рекурсия. После обнаружения точки разбиения мы рекурсивно вызываем QuickSort с параметрами low, mid-1 и mid+1, high. Условие останова возникает, когда в подсписке остается менее двух элементов, так как одноэлементный или пустой массив упорядочивать не нужно.
|
// Swap меняет местами элементы массива. Соответствующий тип данных // должен поддерживать операцию «=». template <class T> void Swap(T & el1, T & el2) { T tmp = el1; el1 = el2; el2 = tmp; } // QuickSort принимает в качестве параметров массив // и предельные значения его индексов template <class T> void QuickSort(T A[], int low, int high) { // локальные переменные, содержащие индекс середины - mid, // центральный элемент и индексы сканирования T pivot; int scanUp, scanDown; int mid; // если диапазон индексов не включает в себя // как минимум два элемента, завершить работу if(high - low <= 0) К-во Просмотров: 595
Бесплатно скачать Реферат: Сортировка данных в массиве
|