Сортировка линейного массива целых чисел различными методами
Методы сортировки (упорядочивания) массивов. Оценка быстродействия алгоритмов различных методов, классификация принципов. Упорядочивание записей и поиск в массиве записи по заданному условию (ключу). Программы, связанные с методами сортировки массивов.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | курсовая работа |
| Язык | русский |
| Дата добавления | 18.07.2012 |
| Размер файла | 51,6 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
30
Нижегородский филиал
Курсовая работа
Программирование на языке высокого уровня
Голикова Никиты Владимировича
Содержание
- Введение
- 1. Алгоритм решения задачи, методы сортировки массивов
- 2. Программы связанные с методами сортировки массивов
- Заключение
- Глоссарий
- Список использованных источников
- Приложения
Введение
Сортировкой или упорядочением массива называется расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке.
Вообще говоря, это большая и сложная тема, в которой известно много различных алгоритмов. Критерии оценки эффективности этих алгоритмов могут включать следующие параметры:
количество шагов алгоритма, необходимых для упорядочения;
количество сравнений элементов;
количество перестановок, выполняемых при сортировке.
Методы сортировки массивов.
При решении задачи сортировки обычно выдвигается требование минимального использования дополнительной памяти, из которого вытекает недопустимость применения дополнительных массивов.
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
количество присваиваний;
количество сравнений.
Все методы сортировки можно разделить на две большие группы:
прямые методы сортировки;
улучшенные методы сортировки.
Прямые методы сортировки по принципу, лежащему в основе метода, в свою очередь разделяются на три подгруппы:
1. сортировка вставкой (включением);
2. сортировка выбором (выделением);
На базе метода прямого включения разработан алгоритм, обеспечивающий значительную производительность сортировки. Мы заметили, что в методе прямого включения, чем больше упорядочен массив, тем меньше операций требуется для его сортировки. При сортировке уже упорядоченного массива трудоемкость имеет линейный порядок. Поэтому имеет смысл попытаться предварительно несколько улучшить порядок элементов в массиве, а затем отсортировать массив методом прямого включения.
Предварительное упорядочивание будем проводить с помощью k - сортировок. Суть k - сортировки заключается в следующем. Массив разбивается на последовательности с шагом k ai, ak+i, a2k+i, …,a [n/k] k+i, i = 1, 2,…,k и сортировка происходит только внутри этих последовательностей.
Обозначим через H последовательность из m возрастающих шагов H = (h1, h2, … hm), где h1=1, h1< h2 < h3 < … < hm
Метод Шелла состоит в последовательном проведении hi-сортировки,
i=m, m-1,…, 1, причем h1=1 гарантирует, что массив будет полностью отсортирован, поскольку 1-сортировка является методом прямого включения.
Эффективность метода зависит от выбора значений шагов. Последовательность значений шагов, которая дает наилучшую трудоемкость, пока неизвестна, метод продолжает исследоваться, но существует и часто используется следующая последовательность шагов, предложенная Кнутом.
1. Алгоритм решения задачи, методы сортировки массивов
Основными операциями Петзольд Ч. Программирование под Windows 95. В двух книгах: BHV - Санкт - Петербург, 2007, silt.,с 124, выполняемыми над массивами, являются упорядочение (сортировка) записей и поиск в массиве записи по заданному условию (по ключу). Сортировка является операцией расстановки записей массива в определенном порядке в соответствии с некоторым критерием упорядочения. Сортировка осуществляется в соответствии со значением ключей всех записей (напр., упорядочение фамилий по алфавиту или чисел по возрастанию). Существует достаточно много методов сортировки, принципиально отличающихся друг от друга. Если массив целиком помещается в оперативной памяти ЭВМ, то его упорядочение называют внутренним. Если для хранения упорядочиваемых данных используются внешнее запоминающее устройство, то такое упорядочение называют внешним. Критериями оценки методов сортировки являются:
С - количество операций сравнения пар ключей
Р - число перестановок элементов,
S - резерв памяти.
Среднее количество операций сравнения зависит от метода сортировки и при рациональном выборе метода достигает некоторого минимума, зависящего от n - размера массива (размер массива - количество содержащихся в нём записей). Методы внутренней сортировки можно разделить на две группы:
методы, не требующие резерва памяти;
методы, требующие резерва памяти.
К первой группе относятся такие методы, как метод выборки, "пузырька", вставки, Шелла. Ко второй группе относятся метод квадратичной выборки, метод слияния и другие. Простые методы сортировки (выбором, обменом, вставкой) требуют приблизительно n**2 сравнений. Более сложные алгоритмы обычно обеспечивают получение результата за n*log2 (n) сравнений в среднем: сортировка методом Шелла, слиянием, "быстрая сортировка". Однако оптимальной в любом случае сортировки не существует, так как их эффективность существенно зависит от типа ключей в массиве и их предварительной упорядоченности.
Рассмотрим алгоритмы наиболее распространенных методов внутренней сортировки (упорядочение выполняется по возрастанию значений ключа).
Метод "Пузырька".
При использовании этого способа требуется самое большее (n-1) проходов. В течение первого прохода массива сравниваются ключи К1 и К2 первой и второй записей, и, если порядок между ними нарушен, то записи R1 и R2 меняются местами. Затем этот процесс повторяется для записей R2 и R3, R3 и R4 и т.д. Данный метод заставляет двигаться, или "всплывать", записи с малыми ключами. После первого прохода запись с наибольшим ключом будет находиться на n - й позиции массива. При каждом последующем проходе записи со следующем наибольшим ключом будут располагаться в позициях n-1, n-2,., 2 соответственно, в результате чего будет сформирована отсортированная таблица. После каждого прохода через массив может быть сделана проверка, были ли совершены перестановки в течение данного прохода. Если перестановок не было, то это означает, что массив уже отсортирован и дальнейших проходов не требуется. Кроме того, можно запоминать индекс последней перестановки. Это позволит уменьшить на следующем шаге просматриваемый массив.
Характеристики сортировки методом "пузырька" в худшем случае составляют n (n-1) /2 сравнений и n (n-1) /2 перестановок (худшим считается случай, когда элементы наиболее удалены от своих конечных позиций). Среднее число сравнений и перестановок имеет порядок n**2. Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой когда каждый пузырек находит свой собственный уровень.
Сортировку пузырьковым методом можно в некоторой степени улучшить и тем самым немного улучшить ее временные характеристики. Можно, например, заметить, что сортировка пузырьковым методом обладает одной особенностью: расположенный не на своем месте в конце массива элемент (например, элемент "а" в массиве "dcab") достигает своего места за один проход, а элемент, расположенный в начале массива (например, элемент "d"), очень медленно достигает своего места. Необязательно все просмотры делать в одном направлении. Вместо этого всякий последующий просмотр можно делать в противоположном направлении. В этом случае сильно удаленные от своего места элементы будут быстро перемещаться в соответствующее место. Хотя эта сортировка является улучшением пузырьковым методом, ее нельзя рекомендовать для использования, поскольку время выполнения по-прежнему зависит квадратично от числа элементов. Число сравнений не изменяется, а число обменов уменьшается лишь на незначительную величину Ричард С.Линкер, Том Арчер. Программирование для Windows 98. Библия разработчика. “Диалектика ” - Москва, 2009.-864 с.: ил.- Парал. тит. англ. Уч.пос.,с 117.
Метод Шелла.
Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами. Сначала сортируются все элементы, которые смещены друг от друга на три позиции. Затем сортируются все элементы, которые смещены на две позиции. И, наконец, упорядочиваются все соседние элементы.
При поверхностном взгляде на алгоритм нельзя сказать, что он дает хороший результат и даже то, что в результате получится отсортированный массив. Однако, он дает и то и другое. Эффективность этого алгоритма объясняется тем, что при каждом проходе используется относительно небольшое число элементов или элементы массива уже находятся в относительном порядке, а упорядоченность увеличивается при каждом новом просмотре данных.
Расстояния между сравниваемыми элементами могут изменяться по-разному. Обязательным является лишь то, что последний шаг должен равняться единице. Например, хорошие результаты дает последовательность шагов 9, 5, 3, 2, 1, которая использована в данной курсовой работе. Следует избегать последовательностей степени двойки, которые, как показывают сложные математические выкладки, снижают эффективность алгоритма сортировки. /Однако, при использовании таких последовательностей шагов между сравниваемыми элементами эта сортировка будет по-прежнему работать правильно. Слегка измененные версии сортировки Шелла используют специальные управляющие элементы, которые не являются в действительности частью той информации, которая должна сортироваться. Управляющие элементы имеют граничные для массива данных значения, т.е. наименьшее и наибольшее значения. В этом случае не обязательно выполнять проверку на граничные значения. Однако, применение таких управляющих элементов требует специальных знаний о той информации, которая сортируется, и это снижает универсальность процедуры сортировки. Анализ сортировки Шелл требует решения некоторых сложных математических задач. Время выполнения сортировки Шелла пропорционально n**1.2 Эта зависимость значительно лучше квадратичной зависимости, которой подчиняются рассмотренные ранее алгоритмы сортировки. Однако, прежде чем вы решите использовать сортировку Шелла, следует иметь в виду, что быстрая сортировка дает даже еще лучшие результаты.
В рассмотренных алгоритмах сортировки запись перемещается каждый раз только на одну позицию. При этом среднее время работы будет в лучшем случае пропорционально n. Методом, существенно превосходящим простые вставки, при котором записи перемещаются большими скачками, является метод Шелла (сортировка с убывающим шагом). Метод состоит в том, что упорядоченный массив разделяется на группы элементов, каждая из которых упорядочивается методом вставки. В процессе упорядочения размеры таких групп увеличиваются до тех пор, пока все элементы массива не войдут в упорядоченную группу. Выбор очередной упорядочиваемой группы и ее расположение внутри массива производятся так, чтобы можно было использовать предшествующую упорядоченность. Группой массива называют последовательность элементов, номера которых образуют арифметическую прогрессию с разностью h (h называют шагом группы). В начале процесса упорядочения выбирается первый шаг группы h1, который зависит от размера таблицы. Шелл предложил брать
h1= [n/2], а hi=h ( (i-1) /2).
В более поздних работах Хиббард показал, что для ускорения процесса целесообразно определить шаг h1 по формуле:
h1=2**k+1, где 2**k < n <= 2** (k+1).
После выбора h1 методом вставки упорядочиваются группы, содержащие элементы с номерами позиций
i, i+h1, i+2*h1,., i+mi*h1.
При этом i=1,2,.,h1; m [i] - наибольшее целое, удовлетворяющее неравенству i+m [i] *hi <= n.
Затем выбирается шаг h2<h1 и упорядочиваются группы, содержащие элементы с номерами позиций i, i+h2,., i+m [i] *h2. Эта процедура со все уменьшающимися шагами продолжается до тех пор, пока очередной шаг h [l] станет равным единице (h1>h2>. >hl). Этот последний этап представляет собой упорядочение всего массива методом вставки. Но так как исходный массив упорядочивался отдельными группами с последовательным объединением этих групп, то общее количество сравнений значительно меньше, чем n /4, требуемое при методе вставки. Число операций сравнения пропорционально n* (log2 (n)) **2.
Обменная сортировка с разделением (Quicksort).
Данный метод является одним из лучших методов внутренней сортировки и весьма эффективен для больших массивов. Целью каждого шага в данном методе является помещение очередной рассматриваемой записи на конечную позицию внутри массива. Если поступать таким способом, то все записи, предшествующие данной, будут иметь меньший ключ, в то время как все последующие - больший. При использовании такого метода массив всегда делится на два подмассива. Анологичный процесс может быть применен к каждому из этих подмассивов и повторяться до тех пор, пока все записи не будут установлены на их конечные позиции. Используются два индекса i и j с начальными значениями границ массива. Сравниваются ключи K [i] и K [j], и если перестановка не требуется, то j уменьшается на 1, и процесс повторяется. В том случае, когда K [i] >=K [j], записи R [i] и R [j] меняются местами. Затем этот процесс повторяется с i, увеличенным на 1, и фиксированным j до тех пор, пока не возникает другая перестановка. В этот момент j снова будет уменьшено на 1, а i останется фиксированным, и т.д. Процесс выполняется до тех пор, пока i<j.
Каждый раз массив разбивается на два подмассива, один из которых обрабатывается, в то время как границы второго запоминаются с тем, чтобы он был обработан позже. В этих целях может быть использован стек, представляющий собой матрицу из двух столбцов. В первом столбце хранятся нижние границы разделяемых подмассивов, во втором - верхние границы. Всякий раз один из полученных в результате разделения подмассивов подвергается дальнейшему разделению, а границы другого помещаются в свободную строку стека (обычно в стек помещаются границы большего по длине массива Джесс Либерти. С++ за 21 день. ”Вильямс” - Москва, 2007. ил. - Парал.тит. англ.,213 с., поскольку это уменьшает требуемый размер стека). Как только завершается процесс разделения текущего подмассива, т.е. ее длина станет меньше трех, для разделения берется подмассив, границы которого были занесены в стек последними. Строка стека, в которой хранились эти границы, освобождается. Процесс упорядочения завершается, когда стек полностью освобождается.
Разделение следует применять для подмассивов, длина которых больше 9, а короткие подмассивы упорядочивать методом вставки.
Стек занимает мало места. Например, стек из 20 строк позволяет упорядочить массив, содержащую до 10**7 записей. Кроме того, в современных языках программирования при работе рекурсивных программ занесение и извлечение из стека выполняется автоматически, поэтому рекомендуется использовать именно этот механизм. Среднее число сравнений для данного алгоритма составляет n*log (n) где n - число записей в сортируемом массиве, m - размер подмассива, сортируемой методом вставки.
Наихудшей ситуацией при использовании рассмотренного алгоритма является случай, когда массив уже отсортирован. При этом число сравнений порядка n, т.е. алгоритм не лучше сортировки выборкой.
Сортировка вставками
Второй метод называется метод вставок., т.к. на j-ом этапе мы "вставляем" j-ый элемент M [j] в нужную позицию среди элементов M [1], M [2],., M [j-1], которые уже упорядочены. После этой вставки первые j элементов массива M будут упорядочены.
Чтобы сделать процесс перемещения элемента M [j], более простым, полезно воспользоваться барьером: ввести "фиктивный" элемент M [0], чье значение будет заведомо меньше значения любого из "реальных"элементов массива (как это можно сделать?). Мы обозначим это значение через - оо.
Если барьер не использовать, то перед вставкой M [j], в позицию i-1 надо проверить, не будет ли i=1. Если нет, тогда сравнить M [j] (который в этот момент будет находиться в позиции i) с элементом M [i-1].
Описанный алгоритм имеет следующий вид:
begin
M [0]: = - oo;
for j: =2 to N do
begin
i: = j;
while M [i] < M [i-1] do
begin
swap (M [i],M [i-1]);
i: = i-1
end
end
end;
Процедура swap нам уже встречалась.
Демонстрация сортировки вставками.
Сортировка посредством выбора
Идея сортировки с помощью выбора не сложнее двух предыдущих.
На j-ом этапе выбирается элемент наименьший среди M [j], M [j+1],., M [N] (см. процедуру FindMin) и меняется местами Дэвид Дж. Круглински. Основы С++. “Русская редакция” - Москва, 2007.- .: ил.176 с. с элементом M [j]. В результате после j-го этапа все элементы M [j], M [j+1],., M [N] будут упорядочены.
Сказанное можно описать следующим образом:
нц для j от 1 до N-1
выбрать среди M [j],., M [N] наименьший элемент и
поменять его местами с M [j]
кц
Более точно: begin
for j: =1 to N-1 do
begin
FindMin (j, i);
swap (M [j],M [i])
end
end;
В программе, как уже было сказано, используется процедура FindMin, вычисляющая индекс lowindex элемента, наименьшего среди элементов массива с индексами не меньше, чем startindex:
procedure FindMin (startindex: integer; var lowindex: integer);
var lowelem:.;
u: integer;
begin
lowindex: = startindex;
lowelem: = M [startindex];
for u: =startindex+1 to N do
if M [u] < lowelem then
begin
lowelem: = M [u];
lowindex: = u
end
end;
2. Программы, связанные с методами сортировки массивов
Обычная сортировка методом "пузырька"
var
l, m, mi, d: integer;
mWin: array [0.8] of integer;
begin
Randomize;
for l: = 0 to 8 do
mWin [l]: = Random (100);
for l: = 0 to 7 do // последний элемент не считаем - он уже будет
// стоять на своем месте
begin
d: = 0;
mi: = 0; // ищем максимальный элемент
for m: = l to 8 do
if mWin [m] > mi then
begin
mi: = mWin [m];
d: = m; // находим позицию максимального элемента массива
end;
mi: = mWin [l]; // текущий сохраняем
mWin [l]: = mWin [d]; // вставляем максимальный
mWin [d]: = mi; // текущий переставляем на свободное место
end;
end; // все
// Сортировка методом пузырька
procedure SortList (lbNum: TStrings);
var
i, j, b_val, b_j: integer;
begin
if lbNum. Count > 1 then
for i: = 0 to lbNum. Count - 2 do
begin
b_val: = StrToInt (lbNum [i]);
b_j: = i;
for j: = i + 1 to lbNum. Count - 1 do
begin
if StrToInt (lbNum [j]) < b_val then
begin
b_val: = StrToInt (lbNum [j]);
b_j: = j;
end;
end;
lbNum [b_j]: = lbNum [i];
lbNum [i]: = IntToStr (b_val);
end;
end;
// Пример использования
procedure TForm1. Button1Click (Sender: TObject);
begin
SortList (ListBox1. Items);
end;
Сортировка Шелла
void sort (one_elem mas [], int num) {
int stp [4] ={9,5,3,1} // Шаги сортировки
int fs,mn,p; // Первый, минимальный и текущий элементы
int n; // Счетчик
one_elem prm; // Временная переменная
// Цикл сортировки
for (n=0; n<4; n++) {
fs=0; // Начинать сортировать с начала
// Перебор всего массива
while (fs<num) {
// Поиск минимального элемента
p=fs;
mn=fs;
while (p<num) {
if (mas [p]. n<mas [mn]. n) mn=p;
p+=stp [n];
}
// Если минимальный элемент отличается от начального, поменять их местами
if (mn>fs) {
prm. n=mas [mn]. n;
strcpy (prm. st,mas [mn]. st);
mas [mn]. n=mas [fs]. n;
strcpy (mas [mn]. st,mas [fs]. st);
mas [fs]. n=prm. n;
strcpy (mas [fs]. st,prm. st);
}
fs+=stp [n]; // Переход к следующему элементу
}
}
}
// Основная программа
void main () {
one_elem mas [100]; // Массив
int num; // Количество элементов
int st; // Выбранный пункт меню
textbackground (0);
textcolor (15);
clrscr ();
do {
// Вывод меню
st=menu (30,5," Ввод данных "
" Добавление данных "
" Вывод данных "
" Сортировка Шелла "
" Выход из программы "
"x0");
textbackground (0);
textcolor (15);
// Выполнение действий в зависимости от выбранного пункта
switch (st) {
// Ввод данных
case (0):
num=input (mas,0);
break;
// Добавление данных
case (1):
num+=input (mas,num);
break;
// Вывод массива
case (2):
output (mas,num);
break;
// Сортировка
case (3):
sort (mas,num);
break;
}
// Выход по ESC или последнему пункту
} while ( (st<4) && (st! =-1));
clrscr ();
}
Метод пузырька
Расположим массив сверху вниз, от нулевого элемента - к последнему.
Идея метода: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.
После нулевого прохода по массиву "вверху" оказывается самый "легкий" элемент - отсюда аналогия с пузырьком. Следующий проход делается до второго сверху элемента, таким образом второй по величине элемент поднимается на правильную позицию.
Делаем проходы по все уменьшающейся нижней части массива до тех пор, пока в ней не останется только один элемент. На этом сортировка заканчивается, так как последовательность упорядочена по возрастанию.
template<class T>
void bubbleSort (T a [], long size) {
long i, j;
T x;
for (i=0; i < size; i++) { // i - номер прохода
for (j = size-1; j > i; j--) { // внутренний цикл прохода
if (a [j-1] > a [j]) {
x=a [j-1]; a [j-1] =a [j]; a [j] =x;
}
}
}
}
Среднее число сравнений и обменов имеют квадратичный порядок роста: Theta (n2), отсюда можно заключить, что алгоритм пузырька очень медленен и малоэффективен.
Тем не менее, у него есть громадный плюс: он прост и его можно по-всякому улучшать. Чем мы сейчас и займемся.
Во-первых, рассмотрим ситуацию, когда на каком-либо из проходов не произошло ни одного обмена. Что это значит?
Это значит, что все пары расположены в правильном порядке, так что массив уже отсортирован. И продолжать процесс не имеет смысла (особенно, если массив был отсортирован с самого начала!).
Итак, первое улучшение алгоритма заключается в запоминании, производился ли на данном проходе какой-либо обмен. Если нет - алгоритм заканчивает работу.
Процесс улучшения можно продолжить, если запоминать не только сам факт обмена, но и индекс последнего обмена k. Действительно: все пары соседих элементов с индексами, меньшими k, уже расположены в нужном порядке. Дальнейшие проходы можно заканчивать на индексе k, вместо того чтобы двигаться до установленной заранее верхней границы i.
Качественно другое улучшение алгоритма можно получить из следующего наблюдения. Хотя легкий пузырек снизу поднимется наверх за один проход, тяжелые пузырьки опускаются со минимальной скоростью: один шаг за итерацию. Так что массив 2 3 4 5 6 1 будет отсортирован за 1 проход, а сортировка последовательности 6 1 2 3 4 5 потребует 5 проходов.
сортировка программа линейный массив
Чтобы избежать подобного эффекта, можно менять направление следующих один за другим проходов. Получившийся алгоритм иногда называют "шейкер-сортировкой".
template<class T>
void shakerSort (T a [], long size) {
long j, k = size-1;
long lb=1, ub = size-1; // границы неотсортированной части массива
T x;
do {
// проход снизу вверх
for (j=ub; j>0; j--) {
if (a [j-1] > a [j]) {
x=a [j-1]; a [j-1] =a [j]; a [j] =x;
k=j;
}
}
lb = k+1;
// проход сверху вниз
for (j=1; j<=ub; j++) {
if (a [j-1] > a [j]) {
x=a [j-1]; a [j-1] =a [j]; a [j] =x;
k=j;
}
}
ub = k-1;
} while (lb < ub);
}
Насколько описанные изменения повлияли на эффективность метода? Среднее количество сравнений, хоть и уменьшилось, но остается O (n2), в то время как число обменов не поменялось вообще никак. Среднее (оно же худшее) количество операций остается квадратичным.
Дополнительная память, очевидно, не требуется. Поведение усовершенствованного (но не начального) метода довольно естественное, почти отсортированный массив будет отсортирован намного быстрее случайного. Сортировка пузырьком Кэйт Грегори. Использование Visual C++. “Вильямс” - Москва, 2009.: ил.. - Парал.тит. англ., уч. Пос, с.431 устойчива, однако шейкер-сортировка утрачивает это качество.
На практике метод пузырька, даже с улучшениями, работает, увы, слишком медленно. А потому - почти не применяется.
Метод Шелла
На базе метода прямого включения разработан алгоритм, обеспечивающий значительную производительность сортировки. Мы заметили, что в методе прямого включения, чем больше упорядочен массив, тем меньше операций требуется для его сортировки. При сортировке уже упорядоченного массива трудоемкость имеет линейный порядок. Поэтому имеет смысл попытаться предварительно несколько улучшить порядок элементов в массиве, а затем отсортировать массив методом прямого включения.
Предварительное упорядочивание будем проводить с помощью k - сортировок. Суть k - сортировки заключается в следующем. Массив разбивается на последовательности с шагом k
ai, ak+i, a2k+i, …,a [n/k] k+i, i = 1, 2,…,k
и сортировка происходит только внутри этих последовательностей.
Обозначим через H последовательность из m возрастающих шагов
H = (h1, h2, … hm), где h1=1, h1< h2 < h3 < … < hm
Метод Шелла состоит в последовательном проведении hi-сортировки, i=m, m-1,…, 1, причем h1=1 гарантирует, что массив будет полностью отсортирован, поскольку 1-сортировка является методом прямого включения.
Сортировка Шелла является довольно интересной модификацией алгоритма сортировки простыми вставками.
Рассмотрим следующий алгоритм сортировки массива a [0]. a [15].
1. Вначале сортируем простыми вставками каждые 8 групп из 2-х элементов (a [0], a [8 [), (a [1], a [9]),., (a [7], a [15]).
2. Потом сортируем каждую из четырех групп по 4 элемента (a [0], a [4], a [8], a [12]),., (a [3], a [7], a [11], a [15]).
В нулевой группе будут элементы 4, 12, 13, 18, в первой - 3, 5, 8, 9 и т.п.
3. Далее сортируем 2 группы по 8 элементов, начиная с (a [0], a [2], a [4], a [6], a [8], a [10], a [12], a [14]).
4. В конце сортируем вставками все 16 элементов.
Очевидно, лишь последняя сортировка необходима, чтобы расположить все элементы по своим местам. Так зачем нужны остальные?
Hа самом деле они продвигают элементы максимально близко к соответствующим позициям, так что в последней стадии число перемещений будет весьма невелико. Последовательность и так почти отсортирована. Ускорение подтверждено многочисленными исследованиями и на практике оказывается довольно существенным.
Единственной характеристикой сортировки Шелла является приращение - расстояние между сортируемыми элементами, в зависимости от прохода. В конце приращение всегда равно единице - метод завершается обычной сортировкой вставками, но именно последовательность приращений определяет рост эффективности.
Использованный в примере набор., 8, 4, 2, 1 - неплохой выбор, особенно, когда количество элементов - степень двойки. Однако гораздо лучший вариант предложил Р. Седжвик. Его последовательность имеет вид
При использовании таких приращений среднее количество операций: O (n7/6), в худшем случае - порядка O (n4/3).
Обратим внимание на то, что последовательность вычисляется в порядке Немнюгин С.А. Turbo Pascal:практикум-2 издание,пер.и доп.-СПб:Питер 2007,с 45, противоположном используемому: inc [0] = 1, inc [1] = 5,. Формула дает сначала меньшие числа, затем все большие и большие, в то время как расстояние между сортируемыми элементами, наоборот, должно уменьшаться. Поэтому массив приращений inc вычисляется перед запуском собственно сортировки до максимального расстояния между элементами, которое будет первым шагом в сортировке Шелла. Потом его значения используются в обратном порядке.
Заключение
В ходе выполнения данного курсового проекта были разработана программа на языке высокого уровня Visual C++. А также изучены возможности данного языка.
Систематизированы и закреплены практические навыки использования ЭВМ Попов В.Б.Паскаль и Дельфи:самоучитель,-СПб:Птиер 2005,с 35, программного обеспечения, существующих средств обслуживания системных программистов, а также теоретические знания по основным разделам курса "Объектно-ориентированного программирования". Основное внимание уделено изучению современных методов защиты информации, способов проектирования приложений, объектно-ориентированному и системному программированию.
При выполнении курсового проекта произведено знакомство с реферативными журналами и другими информационными источниками по объектно-ориентированному и системному программированию с целью анализа состояния решаемой задачи.
Получены практические навыки работы в среде Visual C++.
Модификация сортировки простыми вставками.
Шаг 1. Упорядочиваемое множество разбивается на несколько непересекающихся подмножеств по следующему правилу:
берутся элементы неупорядоченного множества, расположенные на одинаковом расстоянии (дистанции) друг от друга. Полученные множества сортируются методом простых вставок, что позволяет уменьшить общую неупорядоченность множества.
Шаг 2. Алгоритм завершает работу, когда дистанция равна 1, иначе уменьшается дистанция между элементами и повторяется шаг 1.
Примечание:
Выбор последовательности дистанций между элементами в сортировке методом Шелла является отдельной проблемой, которая подробно рассматривается Д. Кнутом в монографии "Искусство программирования для ЭВМ. Т.3: Сортировка и поиск”.
Характеристики алгоритма:
Эффективный алгоритм для почти упорядоченного множества.
Эффективный алгоритм для небольшого количества элементов.
Устойчивая сортировка.
Интересно поведение этого алгоритма в зависимости от выбора значения дистанции.
Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, "всплывает" до нужной позиции как пузырёк в воде, отсюда и название алгоритма.
Булевая переменная t используется для того, чтобы определить, был ли произведён хотя бы один обмен на очередной итерации внешнего цикла. Алгоритм останавливается, когда таких обменов не было.
Можно показать, что для сортировки требуется сделать не более n ? 1 итераций внешнего цикла, поэтому в некоторых реализациях внешний цикл всегда выполняется ровно n ? 1 или n раз, и не отслеживается, были ли обмены или нет на каждой итерации.
Глоссарий
|
№ n/n |
Новое понятие |
Содержание |
|
|
1 |
Длина записей |
совместно с их количеством позволяет оценить необходимый для сортировки объем оперативной памяти. При сортировке записей, имеющих большую длину |
|
|
2 |
Кососимметрическая матрица |
квадратная матрица аik, где аik действительные числа, в которой любые два элемента, симметрично расположенные относительно главной диагонали, равны по абсолютной величине и противоположны по знаку: аik aki; следовательно, аii… |
|
|
3 |
Логика поиска |
задает словесное, содержательное описание задачи поиска, определяет вид аргумента поиска, устанавливает критерии выдачи. Логика поиска не зависит от особенностей организации информационных массивов в памяти, от типа и конфигурации ЭВМ |
|
|
4 |
Магический квадрат |
квадратная МАТРИЦА, разделенная на клетки и заполненная числами или буквами определенным образом, фиксирующим особую магическую ситуацию. Самый распространенный квадрат с буквами - это SATOR, составленный из слов SATOR,… |
|
|
5 |
Метод вставок |
упорядоченная последовательность соз- дается на свободном участке памяти, который выделяется под длину отсортированного массива записей. |
|
|
6 |
Метод Пузырька |
шаг сортировки состоит в проходе снизу вверх по массиву |
|
|
7 |
Метод Шелла |
Общий метод, который использует сортировку вставкой, применяет принцип уменьшения расстояния между сравниваемыми элементами |
|
|
8 |
Неособенная матрица |
в математике, квадратная матрица А IIaijII1 порядка, определитель А которой не равен нулю. Всякая Н. м. имеет обратную матрицу.Н. м. определяет в - мерном пространстве невырожденное Линейное преобразование |
|
|
9 |
Симметрическая матрица |
квадратная матрица aik, в которой любые два элемента, симметрично расположенные относительно главной диагонали, равны между собой: aik aki. … |
|
|
10 |
Сортировка или Упорядочением массива |
расположение его элементов по возрастанию (или убыванию). Если не все элементы различны, то надо говорить о неубывающем (или невозрастающем) порядке |
Список использованных источников
1. Бетзольд Ч. Программирование под Windows 95. В двух книгах: BHV - Санкт - Петербург, 2007, silt.,443 с.
2. Вильямс С. Линкер, Том Арчер. Программирование для Windows 98. Библия разработчика. "Диалектика ” - Москва, 2009.: ил. - Парал. тит. англ. Уч. пос.,332 с.
3. Джесс Либерти. С++ за 21 день. ”Вильямс” - Москва, 2007.: ил. - Парал. тит. англ.,816 с.
4. Дэвид Дж. Круглински. Основы С++. "Русская редакция” - Москва, 2007. - 696 с.
5. Кэйт Грегори. Использование Visual C++. "Вильямс" - Москва, 2009.: ил. - Парал. тит. англ., уч. пос.,864 с.
6. Немнюгин С.А. Turbo Pascal: практикум-2 издание, пер. и доп. - СПб: Питер 2007,45 с.
7. Попов В.Б. Паскаль и Дельфи: самоучитель,-СПб: Питер 2005,119 с.
8. Фаронов В.В. Delphi 2005 Программирование на языке высокого уровня: учебник для вузов-CПб: Питер 2007,112 с.
9. Чеснокова О.В. Алгоритмы и программы. Учимся программировать-СПб: Питер 2008, 43 с.
10. Бетз/ольд Ч. Программирование под Windows 95. В двух книгах: BHV - Санкт - Петербург, 2007, silt.,443 с.
Приложения
Приложение А
Описанный алгоритм имеет следующий вид: begin
M [0]: = - oo;
for j: =2 to N do
begin
i: = j;
while M [i] < M [i-1] do
begin
swap (M [i],M [i-1]);
i: = i-1
end
end
end;
Приложение Б
Можно использовать самые разные схемы выбора шагов. Как правило, сначала мы сортируем массив с большим шагом, затем уменьшаем шаг и повторяем сортировку. В самом конце сортируем с шагом 1. Хотя этот метод легко объяснить, его формальный анализ довольно труден. В частности, теоретикам не удалось найти оптимальную схему выбора шагов. Кнут [1] провел множество экспериментов и следующую формулу выбора шагов (h) для массива длины N:
в последовательности
h1 = 1, hs + 1 = 3hs + 1,. взять ht, если ht + 2 і N.
Вот несколько первых значений h:
h1=1 h2= (3x1) +1=4 h3= (3x4) +1=13 h4= (3x13) +1=40 h5 = (3 x 40) + 1 = 121
Чтобы отсортировать массив длиной 100, прежде всего найдем номер s, для которого hs і 100. Согласно приведенным цифрам, s = 5. Нужное нам значение находится двумя строчками выше. Таким образом, последовательность шагов при сортировке будет такой: 13-4-1. Ну, конечно, нам не нужно хранить эту последовательность: очередное значение h находится из предыдущего по формуле
hs - 1 = | hs / 3 |
Размещено на Allbest.ru
Подобные документы
Анализ основных алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Сортировка пузырьком, методами вставок, выбора, методом Шелла, быстрая сортировка. Операция разделения массива внутренней сортировки.
курсовая работа [161,7 K], добавлен 17.12.2015Изучение алгоритмов внутренней сортировки массивов данных, сравнение сложности их реализации и производительности. Отличительные черты сортировки включением, выбором, разделением, сортировки Шелла, обменной сортировки. Сравнение методов: плюсы и минусы.
курсовая работа [203,8 K], добавлен 03.12.2010Краткое описание языка программирования С++. Алгоритм линейного выбора элемента, методов минимального (максимального) элемента и челночной сортировки. Анализ и разработка приложения, организующего сортировку массива данных пятью методами сортировки.
реферат [614,8 K], добавлен 12.04.2014Реализация различных методов сортировки. Алгоритмические языки программирования. Обработка большого числа единообразно организованных данных. Алгоритмы сортировки массивов. Анализ проблем реализации и использования различных видов сортировок массивов.
курсовая работа [640,3 K], добавлен 07.07.2011Разработка программы для осуществления сортировки данных методами "Выбора" с использованием языка C# и Visual Studio 2012. Плавный метод сортировки. Основные фазы сортировки во внутреннем представлении пирамиды. Программа сортировки методами выбора.
курсовая работа [637,6 K], добавлен 29.11.2014Обработка массивов элементов любого типа как главное назначение алгоритмов сортировки. Анализ наиболее используемых алгоритмов сортировки: пузырьком, выбором, вставками, методом Шелла и быстрой сортировкой. Основные требования к алгоритмам сортировки.
реферат [189,8 K], добавлен 06.12.2014Сущность и порядок реализации простых методов сортировки при составлении программного алгоритма, их классификация и разновидности, отличительные признаки, характерные свойства. Особенности алгоритмов для сортировки файлов записей, содержащих ключи.
реферат [20,7 K], добавлен 20.05.2010Понятие алгоритма и сортировки. Способы и алгоритмы сортировки массивов. Быстрая сортировка Хоара. Описание алгоритма "быстрой сортировки". Реализация на языке программирования. Анализ наихудшего разбиения. Вероятностные алгоритмы быстрой сортировки.
курсовая работа [291,5 K], добавлен 22.03.2012Алгоритм по обработке массивов таким образом, чтобы группы, состоящие из трех или более подряд стоящих нулей, были переписаны в начало массива. Сортировка полученных массивов методом всплывающего пузырька. Вывод на дисплей монитора обновленной матрицы.
курсовая работа [300,1 K], добавлен 30.08.2011Широкое использование компьютерных и информационных технологий. Концепции типов данных. Алгоритмы сортировки одномерных массивов. Описание двумерного массива Паскаля. Методы доступа к элементам массивов. Индексные, динамические и гетерогенные массивы.
курсовая работа [66,3 K], добавлен 07.12.2010
