Файл: Алгоритмы сортировки данных.pdf

Перестановка элементов в шейкерной сортировке выполняется аналогично той же в пузырьковой сортировке, т. е. два соседних элемента, при необходимости, меняются местами. Пусть массив требуется упорядочить по возрастанию. Обозначим каждый пройденный путь от начала до конца последовательности через W_i, где i – номер пути; а обратный путь (от конца к началу) через -W_j, где j – номер пути. Тогда после выполнения W_i, один из неустановленных элементов будет помещен в позицию справа, как наибольший из еще неотсортированных элементов, а после выполнения -W_j, наименьший из неотсортированных, переместиться в некоторую позицию слева. Так, например, после выполнения W₁ в конце массива окажется элемент, имеющий наибольшее значение, а после -W₁ в начало отправиться элемент с наименьшим значением.

Анализируя метод пузырьковой сортировки можно отметить два обстоятельства.

• Если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения.
• При движении от конца массива к началу минимальный элемент “всплывает” на первую позицию, а максимальный элемент сдвигается только на одну позицию вправо.

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

Код на С++:

Следующая таблица отражает временную сложность алгоритма шейкерной сортировки для трех случаев.

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

2.6 Гномья сортировка

Гномья сортировка впервые была предложена 2 октября 2000 года Хамидом Сарбази-Азадом (Hamid Sarbazi-Azad). Он назвал ее «Глупая сортировка, простейший алгоритм сортировки всего с одним циклом…». И действительно, глупый этот метод или нет, но в нем задействован, никак в большинстве сортировок – два или более циклов, а только один.

Позже, голландский ученый Дик Грун, на страницах одной из своих книг, привел для гномьей сортировки следующую аналогию:

Гномья сортировка основана на технике, используемой обыкновенным голландским садовым гномом. Вот как садовый гном сортирует ряд цветочных горшков. По существу, он смотрит на два соседних цветочных горшка, если они находятся в правильном порядке, то он переходит на один горшок вперед, иначе он меняет их местами и возвращается на один горшок назад. Граничные условия: если позади нет ни одного горшка – он шагает вперед, а если нет следующего горшка, тогда он закончил.

Так описал основную идею алгоритма гномьей сортировки Дик Грун. Заменим гнома и горшки на более формальные объекты, например на указатель (номер текущего элемента) и элементы массива, и рассмотрим принцип работы алгоритма еще раз.

Вначале указатель ставиться на 1-ой элемент массива. Затем происходит сравнение двух соседних элементов A[i] и A[i-1], т. е. сравниваются первый элемент (i-1) и второй (i). Если те стоят на своих позициях, то сдвигаем указатель на позицию i+1 и продолжаем сравнение с нового положения. Иначе меняем элементы местами, и, поскольку в какой-то момент может оказаться, что элементы в левом подмассиве стоят не на своих местах, сдвигаем указатель на одну позицию влево, осуществляя следующее сравнение с новой позиции. Так алгоритм продолжает выполняться до тех пор, пока весь массив не будет упорядочен.

Здесь следует выделить два важных момента.

• процесс упорядочивания заканчивается, тогда когда не выполняется условие i<n, где n – размер массива
• как было сказано, указатель перемещается как вперед по списку, так и назад, и в том случае если он окажется над первым элементом, его сразу же следует сместить на одну позицию вправо, т. к. в противном случае придется сравнивать два элемента, одного из которых не существует.

Перейдем собственно к коду. На своем сайте Дик Грун выложил следующий листинг:

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

Код на С++:

Кажется немного необычным, тот факт, что алгоритм сортировки использует всего один цикл. Плюс к этому, на практике гномья сортировка не уступает в скорости сортировки вставками.

2.7 Сортировка слиянием

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

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

1. Массив рекурсивно разбивается пополам, и каждая из половин делиться до тех пор, пока размер очередного подмассива не станет равным единице;
2. Далее выполняется операция алгоритма, называемая слиянием. Два единичных массива сливаются в общий результирующий массив, при этом из каждого выбирается меньший элемент (сортировка по возрастанию) и записывается в свободную левую ячейку результирующего массива. После чего из двух результирующих массивов собирается третий общий отсортированный массив, и так далее. В случае если один из массивов закончиться, элементы другого дописываются в собираемый массив;
3. В конце операции слияния, элементы перезаписываются из результирующего массива в исходный.

Основная подпрограмма MergeSort рекурсивно разбивает и сортирует массив, а Merge отвечает за его слияние. Эта подпрограмма выполняется только в том случае, если номер первого элемента меньше номера последнего. Перейдем к рассмотрению последней.

Работа Merge заключается в образовании упорядоченного результирующего массива путем слияния двух также отсортированных массивов меньших размеров.

Разберем алгоритм сортировки слиянием на следующем примере. Имеется неупорядоченная последовательность чисел: 2, 6, 7, 1, 3, 5, 0, 4. После разбивки данной последовательности на единичные массивы, процесс сортирующего слияния (по возрастанию) будет выглядеть так:

Рисунок 3

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

Код на С++:

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

Также, к достоинствам алгоритма стоит отнести его устойчивость и неплохую скорость работы O(n*log n).

Заключение

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

Конкретная методика изучения темы "Алгоритмы сортировки данных", как и вся методика преподавания информатики и программирования, зависит от многих параметров.

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

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

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

В данном курсовом проекте при разработке программы были закреплены навыки объектно-ориентированного программирования на языке С++.

В приложении представлен код программы на языке С++, в которой пользователь может использовать любой вариант сортировки данных, представленных в данном курсовом проекте.

Библиография

1. Дональд Э.Кнут. Искусство программирования, т.3. Сортировка и поиск 2-е изд.: – М.: Издательский дом «Вильямс», 2001. С. 824.
2. Седжвик Роберт. Фундаментальные алгоритмы на С++. Анализ/Структуры данных/Сортировка/Поиск: Пер. с англ./Роберт Седжвик. - СПб.: ООО "ДиаСофтЮП", 2002.-688с
3. Кормен Т., Лейзерсон Ч.И., Ривест Р.Л., Клиффорд Штайн Алгоритмы: построение и анализ. — 2-е изд. — М.: «Вильямс», 2006. — С. 1296.
4. Кнут Д. Искусство программирования для ЭВМ. Т. 3. Сортировка и поиск. - М.: Мир, 1978.
5. Златопольский Д.М. Методы сортировки массивов. - Информатика и образование, 1997, № 10,11,14,16,19,21,22.
6. Шолмов Л.И. Руководство по турбо Си. М.: Наука, 1994. - 94-98с.
7. Уинер Р. Язык Турбо Си: Пер. с англ. - М.: Мир, 1991. - 384 с.
8. Керниган Б.В, Ричи Д. Си для профессионалов. М.: Энергия, 1996. -213 с.
9. Грейд Д. Математическое программирование. М.: Наука, 1987.- 241 с.
10. Либерман М. Алгоритмы сортировки массивов. М.: Наука, 1997. - 43-81с.

Приложение

Код основной программы на С++

#include "stdafx.h"

#include <iostream>

#include <ctime>

using namespace std;

int i, j, n, d, cnt, k = 0, tmp = 0, frst, lst;

const int nQS = 7;

void SelectionSort(int A[], int n1)

{

int count, k;

for (i = 0; i<n1 - 1; i++)

{

count = A[i]; k = i;

for (j = i + 1; j<n1; j++)

if (A[j]<A[k]) k = j;

if (k != i)

{

A[i] = A[k];

A[k] = count;

}

}

cout << "Отсортированный массив: ";

for (i = 0; i<n1; i++) cout << A[i] << " ";

}

void mainSelection()

{

setlocale(LC_ALL, "Rus");

int n1, A[1000];

cout << "Введите количество элементов -"; cin >> n1;

for (i = 0; i<n1; i++)

{

cout << " элемент № " << i + 1; cin >> A[i];

}

SelectionSort(A, n1);

system("pause >> void");

system("cls");

}

void BSort(int A[], int N)

{

for (i = 0; i<N - 1; i++)

{

for (j = 0; j<N - (i + 1); j++)

{

k = j + 1;

cnt = A[k];

if (A[j]>A[k])

{

A[k] = A[j];

A[j] = cnt;

}

}

}

cout << "Отсортированный массив: ";

for (i = 0; i<N; i++) cout << A[i] << " ";

}

void mainBSort()

{

setlocale(LC_ALL, "Rus");

int n; int A[1000];

cout << "Введите количество элементов - "; cin >> n;

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

{

cout << " элемент № " << i + 1; cin >> A[i];

}

BSort(A, n);

system("pause >> void");