Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
⚡️ Для новых пользователей первый месяц бесплатно. А далее 290 руб/мес, это в 3 раза дешевле аналогов. За эту цену доступен весь функционал: напоминание о визитах, чаевые, предоплаты, общение с клиентами, переносы записей и так далее.
✅ Уйма гибких настроек, которые помогут вам зарабатывать больше и забыть про чувство «что-то мне нужно было сделать».
Сомневаетесь? нажмите на текст, запустите чат-бота и убедитесь во всем сами!
Сортировка Быстрым методом
|
|
Быстрая сортировка является одним из самых эффективных и распространенных методов. Суть метода заключается в разделении массива на две части от опорного элемента. Все меньшие или равные опорному в левую часть, а все большие или равные опорному в правую. Затем рекурсивно запускаем ту же операцию для каждой части и так до конца сортировки.
Рассмотрим алгоритм более подробно.
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), а данные о рекурсивных подвызовах каждый раз добавляются в стек.
|
|