Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Сортировка Быстрым методом
|
|
Быстрая сортировка является одним из самых эффективных и распространенных методов. Суть метода заключается в разделении массива на две части от опорного элемента. Все меньшие или равные опорному в левую часть, а все большие или равные опорному в правую. Затем рекурсивно запускаем ту же операцию для каждой части и так до конца сортировки.
Рассмотрим алгоритм более подробно.
1. Введем два указателя: i и j. В начале алгоритма они указывают, соответственно, на левый и правый конец последовательности.
2. Будем двигать указатель i с шагом в 1 элемент по направлению к концу массива, пока не будет найден элемент a[i] > = p. Затем аналогичным образом начнем двигать указатель j от конца массива к началу, пока не будет найден a[j] < = p.
3. Далее, если i < = j, меняем a[i] и a[j] местами и продолжаем двигать i, j по тем же правилам...
4. Повторяем шаг 3, пока i < = j.
5. Рекурсивно вызываем эту же функцию для каждой части.
Блок-схема и алгоритм метода представлен ниже:
Рис. 1.4. Блок-схема Быстрой сортировки
void quickSortR(long* array, long N) {// На входе - массив array[], a[N] - его последний элемент. long i = 0, j = N; // поставить указатели на исходные местаlong temp, p; p = array[N> > 1]; // центральный элемент // процедура разделенияdo {while (array[i] < p) i++; while (array[j] > p) j--; if (i < = j) {temp = array[i]; array[i] = a[j]; array[j] = temp; i++; j--; }} while (i< =j); // рекурсивные вызовы, если есть, что сортировать if (j > 0) quickSortR(array, j); if (N > i) quickSortR(array+i, N-i); }
Каждое разделение требует, очевидно, Theta(n) операций. Количество шагов деления(глубина рекурсии) составляет приблизительно log n, если массив делится на более-менее равные части. Таким образом, общее быстродействие: O(n log n), что и имеет место на практике.
Однако, возможен случай таких входных данных, на которых алгоритм будет работать за O(n2) операций. Такое происходит, если каждый раз в качестве центрального элемента выбирается максимум или минимум входной последовательности. Если данные взяты случайно, вероятность этого равна 2/n. И эта вероятность должна реализовываться на каждом шаге... Вообще говоря, малореальная ситуация.
Метод неустойчив. Поведение довольно естественно, если учесть, что при частичной упорядоченности повышаются шансы разделения массива на более равные части.
Сортировка использует дополнительную память, так как приблизительная глубина рекурсии составляет O(log n), а данные о рекурсивных подвызовах каждый раз добавляются в стек.