Методы сортировки документов. Алгоритм "Сортировка выбором". Алгортим "Быстрая сортировка"
В статье рассмотрены одни из самых популярных алгоритмов сортировки для массивов, применяемых как практически, так и в учебных целях. Сразу хочу оговориться, что все рассмотренные алгоритмы медленнее, чем метод классической сортировки массива через список значений, но тем не менее, заслуживают внимания. Текста получается много, поэтому по каждому алгоритму описываю самое основное.
1.Алгоритм "Сортировка выбором".
Является одним из самых простых алгоритмов сортировки массива. Смысл в том, чтобы идти по массиву и каждый раз искать минимальный элемент массива, обменивая его с начальным элементом неотсортированной части массива. На небольших массивах может оказаться даже эффективнее, чем более сложные алгоритмы сортировки, но в любом случае проигрывает на больших массивах. Число обменов элементов по сравнению с "пузырьковым" алгоритмом N/2, где N - число элементов массива.
Алгоритм:
1. Находим минимальный элемент в массиве.
2. Меняем местами минимальный и первый элемент местами.
3. Опять ищем минимальный элемент в неотсортированной части массива
4. Меняем местами уже второй элемент массива и минимальный найденный, потому как первый элемент массива является отсортированной частью.
5. Ищем минимальные значения и меняем местами элементы,пока массив не будет отсортирован до конца.
//Сортировка выбором {--- Функция СортировкаВыбором(Знач Массив) Мин = 0; Для i = 0 По Массив.ВГраница() Цикл Мин = i; Для j = i + 1 ПО Массив.ВГраница() Цикл //Ищем минимальный элемент в массиве Если Массив[j] < Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции
2.Алгоритм "Сортировка пузырьком".
Пожалуй самый известный алгоритм, применяемый в учебных целях, для практического же применения является слишком медленным. Алгоритм лежит в основе более сложных алгоритмов: "Шейкерная сортировка", "Пирамидальная сортировка", "Быстрая сортировка". Примечательно то, что один из самых быстрых алгоритмов "Быстрый алгоритм" был разработан путем модернизации одного из самых худших алгоритмов "Сортировки пузырьком"."Быстрая" и "Шейкерная" сортировки будут рассмотрены далее. Смысл алгоритма заключается в том, что самые "легкие" элементы массива как бы "всплывают" , а самые "тяжелые" "тонут". Отсюда и название "Сортировка пузырьком"
Алгоритм:
1. Каждый элемент массива сравнивается с последующим и если элемент[i] > элемент происходит замена. Таким образом самые "легкие" элементы "всплывают" - перемещаются к началу списка,а самые тяжелые "тонут" - перемещаются к концу.
2. Повторяем Шаг 1 n-1 раз, где n - Массив.Количество ().
//Сортировка пузырьком {--- Функция СортировкаПузырьком(Знач Массив) Для i = 0 По Массив.ВГраница() Цикл Для j = 0 ПО Массив.Вграница() - i - 1 Цикл Если Массив[j] > Массив Тогда Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; КонецЕсли; КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}
3.Алгоритм "Шейкерная сортировка"(Сортировка перемешиванием,Двунаправленная пузырьковая сортировка).
Алгоритм представляет собой одну из версий предыдущей сортировки - "сортировки пузырьком". Главное отличие в том, что в классической сортировке пузырьком происходит однонаправленное движение элементов снизу - вверх, то в шейкерной сортировке сначало происходит движение снизу-вверху, а затем сверху-вниз.
Алгоритм такой же, что и у пузырьковой сортировки + добавляется цикл пробега сверху-вниз.
В приведенном ниже примере, есть усовершенствование в шейкерной сортировке. В отличие от классической, используется в 2 раза меньше итераций.
//Сортировка перемешивание (Шейкер-Сортировка) {--- Функция СортировкаПеремешиванием(Знач Массив) Для i = 0 ПО Массив.ВГраница()/2 Цикл нИтер = 0; конИтер = Массив.ВГраница(); Пока нИтер Массив[нИтер+1] Тогда Замена = Массив[нИтер]; Массив[нИтер] = Массив[нИтер + 1]; Массив[нИтер + 1] = Замена; КонецЕсли; нИтер = нИтер + 1;//Двигаем позицию на шаг вперед //Проходим с конца Если Массив[конИтер - 1] > Массив[конИтер] Тогда Замена = Массив[конИтер - 1]; Массив[конИтер-1] = Массив[конИтер]; Массив[конИтер] = Замена; КонецЕсли; конИтер = конИтер - 1;//Двигаем позицию на шаг назад КонецЦикла; КонецЦикла; Возврат Массив; КонецФункции //---}
4. Алгоритм "Гномья сортировка".
Алгоритм так странно назван благодаря голландскому ученому Дику Груну.
Гномья сортировка основана на технике, используемой обычным голландским садовым гномом (нидерл. tuinkabouter). Это метод, которым садовый гном сортирует линию цветочных горшков. По существу он смотрит на следующий и предыдущий садовые горшки: если они в правильном порядке, он шагает на один горшок вперёд, иначе он меняет их местами и шагает на один горшок назад. Граничные условия: если нет предыдущего горшка, он шагает вперёд; если нет следующего горшка, он закончил.
Дик Грун
Вот собственно и все описание алгоритма "Гномья сортировка". Что интересно, алгоритм не содержит вложенных циклов, а сортирует весь массив за один проход.
//Гномья сортировка {--- Функция ГномьяСортировка(Знач Массив) i = 1; j = 2; Пока i < Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по убыванию Если Массив i = j; j = j + 1; Иначе Замена = Массив[i]; Массив[i] = Массив; Массив = Замена; i = i - 1; Если i = 0 Тогда i = j; j = j + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат Массив; КонецФункции //---}
5. Алгоритм "Сортировка вставками".
Представляет собой простой алгоритм сортировки. Смысл заключается в том, что на каждом шаге мы берем элемент, ищем для него позицию и вставляем в нужное место.
Элементарный пример: При игре в дурака, вы тянете из колоды карту и вставляете ее в соответствующее место по возрастанию в имеющихся у вас картах. Или
в магазине вам дали сдачу 550 рублей- одна купюра 500, другая 50. Заглядываете в кошелек, а там купюры достоинством 10,100,1000. Вы вставляете купюру
достоинсвом 50р. между купюрами достоинством 10р и 100р, а купюру в 500 рублей между купюрами 100р и 1000р. Получается 10,50,100,500,1000 - Вот вам
и алгоритм "Сортировка вставками".
Таким образом с каждым шагом алгоритма, вам необходимо отсортировать подмассив данных и вставить значение в нужное место.
//Сортировка вставками {--- Функция СортировкаВставками(Знач Массив) Для i = 0 По Массив.ВГраница()-1 Цикл Ключ = i + 1; Замена = Массив[Ключ]; j = i + 1; Пока j > 0 И Замена < Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}
6. Алгортим "Сортировка слиянием".
Интересный в плане реализации и идеи алгоритм. Смысл его в том, чтобы разбивать массив на подмассивы, пока длина каждого подмассива не будет равна 1. Тогда мы утверждаем, что такой подмассив отсортирован. Затем сливаем получившиеся подмассивы воедино, одновременно сравнивая и сортируя поэлементно значения подмассивов.
p/s не смог вставить сюда рисунок с более наглядной схемой, постоянно размазывается. Зато хорошо видна в блоке скриншотов внизу. Можно посмотреть как работает алгоритм.
//Сортировка слиянием {---
Функция СортировкаСлиянием(Знач Массив) Если Массив.Количество() = 1 Тогда Возврат Массив; КонецЕсли; ТочкаРазрыв = Массив.Количество() / 2; лМассив = Новый Массив; прМассив = Новый Массив; Для Сч = 0 ПО Массив.ВГраница() Цикл Если Сч < ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > массив2[b]) И (b < массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}
7. Алгортим "Сортировка Шелла".
Алгоритм назван так в честь американского ученого Дональда Шелла. По своей сути этот алгоритм является усовершенствованным алгоритмом "Сортировка вставками". Смысл алгоритма заключается в том, чтобы сравнивать не только элементы, стоящие рядом друг с другом, но и на некотором удалении. Сначало выбирается Шаг - некий промежуток, через который будут сравниваться элементы массива на каждой итерации. Обычно его определяют так:
Для первой итерации Шаг = Цел(Массив.Количество()/2), для последующих Шаг = Цел(Шаг/2). Т.е. постепенно шаг сокращается и когда Шаг будет равен 1 произойдет последние сравнение и массив будет отсортирован.
Пример:
Дан массив (10,5,3,1,14,2,7,12).
1. Шаг = 4.
Сортируем простыми вставками каждые 4 группы по 2 элемента (10,14)(5,2)(3,7)(1,12)
10 ,2 ,3 ,1,14 ,5 ,7 ,12
2. Шаг = 2
Сортируем простыми вставками каждые 2 группы по 4 элемента (10,3,14,7)(2,1,5,12)
3 ,1 ,7 ,2 ,10 ,5 ,14 ,12
3. Шаг = 1
Сортируем простыми вставками каждую 1 группу по 8 элементов.
1,2,3,5,7,10,12,14
//Сортировка Шелла {--- Функция СортировкаШелла(Знач Массив) Шаг = Цел(Массив.Количество()/2); Пока Шаг > 0 Цикл i = 0; Пока i < (Массив.Количество() - Шаг) Цикл j = i; Пока j >= 0 И Массив[j] > Массив Цикл Замена = Массив[j]; Массив[j] = Массив; Массив = Замена; j = j - 1; Если ПрименитьОтображениеСортировки Тогда ОтобразитьДиаграммуСортировки(Массив); КонецЕсли; КонецЦикла; i = i + 1; КонецЦикла; Шаг = Цел(Шаг/2); ОбработкаПрерыванияПользователя(); КонецЦикла; Возврат Массив; КонецФункции //---}
8. Алгортим "Быстрая сортировка".
Наиболее популярный и применяемый алгоритм на практике. Является одним из самых эффективных алгоритмов сортировки данных.
Вся суть алгоритма сводится к тому, чтобы разбить сложную задачу на маленькие и решить их по отдельности. Выбирается некая опорная точка и все значения которые меньше перебрасываются влево, все остальные вправо. Далее для каждой полученной части выполняетя тоже самое, до тех пор пока дробить части уже нельзя. В конце мы получаем множество отсортированных частей, которые необходимо просто склеить в 1 целое.
//Алгоритм "Быстрая сортировка" { Процедура б_Сортировка(Массив,НижнийПредел,ВерхнийПредел) i = НижнийПредел; j = ВерхнийПредел; m = Массив[Цел((i+j)/2)]; Пока Истина Цикл Пока Массив[i] < m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m Цикл j = j - 1; КонецЦикла; Если i > j Тогда Прервать; КонецЕсли; КонецЦикла; Если НижнийПредел < j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}
9. Классическая сортировка массива в 1с.
Передаем массив в список значений. Сортируем стандартным методом "Сортировать".
//Сортировка списком значений {--- Функция СортировкаСпискомЗначений(Знач Массив) мСписокЗнч = Новый СписокЗначений; мСписокЗнч.ЗагрузитьЗначения(Массив); мСписокЗнч.СортироватьПоЗначению(НаправлениеСортировки.Возр); Возврат мСписокЗнч.ВыгрузитьЗначения(); КонецФункции //---}
Все сортировки можно ускорить расположив код в циклах в 1 строку. Но для читабельности, оставил так.
Написал обработку в которой реализованы все вышеперечисленные алгоритмы, также поддерживается динамическая анимация процесса сортировки (Кроме стандартной сортировки 1с).
-При запуске обработки автоматически происходит формирование массива случайных чисел от 0 до 100 размерностью 100 элементов.
-Для создания другого массива необходимо нажать на кнопку "Создание ГСЧ массива ", также можно выбирать необходимый диапазон.
-Для включения динамической анимации необходимо поставить галочку на "Отобразить сортировку в диаграмме". Советую на неэффективных алгоритмах устанавливать галочку при размерности массива до 100 элементов, иначе состаритесь ждать сортировки:)
Динамическая отрисовка процесса сортировки очень сильно снижает производительность, зато наглядно видно как работает алгоритм.
Обектом внешней сортировки является файл. Размеры файла принципиально не ограничены, то есть он может не помещаться в оперативной памяти. Для этого вида сортировки дополнительные расходы внешней памяти жестко не нормируются, поэтому активно используются вспомогательные файлы. Доступ к файлам строго последовательный. Это требование обусловлено двумя обстоятельствами. Во-первых, методы внешней сортировки должны быть работоспособными при хранении файлов на устройствах последовательного доступа типа магнитных лент. Во-вторых, при использовании прямого доступа основные затраты времени связаны с позиционированием файлов, что желательно исключить.
В основе методов внешней сортировки лежит процедура слияния, заключающаяся в объединении двух или более отсортированных последовательностей. Рассмотрим эту процедуру на примере слияния двух последовательностей A и B в последовательность C. Пусть элементы A и B отсортированы по возрастанию, то есть a 1 £ a 2 £ …£ a m и b 1 £ b 2 £ …£ b n . Требуется, чтобы последовательность C также располагалась по возрастанию, то есть выполнялось c 1 £ c 2 £ …£ c m + n .
Сначала в качестве текущих выбираются первые элементы последовательностей. Меньший из них записывается в C, и вместо него текущим становится следующий элемент этой же последовательности. Эта операция повторяется до исчерпания одной из последовательностей, после чего в C дописывается остаток другой последовательности.
Можно заметить, что доступ к элементам A, B и C выполнялся строго последовательно. В методах внешней сортировки в качестве последовательностей A, B и C фигурируют отсортированные участки файлов.
Базовым методом внешней сортировки является метод простого слияния. Рассмотрим его на следующем примере. Пусть имеется файл A, включающий элементы 27, 16, 13, 11, 18, 25, 7. Этот файл разделяется на два файла B и C путем поочередной записи элементов в эти файлы. Покажем это схемой
B: 27, 13, 18, 7
A: 27, 16, 13, 11, 18, 25, 7
Затем файлы B и C снова соединяются путем поочередного включения в C элементов из A и B. При этом первым располагается меньший элемент каждой пары. Получится следующий результат
B: 27, 13, 18, 7
Пары отделяются друг от друга апострофами. На следующем этапе снова происходит разделение файла A на B и C, но в каждый файл пишутся поочередно уже не отдельные элементы, а выделенные пары. Получаем
B: 16, 27,’ 18, 25
A: 16, 27,’ 11, 13,’ 18, 25, ‘ 7
B: 16, 27,’ 18, 25
A: 11, 13, 16, 27,’ 7, 18, 25
Затем файл A распределяется по четверкам элементов и при новом соединении будет состоять из упорядоченных восьмерок элементов. В нашем примере сортировка закончится на этом этапе. В общем случае длина отсортированных серий будет увеличиваться по степеням 2, пока величина серии не превзойдет количество элементов в файле.
На этом примере определим основные термины внешней сортировки. В методе участвовали 3 файла, поэтому он называется трехленточным. Для выполнения сортировки потребовалось 3 прохода. Отдельный проход состоял из процедур разделения и слияния, каждая из которых обрабатывала все элементы. Такие процедуры называют фазами. Следовательно, метод простого слияния является двухфазным и трехленточным.
Есть очевидное усовершенствование метода. Результат слияния сразу распределяется на две ленты, то есть в процессе участвуют уже 4 ленты. За счет дополнительной памяти число операций перезаписи уменьшается вдвое. Это однофазный четырехленточный метод, называемый также сбалансированным слиянием.
Как видно из приведенных выше данных, метод может конкурировать по скорости с самыми быстрыми методами внутренней сортировки, но не применяется в таком качестве, так как требует значительных затрат памяти. Число проходов оценивается величиной log 2 n, а общее число пересылок M пропорцинально n log 2 n.
Метод простого слияния не дает какого-либо выигрыша в тех случаях, когда файл A полностью либо частично отсортирован. Этот недостаток отсутствует в методе естественного слияния.
Назовем серией последовательность элементов a i , a i +1 , …, a j , удовлетворяющих соотношениям a i -1 > a i £ a i +1 £ …£ a j > a j +1 . В частных случаях серия может находиться в начале или конце последовательности.
Исходный файл A разбивается на серии. Распределение на B и C ведется по сериям. При соединении сливаются пары серий. Снова возможен как трехленточный, так и четырехленточный вариант метода. Ниже показан пример сортировки методом естественного слияния c 4 лентами.
B: 17, 25, 41, ‘6
A: 17, 25, 41, ‘ 9, 11, ‘ 6, ‘ 3, 5, 8, 44
C: 9, 11, ‘ 3, 5, 8, 44
A: 9, 11, 17, 25, 41 B: 3, 5, 6, 8, 9, 11, 17, 25, 41, 44
D: 3, 5, 6, 8, 44 C:
При последнем разделении лента C оказывается пустой, и отсортированный файл остается на ленте B.
Метод естественного слияния в целом быстрее, но требует большего числа сравнений, так как требуется определять конец каждой серии. Ниже приведена программа сортировки файла двухфазным трехленточным методом естественного слияния.
Program SortSlian;
{ 3-ленточная, 2-фазная сортировка естественным слиянием }
{ ключи целые и положительные }
Type elem=record
{ другие поля }
tape=file of elem;
Name: string; { имя исходного файла }
Procedure Vvod(var F: tape);
While K <> -1 do
Write("Введите очередной ключ (конец -1): ");
if K<>-1 then Write(F, S)
Procedure Pech(var F: tape);
While not eof(F) do
Write(S. Key," ")
Procedure CopyElem(var X, Y: tape;
var Buf: elem; var E: boolean);
{ копирование элемента и считывание следующего
{ в Buf с проверкой конца серии (E=True) }
if not Eof(X) then Read(X, Buf)
else Buf.Key:=-1; { барьер: достигнут конец файла }
E:=(Buf.Key Procedure CopySer(var X, Y: tape; var Buf: elem); { копирование серии из X в Y } {в начале Buf-первый элемент текущей серии на X } {в конце Buf-первый элемент следующей или –1 (конец X) } if Buf.Key>0 then { файл X не считан } CopyElem(X, Y, Buf, E) Until E { E=True в конце серии } Procedure Raspred; { распределение A ---> B и C } Read(A, S); { первый элемент из A } Rewrite(B); Rewrite(C); CopySer(A, B, S); {S-первый элемент следующей серии } if S.Key>0 then { файл A скопирован не весь } CopySer(A, C, S) Until S.Key<0 Procedure Slian; { слияние B и C--->A } E1, E2: boolean; Procedure SlianSer; { слияние серий из B и C ---> A } { S и T - первые элементы серий } { S.Key<0-весь файл B считан, T.Key<0-файл C считан } E1:=False; E2:=False; if (S.Key>0) and ((S.Key { файл B не считан и текущий элемент B меньше, чем в C либо файл C полностью считан } CopyElem(B, A, S, E1); if E1 then { достигнут конец серии на B } CopySer(C, A, T) CopyElem(C, A, T, E2); if E2 then { достигнут конец серии на C } CopySer(B, A, S) Begin { начало Slian } if not (Eof(B) or Eof(C)) then begin { оба файла не пусты } L:=0; { счетчик числа серий } While (S.Key>0) or (T.Key>0) do Begin { начало основной программы } Write("Введите имя файла для записи элементов: "); Assign(A, Name); Assign(B, "Rab1"); Assign(C, "Rab2"); L:=0; { L - число серий после слияния - параметр } WriteLn("Файл A: "); Pech(A); Raspred; { фаза распределения } WriteLn("Файл B: "); Pech(B); WriteLn("Файл C: "); Pech(C); ReadLn; { пауза } Slian { фаза слияния } Until L<=1; { L=0, если исходный файл отсортирован } WriteLn("Файл A в конце: "); Close(B); Erase(B); { удаление рабочих файлов } Close(C); Erase(C); Стоит обратить внимание на процедуру копирования элемента с ленты на ленту CopyElem. Реально в файл записывается элемент из оперативной памяти, оставшийся от предыдущего копирования, а в память читается следующий элемент данного файла. Это связано с необходимостью постоянной проверки конца серии. Приходится особо учитывать случай, когда конец серии совпадает с концом файла. При слиянии считается количество получившихся серий. Сортировка заканчивается, когда остается единственная серия. Эффективность сортировки можно повысить, используя многопутевое слияние, в котором распределение выполняется на k лент. Поскольку число серий на каждом проходе уменьшается в k раз, количество пересылок M пропорционально величине n log k n. Если общее число лент четное, то можно использовать однофазный метод слияния, распределяя серии с одной половины лент на другую. Платой за повышение эффективности многопутевого слияния являются, как всегда, увеличение сложности реализации и дополнительные затраты внешней памяти. На сколько может отличаться количество серий после разделения? На первый взгляд кажется, что не более, чем на одну, но это не так. Например, при распределении серий 17, 25, 41, ’ 9, 60, ‘ 50, 52, ‘ 7 первая и третья серии сливаются в общую серию, что не происходит со второй и четвертой сериями. В результате при последующем слиянии серии на одной из лент могут закончиться раньше, и придется впустую переписывать остаток другой ленты, теряя эффективность. Подобные ситуации учитываются в методе многофазной сортировки. Рассмотрим его на примере трех лент. Пусть при соединении лент B и C на ленту A серии на B заканчиваются раньше. Тогда лента B объявляется выходной, а лента A становится входной. Процесс продолжается до нового повторения ситуации, когда серии на одной из входных лент заканчиваются. Многофазная сортировка возможна и при многопутевом слиянии. Например, при использовании в сортировке k лент можно постоянно иметь одну выходную ленту. При исчерпании серий на одной из k-1 входных лент эта лента становится выходной вместо предыдущей выходной ленты. Методы внутренней и внешней сортировок могут использоваться совместно. Пусть сортируется большой по объему файл. В оперативной памяти выделяется буфер максимально возможного размера. Файл делится на блоки, соответствующие величине буфера. Блоки читаются в буфер, сортируются одним из методов внутренней сортировки и переписываются в другой файл. Сейчас каждый блок нового файла является серией достаточно большой длины, определяемой размером буфера. Остается применить один из методов внешней сортировки, использующий данные серии. Перед тем, как рассматривать какой-либо конкретный алгоритм, было бы полезно изучить терминологию и некоторые основные соглашения об алгоритмах сортировки. Мы будем изучать алгоритмы для сортировки файлов записей
содержащих ключи
. Ключи, которые являются только частью записи (часто очень маленькой их частью), используются для управления процессом сортировки. Целью алгоритма сортировки является переорганизация записей в файле так, чтобы они располагались в нем в некотором строго определенном порядке (обычно в алфавитном или числовом). Если сортируемый файл целиком помещается в память (или целиком помещается в массив), то для него мы используем внутренние
методы сортировки. Сортировка данных с ленты или диска называется внешней
сортировкой. Главное отличие между ними состоит в том, что при внутренней сортировке любая запись легко доступна, в то время как при внешней сортировке мы можем пользоваться записями только последовательно, или большими блоками. Большинство алгоритмов сортировки, которые мы рассмотрим - внутренние. Обычно, главное, что будет нас интересовать в алгоритме - это время его работы. Первые четыре алгоритма, которые мы рассмотрим, для сортировки N элементов имеют время работы пропорциональное, в то время как более сложные алгоритмы используют время пропорциональное. (Можно показать, что никакой алгоритм сортировки не может использовать менее, чем сравнений между ключами.) После изучения простых методов мы рассмотрим более сложные методы, время работы которых пропорционально и методы использующие бинарные свойства ключей для уменьшения общего времени работы до N. Количество используемой дополнительной памяти алгоритма сортировки - это еще один важный фактор, который мы будем принимать во внимание. Вообще говоря, методы сортировки делятся на три типа: методы сортировки, которые сортируют без использования дополнительной памяти, за исключением, возможно, небольшого стека и / или массива; методы, которые используют для сортировки связанные списки и поэтому используют N
дополнительных указателей хранящихся в памяти; и методы, которые нуждаются в дополнительной памяти для хранения копии сортируемого файла. Стабильность
- еще одна немаловажная характеристика методов сортировки. Метод сортировки называется стабильным,
если он сохраняет относительных порядок следования записей с одинаковыми ключами. Например, если алфавитный список группы сортируется по оценкам, то стабильный метод создает список, в котором фамилии студентов с одинаковыми оценками будут упорядочены по алфавиту, а нестабильный метод создаст список в котором, возможно, исходный порядок будет нарушен. Большинство простых методов стабильны, в то время как большинство хорошо известных сложных методов - нет. Если стабильность необходима, то она может быть достигнута посредством добавления к ключу небольшого индекса перед сортировкой или посредством удлинения, каким-либо образом, ключа. Стабильность с легкостью принимается за норму; к нестабильности люди относятся с недоверием. На самом же деле, лишь немногие методы достигают стабильности без использования дополнительного времени или места. Следующая программа, для сортировки трех записей, предназначена для иллюстрации основных соглашений, которые мы будем использовать. В частности, главная программа любопытна тем, что она работает только для N=3; смысл в том, что любая программа сортировки может быть сведена к процедуре sort3
этой программы. Три оператора присвоения, каждый из которых сопровождается оператором if,
на деле реализуют операцию «обмена». Мы вставляем ее непосредственно в программный код вместо использования вызова процедуры, поскольку они являются основой многих алгоритмов и часто попадают внутрь цикла. Чтобы сконцентрироваться на алгоритмических вопросах, мы будем работать с алгоритмами, которые просто сортируют массивы целых в численном порядке. В общем, очень легко адаптировать такие алгоритмы для практического использования, включающего в себя работу с большими ключами или записями. В основном программы сортировки работают с записями двумя способами: либо они сравнивают и сортируют только ключи, либо передвигают записи целиком. Большинство алгоритмов, которые мы изучим можно применять, посредством их переформулировки в терминах этих двух операций, для произвольных записей. Если сортируемые записи довольно большие, то обычно пытаются избежать передвижения их посредством «косвенной сортировки»: при этом сами записи не переупорядочиваются, а вместо этого переупорядочивается массив указателей (индексов), так, что первый указатель указывает на самый маленький элемент и так далее. Ключи могут храниться либо с записями (если они большие), либо с указателями (если они маленькие). Если необходимо, то после сортировки записи можно упорядочить. Это описано дальше. Программа sort3
использует даже более ограниченный доступ к файлу: это три операции вида «сравнить две записи и обменять их, если нужно, чтобы поместить запись с меньшим ключом на первое место». Программы, ограниченные такими операциями интересны, поскольку они подходят для реализации на аппаратном уровне. Мы изучим их более подробно позднее. Все примеры программ используют для сортировки глобальный массив. Это не означает, что такой подход лучше или хуже чем передача массива как параметра. Все зависит от точки зрения и конкретного алгоритма. Массив сделан глобальным только потому, что тогда примеры становятся короче и понятней. Для этого мы можем использовать следующую процедуру, которая физически упорядочивает записи файла используя при этом N перестановок: Приведенная программа использует последовательность… 1093, 364, 121, 40, 13, 4, 1. Могут существовать и другие последовательности - одни лучше, другие хуже. Свойство 6
Оболочечная сортировка никогда не делает более чем N
1.5
сравнений для вышеуказанной последовательности h.
Не только не считается самым быстрым методом, более того, она замыкает перечень самых медленных способов упорядочивания. Однако и у нее есть свои плюсы. Так, сортировка методом пузырька - самое что ни на есть логичное и естественное решение проблемы, если необходимо расставить элементы в определенном порядке. Обычный человек вручную, к примеру, воспользуется именно им - просто по интуиции. Название метода придумали, используя аналогию с воздушными пузырьками в воде. Это метафора. Подобно тому, как маленькие пузыри воздуха поднимаются наверх - ведь их плотность больше, чем какой-либо жидкости (в данном случае - воды), так и каждый элемент массива, чем меньше он по значению, тем больше он постепенно пробирается к началу перечня чисел. Сортировка пузырьком выполняется следующим образом: Еще короче алгоритм будущей программы можно записать так: Самая простая реализация выполняется так: Процедура Sortirovka_Puzirkom
;
Начало
цикл для j
от nachalnii_index
до konechii_index
;
цикл для i
от nachalnii_index
до konechii_index-1
;
если massiv[i]>massiv
(меняем значения местами);
Конец
Конечно, здесь простота только усугубляет ситуацию: чем проще алгоритм, тем более в нем проявляются все недостатки. Затратность времени слишком велика даже для небольшого массива (тут вступает в дело относительность: для обывателя количество времени может казаться маленьким, но в деле программиста каждая секунда или даже миллисекунда на счету). Потребовалась реализация получше. Например, учитывающая обмен значений в массиве местами: Процедура Sortirovka_Puzirkom
;
Начало
sortirovka
= истина;
цикл пока sortirovka
= истина;
sortirovka
= ложь;
цикл для i
от nachalnii_index
до konechii_index-1
;
если massiv[i]>massiv
(первый элемент больше второго), то:
(меняем элементы местами);
sortirovka
= истина; (обозначили, что обмен был произведен).
Конец.
Основной минус - продолжительность процесса. Сколько же времени выполняется пузырьком? Время выполнения рассчитывается из квадрата количества чисел в массиве - конечный результат ему пропорционален. При наихудшем варианте массив будет пройден столько же раз, сколько в нем имеется элементов минус одно значение. Так происходит потому, что в конечном итоге остается только один элемент, который не с чем сравнивать, и последний проход по массиву становится бесполезным действом. Кроме того, эффективен метод сортировки простыми обменами, как его еще называют, только для массивов небольшого размера. Большие объемы данных с его помощью обработать не получится: результатом станут либо ошибки, либо сбой работы программы. Сортировка пузырьком весьма проста для понимания. В учебных программах технических ВУЗов при изучении упорядочивания элементов массива ее проходят в первую очередь. Метод легко реализуется как на языке программирования Delphi (Д (Делфи), так и на C/C++ (Си/Си плюс плюс), невероятно простой алгоритм расположения значений в верном порядке и на Сортировка пузырьком идеально подходит для начинающих. По причине недостатков алгоритм не применяют во внеучебных целях. Изначальный вид массива 8 22 4 74 44 37 1 7 Шаг 1
8 22 4 74 44 37 1 7 8 22 4 74 44 1 37 7 8 22 4 74 1 44 37 7 8 22 4 1 74 44 37 7 8 22 1 4 74 44 37 7 8 1 22 4 74 44 37 7 1 8 22 4 74 44 37 7 Шаг 2
1 8 22 4 74 44 7 37 1 8 22 4 74 7 44 37 1 8 22 4 7 74 44 37 1 8 22 4 7 74 44 37 1 8 4 22 7 74 44 37 1 4 8 22 7 74 44 37 Шаг 3
1 4 8 22 7 74 37 44 1 4 8 22 7 37 74 44 1 4 8 22 7 37 74 44 1 4 8 7 22 37 74 44 1 4 7 8 22 37 74 44 Шаг 4
1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Шаг 5
1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Шаг 6
1 4 7 8 22 37 44 74 1 4 7 8 22 37 44 74 Шаг 7
1 4 7 8 22 37 44 74 Пример:
const kol_mas=10;
var massiv:array of integer;
a, b, k: integer;
writeln ("input", kol_mas, "elements of array");
for a:=1 to kol_mas do readln(massiv[a]);
for a:=1 to kol_mas-1 do begin
for b:=a+1 to kol_mas do begin
if massiv[a]>massiv[b] then begin
k:=massiv[a]; massiv[a]:=massiv[b]; massiv[b]:=k;
end;
writeln ("after sort");
for a:=1 to kol_mas do writeln(massiv[a]);
#include
#include
int main(int argc, char* argv)
int massiv = {36, 697, 73, 82, 68, 12, 183, 88},i, ff;
for (; ;){
ff = 0;
for (i = 7; i>0; i--){
if (massiv[i] < massiv) {
swap (massiv[i],massiv);
if (ff == 0) break;
getch(); // задержка экрана
На днях в комментариях вконтакте у меня возник спор с одним из других студентов проекта. Суть спора заключалась в том, «кто кого» - метод sort() из класса java.util.Arrays или самописные реализации простых алгоритмов: bubble
(пузырьковая), insertion
(вставками), selection
(выбором), shell
(алгоритм Шелла).
Для некоторых ответ на данный вопрос может быть очевиден, но раз спор возник, при том что у каждой из сторон были «уважаемые источники» в пользу своей точки зрения, было принято решение провести исследование, поразмяв в процессе серое вещество, реализуя различные алгоритмы.
TL;DR:
java.util.Arrays.sort() безоговорочно лидирует на массивах от 100 000 элементов, при меньшем размере с ним иногда может потягаться метод Шелла. Остальные рассмотренные алгоритмы сливают вчистую и могут быть полезны лишь при каких-то экзотических условиях.
Теперь давайте рассмотрим, как же осуществляется сортировка массивов в наших убер-девайсах из кремния.
Откуда взялось такое необычное название?
Описание алгоритма
Псевдокод на основе описанного алгоритма
Недостатки метода
Достоинства
Наглядный принцип сортировки
Пример сортировки пузырьком на языке Pascal
Пример сортировки пузырьком на языке С (Си)
Selection sort. Сортировка выбором
Начнем с самого простого и очевидного способа. Суть его нам отлично демонстрирует Роберт Седжвик в своей видеолекции на coursera (привожу погано пережатую в gif мной анимацию оттуда):
Пробегая по массиву с первого элемента, мы на каждом шаге ищем в правой части минимальный элемент, с которым и меняем местами текущий. В результате мы оставляем за собой окончательный вариант нашего массива в отсортированном виде.
Вот код, реализующий этот алгоритм на Java:
public
void
sort
(int
array)
{
int
n =
array.
length;
for
(int
i =
0
;
i <
n;
i ++
)
{
int
minIndex =
min
(array,
i,
n -
1
)
;
swap
(array,
i,
minIndex)
;
}
}
public
static
void
swap
(int
array,
int
i,
int
j)
{
int
temp =
array[
i]
;
array[
i]
=
array[
j]
;
array[
j]
=
temp;
}
public
static
int
min
(int
array,
int
begin,
int
end)
{
int
minVal =
array[
begin]
;
int
minIndex =
begin;
for
(int
i =
begin +
1
;
i <=
end;
i++
)
{
if
(array[
i]
<
minVal)
{
minVal =
array[
i]
;
minIndex =
i;
}
}
return
minIndex;
}
Анализ алгоритма показывает, что необходимо на каждом проходе прошерстить весть остаток массива, то есть нам понадобится ровно N + (N-1) + (N-2) + … + 1 = N^2/2 сравнений. Таким образом, сложность алгоритма составляет O(N^2). Что же это означает? А означает это, что, увеличив количество элементов в массиве (N) в 2 раза, мы увеличим время работы алгоритма не в 2, а в 2^2 = 4 раза. Увеличив N в 10 раз, время работы увеличим в 100 раз и так далее. На моем ноутбуке 2012 года с процессором Core i3 под Ubuntu 14.4 я получил следующее время работы:
Insertion sort. Сортировка вставками
Здесь идея несколько иная. Опять же, обратимся к анимации от Доктора Седжвика:
То, что впереди, нами еще даже не просмотрено, а все что оставляем позади себя, всегда остается выстроенным по порядку. Суть в том, что каждый новый элемент исходного массива мы «возвращаем» к началу до тех пор, пока он не «упрется» в меньший элемент.
Таким образом, у нас опять N проходов (для каждого элемента исходного массива), но в каждом проходе в большинстве случаев мы просматриваем не весь остаток, а только часть. То есть вариант 1 + (N-1) + (N-2) + … + N = N^2/2 мы получим, только если каждый следующий элемент нам придется возвращать к самому началу, то есть в случае отсортированного «наоборот» входного массива (не везет, так невезет). В случае же уже отсортированного массива (вот везуха ваще) будет полная халява – на каждом проходе всего одно сравнение и оставление элемента на месте, то есть отработает алгоритм за время, пропорциональное N. Сложность алгоритма же будет определяться худшим теоретическим случаем, то есть O(N^2). Среднестатистически же, время работы будет пропорционально N^2/4, то есть, вдвое быстрее предыдущего алгоритма. В моей реализации из-за неоптимального использования перестановки время работы получилось больше, чем у Selection. Планирую в ближайшее время исправить и обновить пост.
Вот код и результат его работы на той же машине:
public
void
sort
(int
array)
{
int
length =
array.
length;
for
(int
i =
1
;
i <
length;
i++
)
{
for
(int
j =
i;
j >=
1
;
j--
)
{
if
(array[
j]
<
array[
j -
1
]
)
swap
(array,
j,
j -
1
)
;
else
break
;
}
}
}
Shell sort. Сортировка Шелла
Умный мужик Дональд Шелл аж в 1959-м году заметил, что в алгоритме вставками дороже всего обходятся случаи, когда элемент возвращается очень далеко к началу массива: на каком-то проходе мы вернем элемент к началу на пару позиций, а на другом проходе почти через весь массив к началу – далеко и долго. Нельзя ли это сделать сразу, прыгая через несколько элементов? И такой способ он нашел. Заключается он в последовательном выполнении особых частичных сортировок, называемых в общем виде d-sort или, у Седжвика, h-sort (подозреваю, h означает hop - прыжок).
3-sort, например, будет сравнивать рассматриваемый элемент не с предыдущим, а пропустит два и сравнит с отстоящим на 3 позиции назад. Если поменяли, он его сравнит снова с элементом на 3 позиции назад и так далее.
Суть в том, что полученный в результате массив будет «3-отсортирован», то есть неправильность положения элементов составит менее 3х позиций. Работать с таким алгоритму вставки будет легко и приятно. Кстати, «1-sort» является ничем иным, как просто алгоритмом вставки=)
Последовательно применяя к массиву h-sort с уменьшающимся значением h, мы сможем отсортировать большой массив быстрее. Вот как это выглядит:
Сложность здесь заключается в том, как выбрать правильную последовательность частичных сортировок. От этого, в итоге, зависит производительность алгоритма. Наиболее распространенной является последовательность, предложенная Дональдом Кнутом:
h = h*3 + 1, то есть 1, 4, 13, 40, … и так до 1/3 размера массива. Такая последовательность обеспечивает достойную производительность, а также проста в реализации.
Анализ алгоритма требует тонн матана и мной не осилен. Обширность анализа так же определяется множеством вариантов последовательностей h. Эмпирически же можно сказать, что скорость алгоритма весьма хороша – смотрите сами:
Миллион элементов менее, чем за секунду!
А вот код на Java с кнутовской последовательностью.
public
void
sort
(int
array)
{
int
h =
1
;
while
(h*
3
<
array.
length)
h =
h *
3
+
1
;
while
(h >=
1
)
{
hSort
(array,
h)
;
h =
h/
3
;
}
}
private
void
hSort
(int
array,
int
h)
{
int
length =
array.
length;
for
(int
i =
h;
i <
length;
i++
)
{
for
(int
j =
i;
j >=
h;
j =
j -
h)
{
if
(array[
j]
<
array[
j -
h]
)
swap
(array,
j,
j -
h)
;
else
break
;
}
}
}
Bubble sort. Метод пузырька
Это классика! Этот алгоритм реализует почти каждый начинающий программист. Это настолько классика, что у Доктора Седжвика даже не нашлось анимации для него, потому мне пришлось потрудиться самому.
Здесь на каждом проходе мы обходим массив с начала до конца, меняя местами соседние элементы, стоящие не по порядку. В результате самые крупные элементы «всплывают» (отсюда и название) в конец массива. Каждый новый проход мы начинаем, оптимистично надеясь, что массив уже отсортирован (sorted = true). В конце прохода, если мы видим, что ошиблись, начинаем новый проход.
Сложность здесь заключается в том, что мы, опять же, обходим весь (почти) массив на каждом проходе. Сравнение происходит на каждом шаге, обмен - почти на каждом, что делает данный алгоритм одним из самых медленных (если рассматривать рационально реализованные, а не "сортировку встряхиванием" и прочие подобные).
Интересно, что формально сложность и здесь будет равна O(N^2), только вот коэффициент гораздо выше, чем у вставок и выборов. Код алгоритма:
public
void
sort
(int
array)
{
boolean
isSorted;
int
nMinusOne =
array.
length -
1
;
for
(int
i =
0
;
i <
nMinusOne;
i++
)
{
isSorted =
true
;
for
(int
j =
0
;
j <
nMinusOne -
i;
j++
)
{
if
(array[
j]
>
array[
j +
1
]
)
{
swap
(array,
j,
j +
1
)
;
isSorted =
false
;
}
}
if
(isSorted)
return
;
}
}
Время работы:
Почувствуйте разницу: более получаса на миллионе элементов!
Вывод: Никогда не исползуйте этот алгоритм!!!
Резюме первой части
Как итог предлагаю посмотреть общую таблицу для этих алгоритмов.
Можете так же сравнить с результатами для встроенного метода java.util.Arrays.sort() . Похоже на какую-то магию - что же может быть быстрее Шелла? Об этом напишу в следующей части. Там мы рассмотрим широко применяемые алгоритмы быстрой сортировки, а также сортировки слиянием, узнаем о разнице в методах сортировки массивов из примитивов и ссылочных типов, а также познакомимся с очень важным в этом деле интерфейсом Comparable ;)
Ниже можете изучить график, построенный в логарифмическом масштабе по данным таблицы. Чем более полого идет линия, тем лучше алгоритм =)
Кто хочет скачать весь проект и прогнать тесты у себя, держите ссылку:
Java
До встречи в следующей части! =)
