Быстрая сортировка. Сортировка вставками

Сортировка вставками.

Сортировка выбором.

1. Общее быстродействие O(n^2).

2. Сортировка происходит на месте.

3. Неустойчивая.

4. Поведение неестественное.

Идея метода:

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

A[1..N] - сортируемый массив из n элементов.

for (i=1; i<N; i++) Hайти наименьший из элементов i..N и поменять его местами с i-м.

1. Общее быстродействие O(n^2). Но ввиду простоты реализации, является самой быстрой для малых массивов и списков (менее 20 элементов). В виду своих особенностей, алгоритм хорош для частично отсортированных данных.

2. Сортировка происходит на месте.

3. Устойчивая.

4. Поведение естественное.

Идея метода:

Сортировка простыми вставками в чем-то похожа на "пузырек" или "выбор". Аналогичным образом делаются проходы по части массива, и аналогичным же образом в его начале "вырастает" отсортированная последовательность. Однако в сортировке пузырьком или выбором можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же хотя последовательность a[0]...a[i] упорядочена, но по ходу алгоритма в нее могут вставляться новые элементы.

1. Общее быстродействие O(n*log(n)). Наиболее быстрая сортировка для неупорядоченных массивов с 50 и более элементами.

2. Требует дополнительной памяти.

3. Неустойчивая.

5. Поведение неестественное.

Метод основан на подходе "Разделяй и властвуй".

Быструю сортировку нетрудно реализовать, она хорошо работает на различных видах входных данных и во многих случаях требует меньше затрат ресурсов по сравнению с другими методами сортировки. На выполнение сортировки N элементов в среднем затрачивается время, пропорциональное N log N и для него характерны исключительно короткие внутренние циклы.

Его недостатком является то, что он неустойчив, для его выполнения в наихудшем случае требуется N2 операций.

Наиболее быстрой является сортировка для неупорядоченных массивов с 50 и более элементами.

Идея метода:

В массиве выбирается опорный элемент a[i], затем сортируемый массив делится на две части, которые затем сортируются независимо друг от друга. Точное положение точки деления зависит от исходного порядка элементов в исходном массиве. Основная идея метода заключается в процессе разбиения массива, который переупорядочивает массив таким образом, что выполняются следующие условия:

1. Элемент a[i] для некоторого i занимает свою окончательную позицию в массиве.

2. Ни один из элементов a[i],..., a[i-l] не превышает a[i].

3. Ни один из элементов a[i+l],..., а[r] не является меньшим a[i].

Разбиение осуществляется с использованием следующей стратегии:

Прежде всего, в качестве разделяющего элемента произвольно выбирается элемент а[r] — он сразу займет свою окончательную позицию. Далее начинается просмотр с левого конца массива, который продолжается до тех пор, пока не будет найден элемент, превосходящий по значению разделяющий элемент. Затем выполняется просмотр, начиная с правого конца массива, который продолжается до тех пор, пока не отыскивается элемент, который по значению меньше разделяющего. Оба элемента, на которых просмотр был прерван, очевидно, находятся не на своих местах в разделенном массиве, и потому они меняются местами. Процесс продолжается до тех пор, пока слева от левого указателя не останется ни одного элемента, который был бы больше по значению разделяющего, и ни одного элемента справа от правого указателя, которые были бы меньше по значению разделяющего элемента.

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

Дата добавления: 2014-01-11