Реализация рекурсивной быстрой сортировки

Сортировка, основанная на сравнениях, широко используемая на практике из-за быстрой работы в большинстве случаев (Quick Sort). Принцип работы сортировки, выбор опорного элемента алгоритма и этап разделения массива на части. Код рекурсивной сортировки.

Рубрика Программирование, компьютеры и кибернетика
Вид статья
Язык русский
Дата добавления 16.01.2016
Размер файла 16,5 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

QuickSort

Быстрая сортировка(Quick Sort, QSort) -- сортировка, основанная на сравнениях, широко используется на практике из-за быстрой работы в большинстве случаев. Эта сортировка не является стабильной, реализуется рекурсивно.

QSort -- классический пример принципа разделяй и властвуй.

QSort традиционно реализуется как функция, которой на вход подается массив a и значения l и r. Вызов QSort(a,l,r) сортирует участок массива с индексами от l до r включительно. Для полной сортировки массива нужно вызвать QSort(a,0,n-1). Общий принцип работы Qsort следующий:

1. Выбирается опорное значение x, равное

x=a[i]

2. С помощью индексов i и j массив а делится на три части:

a) [l,i)содержит все элементы, меньше х

б) [j,i)содержит все элементы, равные х

в) [i,r]содержит все элементы, больше х

3. Элементы средней части уже заняли свое относительное положение и для полной сортировки массива достаточно отдельно отсортировать левую и правую части, если в них более одного элемента

В зависимости от выбора опорного элемента, изменяется те входные последовательности, на которых алгоритм работает за Размещено на http://www.allbest.ru/

, поэтому используют различные подходы к выбору опорного элемента, основная цель которых -- увеличить вероятность того, что левая и правая части будут разделены примерно поровну:

1. -- очень часто встречается «плохая» входная последовательность элементов

2.

x=a[l](x=a[r])

сортировка быстрый рекурсивный код

-- аналогично предыдущему очень часто будет работать за

3.

x=a[random(l,r)]

-- очень маленькая вероятность долгого времени работы, однако из-за случайности выбора не используется в стандартных пакетах

4. Особым образом выбрать три элемента массива, а потом взять средний из них (медиана из трех). Это наиболее устойчивый способ выбора опорного элемента.

Этап разделения массива на 3 части называется partition и может быть осуществлен за О(n). В предположении, что разделение массива на левую и правую части происходит примерно поровну, время работы алгоритма можно оценить с помощью следующей рекуррентной формулы:

T(n) = 2T(n/2) + O(n).

Несложно доказать, что

T(n)=O(n log(n)).

Суммарное количество действий для фиксированной глубины рекурсии составит O(n), при разделении примерно поровну, максимальная глубина рекурсии составит logn, а следовательно количество действий -- nlog(n).

На самом деле, даже при разделении в пропорции 1:2. Таким образом, разделение в любой, но фиксированной пропорции приводит к логарифмической оценке максимальной глубины, но «равномерность» раздела влияет на величину константы.

Алгоритм этапа partition:

1. Возьмем i=l и j=r

2. Пока a[i] < x, увеличиваем индекс i на единицу.

3. Пока a[j] > x, уменьшаем индекс j на единицу.

4. Если меняем значения a[i] и a[j] местами. Уменьшаем j на 1. Увеличиваем i на 1.

5. Возвращаемся к шагу 2 и продолжаем работу алгоритма, иначе разделение массива на три части по опорному элементу х завершено.

В данной статье я представлю рекурсивный пример реализации быстрой сортировки. Массив, который нужно отсортировать будет глобальным, если же вы захотите сделать его локальным, то просто передавайте его как параметр в функцию. Конечно, после того, как вы сделаете это вам нужно будет использовать template для того, чтобы ваша функция работала со всеми типами данных. Я этим заниматься в рамках данной статьи не буду, поэтому просто приведу код рекурсивной сортировки quicksort:

#include <iostream>

using namespace std;

int a[100];

void quickSort(int l, int r)

{

int x = a[l + (r - l) / 2];

//запись эквивалентна (l+r)/2,

//но не вызывает переполнения на больших данных

int i = l;

int j = r;

//код в while обычно выносят в процедуру particle

while(i <= j)

{

while(a[i] < x) i++;

while(a[j] > x) j--;

if(i <= j)

{

swap(a[i], a[j]);

i++;

j--;

}

}

if (i<r)

quickSort(i, r);

if (l<j)

quickSort(l, j);

}

int main()

{

int n;//количество элементов в массиве

cin >> n;

for(int i = 0; i < n; i++)

{

cin>>a[i];

}

quickSort(0, n-1);

for(int i = 0; i < n; i++)

{

cout<<a[i]<<" ";

}

return 0;

}

Размещено на Allbest.ru

...

Подобные документы

  • Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.

    курсовая работа [291,5 K], добавлен 22.03.2012

  • Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.

    реферат [189,8 K], добавлен 06.12.2014

  • Исследование основных особенностей алгоритмов быстрой и поразрядной сортировки данных. Построение графиков зависимости времени сортировки от количества элементов в файле и от степени перемешенности элементов. Описания сортировки чисел и строковых данных.

    лабораторная работа [1,2 M], добавлен 23.07.2012

  • Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.

    курсовая работа [161,7 K], добавлен 17.12.2015

  • Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.

    реферат [614,8 K], добавлен 12.04.2014

  • Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.

    курсовая работа [203,8 K], добавлен 03.12.2010

  • Исторические предпосылки разработки тестирования. Виды электронных тестов и их роль в программировании. Этапы разработки программы для решения задачи быстрой сортировки. Пользовательский интерфейс, отладка, алгоритм программы. Файл теста в формате XML.

    курсовая работа [1,5 M], добавлен 27.01.2014

  • Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора.

    курсовая работа [637,6 K], добавлен 29.11.2014

  • Разработка программы, сортирующей массивы данных различного типа методом подсчета. Основные шаги алгоритма сортировки, ее свойства и модификация подсчетом. Целесообразность применения сортировки подсчетом. Условия эффективности алгоритма сортировки.

    лабораторная работа [438,5 K], добавлен 16.07.2015

  • Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи.

    реферат [20,7 K], добавлен 20.05.2010

  • Описание алгоритма сортировки с двоичным включением, выбор структур данных. Пример сортировки массива, отсортированного случайным образом. Алгоритм покрытия по методу "Построение одного кратчайшего покрытия". Волновой алгоритм поиска длиннейшего пути.

    курсовая работа [78,2 K], добавлен 24.09.2010

  • Составление программы сортировки по возрастанию массив из 20 шестнадцатеричных чисел, просматривающей все исходные числа во внешней памяти и выбирающей самое большое число. Блок-схема алгоритма работы программы. Таблица команд и число их выполнения.

    курсовая работа [23,1 K], добавлен 24.05.2015

  • Представление данных в цифровых автоматах, методы контроля их работы. Построение алгоритма реализации численного метода "быстрой сортировки", построение кода и блок-схемы Хемминга. Выполнение арифметических и логических исчислений с целыми числами.

    курсовая работа [98,7 K], добавлен 22.12.2009

  • Постановка задачи сортировки. Анализ основных понятий сортировок слияниями. Алгоритм сортировки простым и естественным слиянием. Оценка сложности алгоритма. Программная реализация простого слияния. Тестирование меню на корректность входных данных.

    курсовая работа [283,6 K], добавлен 22.06.2015

  • Анализ структуры топологической сортировки в программной среде. Метод топологической сортировки с помощью обхода в глубину. Программа, реализующая топологическую сортировку методом Демукрона. Создание карты сайта и древовидная система разделов.

    курсовая работа [1,3 M], добавлен 22.06.2011

  • Реализация различных методов сортировки. Алгоритмические языки программирования. Обработка большого числа единообразно организованных данных. Алгоритмы сортировки массивов. Анализ проблем реализации и использования различных видов сортировок массивов.

    курсовая работа [640,3 K], добавлен 07.07.2011

  • Определение понятия, видов и задач сортировки. Рассмотрение основ построения простых и улучшенных алгоритмов сортировки, анализ числа операций. Линейная и пирамидальная организация данных. Основные правила нижней оценки числа операций в алгоритмах.

    презентация [274,5 K], добавлен 19.10.2014

  • Алгоритм сортировки Шейкер: математическое описание задачи и описание алгоритма. Алгоритм покрытия: построение одного кратчайшего покрытия. Описание схемы и работы алгоритма на графах: нахождение кратчайшего пути. Контрольные примеры работы алгоритмов.

    курсовая работа [43,8 K], добавлен 19.10.2010

  • Понятие и основной принцип действия алгоритмов сортировки информации. Сравнительное исследование и анализ эффективности методов сортировки Шелла и Флойда в виде графиков зависимостей количества сравнений и числа перестановок элементов от объёма данных.

    контрольная работа [573,6 K], добавлен 09.11.2010

  • Анализ эффективности методов сортировки данных в языке Turbo Pascal. Разработка эскизного и технического проекта программы. Сортировка без и с использованием дополнительной памяти, за исключением небольшого стека (массива). Сортировка связанных списков.

    курсовая работа [359,0 K], добавлен 23.05.2012

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.