Линейная сортировка

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

И так, линейная сортировка признана самым быстрым из всех методов сортировки. Данный метод позволяет сортировать массивы за линейное время!

Но, как известно, ничего идеального не существует. Вот и у линейной сортировки есть существенный минус. Данный метод сортировки самый жадный в плане используемой памяти.

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

Идея алгоритма заключается в следующем.

  1. Необходимо заранее знать диапазон, в который попадают все элементы массива. Обычно такой диапазон не известен, но можно взять шире, к примеру, если элементы массива типа Byte, то диапазон будет от 0 до 255, если это Word, то от 0 до 65535 (2^16-1) и т.п. Задаем вспомогательный целочисленный массив, размерность которого совпадает с диапазоном возможных значений элементов сортируемого массива, например, если элементы сортируемого массива имеют тип Word, то вспомогательный массив может быть задан так:

    var Elems: array[Word] of Integer;

    Или так (что будет равнозначно предыдущей записи):

    var Elems: array[0..65535] of Integer;

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

  2. Следующим шагом заполняем вспомогательный массив нулями.
  3. Проходим по всем элементам сортируемого массива, при этом увеличиваем на 1 элемент вспомогательного массива с индексом, равным значению текущего элемента сортируемого массива.
  4. Теперь элементы вспомогательного массива указывают на количество каждого из значений сортируемого массива. Для сортировки по возрастанию, проходим вспомогательный массив от нулевого индекса до максимального, по убыванию - в обратном порядке.

Алгоритм можно немного оптимизировать, если во время сортировки определять еще значения минимального и максимального элементов сортируемого массивов.

Посмотрим на пример программы (массив заполняется случайными числами, выводится, сортируется линейным методом и снова выводится):

  1. program LinearSort;
  2. {$APPTYPE CONSOLE}
  3. const N = 20; // кол-во элементов сортируемого массива
  4. type TElem = Byte; // тип элементов сортируемого массива
  5. var Vector: array[1..N] of TElem; // сортируемый массив
  6.     Temp: array[TElem] of Integer; // вспомогательный массив
  7.     Min, Max: TElem; // минимум и максимум сортируемого массива
  8.     I, J: Integer; // счетчики
  9. begin
  10.   Randomize; // Заполняем массив случайными числами:
  11.   for I := 1 to N do // High возращает максимально возможное значение типа данных
  12.   begin
  13.     Vector[I] := Random (High (TElem) + 1); // заполняем элемент случайным числом
  14.     Write (Vector[I], ' '); // выводим элемент массива
  15.   end; {for}
  16.   WriteLn; WriteLn; // выводим пустую строку
  17.   // Далее идет линейная сортировка массива:
  18.   FillChar (Temp, SizeOf (Temp), 0); // заполняем вспомогательный массив нулями
  19.   Min := High (TElem); // определяем минимум максимальным значением
  20.   Max := 0; // определяем максимум минимальным значением
  21.   for I := 1 to N do // собственно, этот цикл и есть сортировка
  22.   begin
  23.     Inc (Temp[Vector[I]]); // накапливаем количество каждого из значений массива
  24.     if Vector[I] < Min then Min := Vector[I]; // определяем минимальный элемент
  25.     if Vector[I] > Max then Max := Vector[I]; // определяем максимальный элемент
  26.   end; {for}
  27.   // Выводим результат сортировки:
  28.   for I := Min to Max do
  29.     for J := 1 to Temp[I] do
  30.       Write (I, ' ');
  31.   ReadLn;
  32. end.

Программу можно откомпилировать, создав консольный проект в Delphi.
При желании можно изменить количество элементов сортируемого массива и их тип (например, с Byte на Word).

5
Your rating: Нет Average: 5 (4 votes)

Комментарии

Материал интересный! Не

Материал интересный! Не сомневаюсь, вопросы будут и по сути и по языку. Но и Вы попались с кодировкой знаков "<", ">". (см. решение в комментах к бонус-тесту1)

Уже исправлено. Это глюки

Уже исправлено. Это глюки визуального редактора.

Ээ ...й !!! Коллеги! И что же

Ээ ...й !!! Коллеги! И что же вы не спросите,  что такое High(T) или FillChar(...), например?

Хм...Объясните это

Хм...Объясните это пожалуйста) Как раз возник такой вопрос.

High(T) - возвращает

High(T) - возвращает максимальное допустимое значение переменных типа T, например, для Byte это 255.

Есть еще Low(T), которая, напротив, возвращает минимальное допустимое значение, для Byte оно равно 0.

Функция FillChar(...) заполняет память однородными значениями.

Давайте проведем замер

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

И так, входные данные: массив, состоящий из 100 000 элементов, заполненный случайными числами от 0 до 999. Выводить на экран сами элементы массивы мы не будем, т.к. их очень много. Выведем только время работы алгоритма и число итераций.

Смотрим на результат пузырьковой сортировки (возможно, реализация алгоритма немного отличается от той, что давалась в лекциях):

  1. program BubbleSort;
  2. {$APPTYPE CONSOLE}
  3. uses SysUtils, Windows;
  4. const N = 100000;
  5. type TElem = 0..999;
  6. var Vector: array[1..N] of TElem;
  7.     Temp: TElem;
  8.     Flag: Boolean;
  9.     I, M: Integer;
  10.     Cnt: Int64;
  11.     Start: Cardinal;
  12. begin
  13.   for I := 1 to N do Vector[I] := Random (High (TElem) + 1);
  14.   Start := GetTickCount;
  15.   Cnt := 0;
  16.   // НАЧАЛО: Пузырьковая сортировка
  17.   M := N;
  18.   repeat
  19.     Flag := True;
  20.     Dec (M);
  21.     for I := 1 to M do
  22.     begin
  23.       Inc (Cnt); // увеличиваем счетчик итераций
  24.       if Vector[I] > Vector[I+1] then
  25.       begin
  26.         Temp := Vector[I]; Vector[I] := Vector[I+1]; Vector[I+1] := Temp;
  27.         Flag := False;
  28.       end; {if}
  29.     end; {for}
  30.   until Flag;
  31.   // КОНЕЦ: Пузырьковая сортировка
  32.   WriteLn ('Delay (ms): ' + IntToStr (GetTickCount - Start));
  33.   WriteLn ('Count: ' + IntToStr (Cnt));
  34.   ReadLn;
  35. end.

Результат следующий:
Delay (ms): 93047
Count: 4999921797

Т.е. алгоритм работал более полутора минут, при этом было осуществлено около 5 миллиардов итераций!

Честно, я даже устал ждать, когда же сортировка завершится. А ведь 100 000 элементов это не так много. В реальных прикладных задачах могут быть куда более крупные массивы данных.
Конечно, можно использовать алгоритм быстрой сортировки. Предлагаю студентам самим произвести замер времени, которое уйдет на работу быстрой сортировки для данного примера.

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

  1. program LinearSort;
  2. {$APPTYPE CONSOLE}
  3. uses SysUtils, Windows;
  4. const N = 100000;
  5. type TElem = 0..999;
  6. var Vector: array[1..N] of TElem;
  7.     Temp: array[TElem] of Integer;
  8.     Min, Max: TElem;
  9.     I, J, Ind: Integer;
  10.     Cnt: Int64;
  11.     Start: Cardinal;
  12. begin
  13.   for I := 1 to N do Vector[I] := Random (High (TElem) + 1);
  14.   Start := GetTickCount;
  15.   Cnt := 0;
  16.   // НАЧАЛО: Линейная сортировка
  17.   FillChar (Temp, SizeOf (Temp), 0);
  18.   Min := High (TElem); Max := Low (TElem);
  19.   for I := 1 to N do
  20.   begin
  21.     Inc (Cnt); // увеличиваем счетчик итераций
  22.     Inc (Temp[Vector[I]]);
  23.     if Vector[I] < Min then Min := Vector[I];
  24.     if Vector[I] > Max then Max := Vector[I];
  25.   end; {for}
  26.   Ind := 1;
  27.   for I := Min to Max do
  28.     for J := 1 to Temp[I] do
  29.     begin
  30.       Vector[Ind] := I;
  31.       Inc (Ind);
  32.       Inc (Cnt); // увеличиваем счетчик итераций
  33.     end; {for}
  34.   // КОНЕЦ: Линейная сортировка
  35.   WriteLn ('Delay (ms): ' + IntToStr (GetTickCount - Start));
  36.   WriteLn ('Count: ' + IntToStr (Cnt));
  37.   ReadLn;
  38. end.

Смотрим на результат:
Delay (ms): 0
Count: 200000

И так, как мы видим, число итераций в двое больше, чем количество элементов сортируемого массива, т.е. зависит от него линейно. Скорость же работы в данном случае составила менее 1 миллисекунды (это против полутора минут работы пузырьковой сортировки).

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

P.S. Линейная сортировка называется еще сортировкой подсчетом. Названия разные, а суть алгоритма одна и та же.

Коммент в строке 10 исходного

Коммент в строке 10 исходного примера я бы подредактировал. Randomaze ничего не знает о существовании массива.

Наверное, не очевидно

Наверное, не очевидно получилось. Это мой стиль комментариев, если комментарий идет с маленькой буквы, то он относится к данной строке, а если с большой и в конце символ ":", то к коду ниже. Т.е. тот комментарий относился не к randomize, а к циклу ниже.

[quote]Данный метод

[quote]Данный метод сортировки самый жадный в плане используемой памяти...[/quote]

Можно подумать, что современным архитектурам эвм есть разница, что вычислять. Тем более, речь идет всего лишь о простейшей сортировке, а не о сверхкосмических задачах, † м? :D

P.S.: Комментарии вполне доходчивы, зря вы так.

Теперь понял!

Теперь понял!

Вы не правы. Если элементы

Вы не правы. Если элементы массива имеют тип Byte, то вспомогательный массив будет содержать 256 элементов типа Integer, если же элементы сортируемого массива типа Word, то вспомогательный массив состоит уже из 65536 элементов типа Integer. А вот если рассматривать общий случай и сортируемый массив задавать, как массив типа Integer (в Делфи), то понадобится вспомогательный массив, состоящий из более чем 4 миллиардов элементов типа Integer, т.е. 16 Гб памяти.