Файл: Алгоритмы сортировки данных (Выбор языка программирования).pdf

1.2 Алгоритм сортировки простым включением.

Данный метод, в основном, применяют играющие в карты. Элементы (карты) условно делятся на готовую конкретную последовательность и входную последовательность . Постоянно на следующем шаге, считая с I = 2 и увеличивая i на один, берется i-й элемент входной последовательности и перекладывается в готовую последовательность, ставя его на нужное место(Табл.1).

Табл.1. Карта с пояснениями работы алгоритма включением

При поиске нужного места можно чередовать сравнения и пересылки, таким образом, как бы «просеивать» x, сравнивая его со следующим элементом и или вставляя x, или перенаправляя направо и двигаясь налево. «Просеивание» можно закончить при двух разных условиях:

1. Найден элемент ключ, которого меньше, чем ключ x.

2. Достигли левого конца готовой последовательности.

Данный стандартный образец цикла с количеством двух условий окончания предоставляет возможность исследовать всем знакомый способ фиктивного элемента («барьера»). Он легко используется в этом случае, если установить барьер .

for (int i = 1; i < arr.Length; i++)

{

int tmp = arr[i];

int j;

for (j = i - 1; j >= 0 && arr[j] > tmp; j--)

arr[j + 1] = arr[j];

arr[j + 1] = tmp;

}

Анализ сортировки простыми включениями. Значение сравнений ключей на i-м просеивании будет наибольшим i-1, и наименьшим 1 если допустить, что у всех переводов n ключей равная вероятность, в среднем равная i/2. Число пересылок (присваиваний) рассчитывается, как (с учетом барьера). Таким образом, итоговое значений сравнений и пересылок рассчитывается следующим образом:

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

Алгоритм сортировки простыми включениями легко улучшить, применяя то, что готовая последовательность, куда надо внести очередной элемент, к тому моменту также упорядочена. Поэтому место включения определяется более быстро. Понятно, что тут можно применить бинарный поиск, который исследует средний элемент готовой последовательности и ведёт деление пополам до момента, когда будет найдено место включения. Усовершенствованный алгоритм сортировки по другому определяют сортировкой бинарными включениями.

Анализ сортировки бинарными включениями. В целом число сравнений не очень зависит от исходного порядка элементов. Тем не менее из-за округления в момент деления диапазона поиска надвое настоящее число сравнений для i элементов получается иногда на 1 больше, чем ждали. Причина этого «перекоса» заключается в следующем: места включения в нижней части рассчитываются в среднем немного быстрее, чем в верхней части. Поэтому из этого получается преимущество тогда, когда элементы с самого начала находятся далеко от правильного порядка. На самом деле же наименьшее значение сравнений надо будет, когда элементы с самого начала расположены в обратном порядке, а наибольшее число сравнений – в случае, когда они уже упорядочены. Соответственно, это случай необычного выражения алгоритма сортировки

С = n (Log(n) – Log(e) ± 0,5).

Усовершенствование, получаемое нами при применении метода бинарного поиска, касается только числа сравнений, а не числа необходимых пересылок. На самом деле перестановка элементов, т.е. ключей и соответствующей информации, в основном требует поболее времени, чем сравнение двух ключей. Это улучшение никоим образом не есть решающее: важнейший показатель М по-прежнему остается . И в самом деле, для пересортировки уже отсортированного массива нужно больше времени, чем для сортировки простыми включениями со следующим поиском! Получше результаты могут быть от метода, если пересылки элементов применяются лишь для единичных элементов и на большие расстояния. Этот момент обращает внимание к сортировке выбором.

1.3 Алгоритм сортировки простым выбором.

алгоритм сортировка программирование поиск

Этот метод включает следующие условия:

1. Определяется элемент с самым маленьким ключом.

2. Выбранный элемент меняется расположением с первым элементом а[1].

Эти операции затем повторяются с прочими n - 1 элементами, затем c n - 2 элементами, до тех пор, пока в остатке не будет только один элемент – наибольший(табл.2).

Табл.2. Карта с пояснениями работы алгоритма выбором

Этот метод, называемый часто сортировкой простым выбором, в каком-то смысле противоположен сортировке простыми вставками; сортировка простыми вставками при следующем каждом шаге засчитывает лишь один следующий в текущий момент элемент входной последовательности и все элементы готового массива для расчета места включения; сортировка простым выбором ведет учёт всех элементов входного массива, чтобы определить элемент с самым маленьким ключом, и данный один очередной элемент направляется в готовую последовательность. В целом алгоритм сортировки простым выбором отражается в следующем виде:

int tmp;

for (int i = 0; i < arr.Length; ++i)

{

int pos = i;

tmp = arr[i];

for (int j = i + 1; j < arr.Length; ++j)

{

if (arr[j] < tmp)

{

pos = j;

tmp = arr[j];

}

}

arr[pos] = arr[i];

arr[i] = tmp;

}

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

Наименьшее значение присваиваний равно когда с самого начала упорядочены ключи и равно наибольшему значению когда изначально ключи выстроены в обратном порядке. Усредненное у Д. Кнута определено в виде , при этом =0,577216… (константа Эйлера).

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

1.4 Алгоритм сортировки простым обменом.

Группировка способов сортировки не имеет ясного и однозначного определения. Два представленных выше способа при желании можно определить в качестве сортировки обменом. Тем не менее, есть метод, при применении которого взаимообмен двух элементов есть основная характеристика процесса. Рассмотренный далее алгоритм сортировки простым обменом базируется на основе сравнивания и обмена двух рядом стоящих элементов до момента, когда не будут отсортированы все элементы.

Так же, как и в рассмотренных способах простого выбора, совершаются повторяющиеся переходы по массиву, всякий раз определяя самый маленький элемент оставшегося множества, продвигаясь к левому краю массива. В случае, когда для разнообразия рассматривать массив, находящийся вертикально, а не горизонтально, и с помощью доли воображения представить себе элементы пузырьками в чане с водой, имеющими «веса», соответствующие их ключам, то тогда очередной переход по массиву приведет к «всплыванию» пузырька на уровень, который соответствует его весу. Такой метод всем знаком в качестве сортировки методом пузырька(табл.3).

int i, j;

int x;

for (i = 0; i < arr.Length; i++)

{

for (j = arr.Length - 1; j > i; j--)

{

if(arr[j-1]>arr[j]){

x=arr[j-1];

arr[j-1]=arr[j];

arr[j]=x;

}

}

}

return arr;

Табл.3. Карта с пояснениями работы алгоритма обменом

Данный алгоритм нетрудно оптимизировать. Данный пример демонстрирует, что три последних прохода никоим образом не оказывают влияния на распорядок элементов, так как они уже отсортированы. Простой способ усовершенствовать этот алгоритм в том, что надо запоминать, был ли на этом проходе какой-нибудь обмен. В случае отрицательного ответа, это значит, что алгоритм может закрыть процесс. Эту процедуру улучшения возможно продолжить, в случае запоминания не только самого факта обмена, но и места (индекса) последнего обмена. Очевидно, что все пары соседcтвующих элементов имеют индексы, которые меньше данного индекса k, уже находятся в необходимом порядке. Соответственно последующие переходы можно окончить на данном индексе, чем двигаться до определенного ранее нижнего уровня i. Тем не менее, если внимательней посмотреть, то тогда возможно отметить необычную асимметрию: один не там, где нужно находящийся «пузырек» в «тяжелом» краю отсортированного массива всплывет на нужное место за один переход, а не там, где нужно, находящийся «пузырек» в «легком» краю опускается на нужное место всего лишь на один шаг на каждом переходе.

К примеру, массив

1218424455679406

будет отсортирован с помощью метода пузырька за один переход, а рассортировать массив

9406121842445567

придется за семь переходов. Эта необычная асимметрия наводит на третье усовершенствование: поменять направление чередующих один за другим переходов. Представленный таким образом алгоритм часто называют шейкер-сортировкой(табл.4).

Табл.4. Карта с пояснениями работы шейкерной сортировки

int b = 0, prm = 0;

int left = 0;

int right = arr.Length - 1;

while (left < right)

{

for (int i = left; i < right; i++)

{

if (arr[i] > arr[i + 1])

{

b = arr[i];

arr[i] = arr[i + 1];

arr[i + 1] = b;

b = i;

prm++;

}

}

right = b;

if (left >= right) break;

for (int i = right; i > left; i--)