Мастера DELPHI, Delphi programming community Рейтинг@Mail.ru Титульная страница Поиск, карта сайта Написать письмо 
| Новости |
Новости сайта
Поиск |
Поиск по лучшим сайтам о Delphi
FAQ |
Огромная база часто задаваемых вопросов и, конечно же, ответы к ним ;)
Статьи |
Подборка статей на самые разные темы. Все о DELPHI
Книги |
Новинки книжного рынка
Новости VCL
Обзор свежих компонент со всего мира, по-русски!
|
| Форумы
Здесь вы можете задать свой вопрос и наверняка получите ответ
| ЧАТ |
Место для общения :)
Орешник |
Коллекция курьезных вопросов из форумов
KOL и MCK |
KOL и MCK - Компактные программы на Delphi
 

Поразрядная сортировка

Роман Игнатьев ©

Файлы к статье

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

Необходимость в упорядочивании каким-либо образом каких-либо данных возникает постоянно, иногда совсем неожиданно. О словарях я даже не говорю, но сортировка встречается, например, при поиске двух ближайших точек на плоскости и во множестве других алгоритмов. И сортировка массива, насколько я помню, была первым серьезным методом (решение квадратного уравнения не в счет), который я реализовал, обучаясь программированию. Самое занятное то, что метод сортировки я придумал самостоятельно, и это был метод пузырька, хотя более "человеческим" является метод вставок, именно так обычно сортируют карты на руках при игре в дурака. Позже я познакомился с другими методами, гораздо более эффективными и быстрыми. И более сложными. В некоторых случаях более эффективными. Именно поэтому я и сейчас часто применяю сортировку пузырьком, иногда она оказывается вполне к месту.

Думаю, пришло время все-таки дать определение тому, что же такое сортировка. Пусть имеется упорядоченное множество K, состоящее из элементов k. "Упорядоченное" означает, что для любых двух k1,k2 из этого множества всегда можно сказать, что k1>k2 или k1<k2 или, наконец, k1=k2. И пусть имеется другое множество, каждый элемент которого имеет в своем составе то самое k, которое называется ключем. Требуется упорядочить второе множество так, чтобы ключ каждого предыдущего элемента был не больше (не меньше) ключа последующего элемента.

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

Как я уже сказал, есть множество методов сортировки. Наиболее известными являются, на мой взгляд, метод пузырька (иногда его называют обменной сортировкой), быстрая сортировка (quicksort) и пирамидальная сортировка (heapsort). При этом именно быстрая сортировка присутствует в Delphi, в частности, ее использует TStringList, когда ему нужно отсортировать строки. Все эти методы сравнивают ключи между собой. И можно показать, что при таком способе можно сделать количество операций при сортировке пропорциональным N*Log(N), где N - количество ключей, а Log - логарифм, но не меньше (если кто интересуется, посылаю к [1]).

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

Для того, чтобы обойти ограничение в N*Log(N), нужно просто сортировать записи, не сравнивая ключи между собой. Как это возможно? В общем случае так сделать нельзя, но если ввести некоторые ограничения на значения ключей, это вполне достижимо. Например, пусть имеются 16 записей, и их ключи принимают значения от 1 до 16 без повторений. Тогда достаточно просто переписать записи во второй массив, каждую запись с индексом, равным ключу. Всего один просмотр массива - и записи идут по порядку. Никаких сравнений.

Понятно, что такой случай очень редко встречается. Гораздо чаще тип ключа - целое число, например, integer. Как быть в этом случае? Надо применить поразрядную сортировку.

Сразу скажу об ограничении: для поразрядной сортировки ключи должны быть дискретными, например, целыми числами. И весьма желательно, чтобы разрядность этих чисел была не такой уж большой. По странному стечению обстоятельств, именно с такими числами и приходится чаще всего работать при программировании на компьютере. Действительно, даже тип double занимает всего 8 байт, и при наличии большого желания его можно считать целым числом длиной 64 бита. Честно говоря, чем больше битов, тем хуже для поразрядной сортировки, поэтому ниже речь пойдет о сортировке 32-битных целых чисел, в полном соответствии с разрядностью большинства процессоров. Конечно, этот метод сортировки можно применить для любого количества битов, вот только время его работы, хотя и пропорционально количеству сортируемых ключей, но вместе с тем и количеству разрядов, что делает его не таким уж и привлекательным, когда ключи становятся длинными.

Впрочем, пора переходить к описанию метода. Проще всего его объяснить на примере. Допустим, нам надо отсортировать всего лишь набор из десятка двузначных чисел: (83, 26, 37, 43, 42, 51, 87, 13, 90, 45). Само название метода дает намек, как мы будем это делать, разумеется, поразрядно (здесь два десятичных разряда). Наиболее естественно сначала выписать все числа так, чтобы старшие разряды шли по возрастанию, а потом упорядочить внутри каждого разряда по второй цифре. Но если у вас полсотни таких чисел? Представьте себе, что они написаны на бумажках, и вы раскладываете их по корзинам (или шляпам, например). Понадобиться десяток корзин, в которые вы положите бумажки с самой левой цифрой, которая равна номеру корзины. А потом вам придется вынимать из каждой корзины ее содержимое и раскладывать по порядку на столе. На самом деле, начинать надо с младшей (правой) цифры. Возьмем десяток корзин, занумеруем их по порядку от 0 до 9 (настоящий программист считает именно с 0, а не с 1, именно поэтому у него постоянные проблемы с подсчетом в реальной жизни), и разложим в них числа, смотря только на правую цифру, это можно сделать, просмотрев числа по порядку всего одни раз:

0 1 2 3 4 5 6 7 8 9
90 51 42 83
3
13
  45 26 37
87
   

Как видно, в некоторых ячейках таблицы совсем ничего нет, а кое-где есть несколько чисел, причем в том порядке, в каком они шли сначала (это важно!). Теперь выложим эти числа: (90, 51, 42, 83, 43, 13, 45, 26, 37, 87). Пока почти никакого намека на порядок. Но осталась еще одна цифра, и мы раскладываем числа именно по ней, причем опять в том порядке, в котором они идут:

0 1 2 3 4 5 6 7 8 9
  13 26 37 42
43
45
51     83
87
90

Посмотрим, что получилось: (13, 26, 37, 42, 43, 45, 51, 83, 87, 90). Вуаля! Все числа идут по возрастанию. Сортировка закончена. Самое главное здесь записывать числа в каждой ячейке именно по порядку просмотра массива, иначе фокус не получится!

Теперь поговорим о реализации. А именно, о сортировке чисел, каждое из которых занимает 4 байта. Человеку естественно записывать числа в десятичной системе счисления, а вот компьютер чаще всего работает с двоичной. Конечно, первое побужение - это взять две ячейки, и раскладывать числа по ним. Но при этом нам придется просмотреть массив чисел 32 раза. Гораздо лучше и естественней взять массив из 256 ячеек, и рассматривать числа как 4 байта, ведь в любом байте всего 256 значений. На столе столько корзинок вряд ли поместится, а вот в памяти компьютера - без проблем. Вот только элементы массива странные: в каждом может быть вообще ничего, или несколько чисел, причем сколько их будет сразу и не скажешь, вроде бы не больше, чем их есть в исходном наборе. Поэтому массив здесь применить сложно. К счастью, не массивами едиными жив программист, и есть тип данных, который подходит очень хорошо, это однонаправленный список. Он хорош еще и тем, что в нем можно менять порядок записей, не меняя их местами, что делает его идеальной структурой для этой сортировки.

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

Эта процедура использует массив из 256 таких же списков и делает следующее:

Для всех i от 1 до SizeOf(Key), то есть для каждого байта ключа от младшего к старшему:

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

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

Осталась реализация. Элемент однонаправленного списка - запись, одно поле которой ключ, а второе - ссылка на следующий элемент списка:

type
  PDElem = ^TDElem;
  TDElem = record
    Key: LongWord;
    Item: Pointer;
    Next: PDElem;
  end;

В соответствии с соглашениями, тип записи начинается с T, а тип указателя на эту запись - с P. Как ни странно, список имеет тип тоже PDElem, это просто указатель на первый элемент списка (или пустой указатель, когда список пуст), полностью аналогично PChar: вроде бы указатель на символ, но на самом деле это обычно указатель на первый элемент массива символов, последний из которых #0. Здесь сигналом конца списка является nil в поле Next последнего элемента.

Поле ключа (Key) я объявил как LongWord, что читается как "целое-в-четыре-байта-без-знака". Ключи со знаком (integer), конечно, тоже можно сортировать, но учитывать знак все-таки довольно сложно (интересующимся советую посмотреть здесь), тем более, что если к ключу, имеющему тип integer, прибавить High(integer) и еще 1, то гарантированно получится положительное число, что и требуется.

Поле Next - как раз тот самый указатель на следующий элемент. Я еще добавил поле Item, просто указатель на сортируемые структуры, его никто трогать не будет, так, на всякий случай.

Теперь остается написать процедуру, которая берет список, и сортирует его по возрастанию:

procedure RadixSort(DList: PDElem); 

Как я уже сказал, понадобиться еще массив таких списков:

type
  TBucket = array [byte] of TDElem;
  TBucketTail = array [byte] of PDElem;

var
  Bucket: TBucket;
  BucketTail: TBucketTail;

Ээээ... Два массива. Все дело в том, что использовать просто массив указателей мне кажется не слишком удобным, при присвоении нового элемента приходится проверять, а не равен ли указатель nil? То есть, а не пуст ли данный список? Если же массив сделан из самих записей, такой вопрос не возникает. Разумеется, массив Bucket состоит из записей, у которых нам нужно только поле Next, остальные поля могут содержать что угодно. При этом, конечно, расходуется место в памяти, но очень немного, зато обработка будет более однообразной. Второй же массив, BucketTail, будет указывать на последний элемент списка в той же ячейке Bucket. Понятно, в самом начале он указывает на сам элемент Bucket. Если бы этого массива не было, пришлось бы для присоединения элемента проходить весь список от первого элемента к последнему, а так - операция тривиальна.

Пора написать реализацию:

procedure RadixSort(DList: PDElem);
var
  i, j: integer;
  KeyIndex: byte;
  ListElem, lastElem: PDElem;
  firstElem: TDElem;
begin
  if not assigned(DList) then exit;
  //начальные установки
  //элементы Bucket имеют тип записи, для однообразия в цикле
  for i := 0 to sizeOf(LongWord) - 1 do
  begin
    for j := 0 to High(byte) do
      BucketTail[j] := @Bucket[j];
    //Идем по списку
    ListElem := DList;
    repeat
      //i указывает номер обрабатываемого байта, сдвигаем вправо на i*8
      //и берем младший байт, он как раз и нужен
      KeyIndex := byte(ListElem^.Key shr (i shl 3));
      //Вставлять надо в конец списка
      BucketTail[KeyIndex]^.Next := ListElem;
      //и не забыть переместить хвост
      BucketTail[KeyIndex] := ListElem;
      //Теперь можно взять следующий элемент
      ListElem := ListElem^.Next;
    until not assigned(ListElem);

    //Все, теперь для следующей итерации надо вновь срастить список
    firstElem.Next := nil;
    lastElem := @firstElem;
    for j := 0 to High(byte) do
      //Если в ячейке есть список
      if BucketTail[j] <> @Bucket[j] then  //добавляем его в хвост
      begin
        lastElem^.Next := Bucket[j].Next;
        lastElem := BucketTail[j];
      end;
      //осталось присвоить список и обнулить его хвост
      DList := firstElem.Next;
      lastElem^.Next := nil;
  end; //for i
end;

Если выкинуть комментарии, получается очень компактная процедура, состоящая из одного цикла for i := 0 to sizeOf(LongWord) - 1. Я уже говорил, что программисты считают от 0? Это удобно, потому что i-й байт ключа получается выражением byte(ListElem^.Key shr (i shl 3)). i shl 3 - это умножение i на 8 (2^3), после этого Key сдвигается вправо на это количество бит, и все старшие байты нагло отрезаются преобразованием типа. То есть при i=0 мы получим самый младший байт, при i = 1 - второй и т.д. Но я отвлекся. Итак, в первой строчке происходит выход, если список пустой, ведь никакого смысла сортировать его нет. Затем начинается цикл по байтам ключа, в самом начале которого массив хвостов должен указывать на начала списков в массиве Bucket. А дальше идет цикл repeat прохода по списку, в котором ListElem указывает на очередной элемент, KeyIndex получает значение i-го байта ключа, и этот элемент вставляется в список с этом номером. После прохода по списку он снова формируется из списков массива.

Вот и все. Осталось проанализоровать, как время работы процедуры зависит от количества элементов списка. Предположим, что это количество весьма велико, и явно больше размера наших массивов в 256 элементов. В этом случае время циклов по j гораздо меньше цикла, в котором делается проход по всем элементам списка (repeat). А этот обход делается столько раз, сколько байт в ключе. В других местах мы этого ведь не делаем, даже при сращивании массива в единый список они просто соединяются друг с другом 256 раз. Таким образом, можно сказать, что время работы этой процедуры линейно зависит от количества элементов списка. Этот факт обычно обозначают как T = O(n). Великолепное соотношение, например, QuickSort, алгоритм, который, в частности, применяется при сортировке TStringList и во многих других местах, имеет время работы T= O(n*log(n)). К сожалению, алгоритм цифровой сортировки имеет ограничения, сортируем-то мы список, а не массив, да и ключ должен быть достаточно мал. Именно поэтому данный алгоритм применяют достаточно редко, он не универсален, да и количество сортируемых элементов должно быть большим...

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

   Внимание! Запрещается перепечатка данной статьи или ее части без согласования с автором. Если вы хотите разместить эту статью на своем сайте или издать в печатном виде, свяжитесь с автором.
Автор статьи:  Роман Игнатьев
  

Другие статьи Наверх


  Рейтинг@Mail.ru     Титульная страница Поиск, карта сайта Написать письмо