Поразрядная сортировка, общий принцип

Поразрядная сортировка, общий принцип

Aвтор:this
Дата: 10.05.2002
Просмотров: 132893
реализации(C++: 1шт...) +добавить

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

В двух словах: поразрядная сортировка подразумевает следующее: сначала элементы сортируются по своему младшему(последнему) разряду, затем следующему(предпоследнему) и т.д. до старшего разряда, первого.

На каждой своей итерации алгоритм включает 2 этапа: распределение и сборка. Скорость работы алгоритмы определяется тем что количество проходов по всем элементам исходного списка(массива и проч.) равна максимальному количеству разрядов в элементе, т.е. разрядов сортируемого ключа. Если мы сортируем числа, то количество разрядов - будет равно количеству десятичных разрядов этого числа, например: 27 - количество разрядов 2, 487 - количество разрядов 3, число 9 - 1 разряд и т.д. В случае же сортировки текстовых строк - количество разрядов будет очевидно определяться количеством букв в строке.

Теперь рассмотрим подробно, что же представляет собой этот алгоритм.

Перед сортировкой необходимо определить 2 величины:

width - максимальное количество разрядов в сортируемых величинах, по-другому - количество разрядов в самом длинном ключе(как мы помним "ключ" = сортируемый элемент).
range - количество возможных значений одного разряда ключа(сортируемого элемента). Т.е. для десятичных чисел очевидно имеем - 10, для 16-тиричных - 16, для строки это будет соответственно количество букв в алфавите: т.о. для строки из русских символов - 33, из английских - 36.

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

Например, пусть имеем исходную последовательность из {11, 24, 9, 59, 21, 98, 76, 8}, для которой определяем width = 2, range = 10, поэтому будет 10 "карманов": список0, список1..., список9. Тогда на первом проходе карманы №2, 3, 5, 7 окажутся пусты, а остальные распределят элементы след. образом:
список0: 9, 8
список1: 11, 21
список4: 24
список6: 76
список8: 98
список9: 59

Далее второй этап - сборка: просто последовательно соединяем один за другим все карманы и располагаем элементы уже в этой последовательности:
9, 8 (<< это был список0), 11, 21 (список1), 24(список4), 76(список 6), 98(список 8), 59(список9)

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

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

псевдокод: реализация на массивах ссылка

// инициализация дополнительных списков - "карманов"
pockets = array[range]
for i = 0 to range - 1
    pockets[i] = newArray
 
// Основной цикл
for step = 0 to width - 1
    // распределение
    for i = 0 to (sortedArr.length - 1)
        // Получаем значение step-го разряда текущего элемента(ключа)
        // ("/" - целочисленное деление)
        currDigit = (sortedArr[i] % range^(step + 1)) / range^step
        pockets[currDigit].add(sortedArr[i]);
 
    // сборка
    k = 0 // индекс элементов новой последовательности
    for i = 0 to range - 1
        for ii = 0 to (pockets[i].length - 1)
            sortedArr[k++] = pockets[i][ii]
    // Очищение карманов
    if step < width - 1
        for i = 0 to range - 1
            pockets[i] = newArray

// инициализация дополнительных списков - "карманов"
pockets = array[range]
for i = 0 to range - 1
    pockets[i] = newArray

// Основной цикл
for step = 0 to width - 1
    // распределение
    for i = 0 to (sortedArr.length - 1)
        // Получаем значение step-го разряда текущего элемента(ключа)
        // ("/" - целочисленное деление)
        currDigit = (sortedArr[i] % range^(step + 1)) / range^step
        pockets[currDigit].add(sortedArr[i]);
    
    // сборка
    k = 0 // индекс элементов новой последовательности
    for i = 0 to range - 1
        for ii = 0 to (pockets[i].length - 1)
            sortedArr[k++] = pockets[i][ii]
    // Очищение карманов
    if step < width - 1
        for i = 0 to range - 1
            pockets[i] = newArray

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

Данный алгоритм примерно выглядит следующим образом:

псевдокод: поразрядная сортировка на односвязном списке ссылка

// Возвращает ссылку на отсортированный односвязный список
// Передается: та же ссылка list, но на неотсортированный список и width
function radixList(list, width, range)
 
  // Дополнительные переменные типа списка(listtype)
  // out - результирующий список, который пока идиентичен
  // исходному
  out  = list;
 
  // Массивы ссылок на головы и хвосты списков карманов                 
  head = newArrayOfList[range]
  tail = newArrayOfList[range]
 
  // Вспомогательная переменная
  rangepow = 1;
 
  for step = 0 to (width - 1)
    // Обнуляем все карманы
    for i = 0 to range - 1
      head[i] = NULL
      tail[i] = NULL
 
    // РАСПРЕДЕЛЕНИЕ >>
    // Проходимся по всему исходному списку
    // пока не будет достигнут конец 
    //(ссылка на текущий элемент - в никуда)
    while list != NULL
      // Получаем значение step-го разряда текущего элемента(ключа)
      // ("/" - целочисленное деление)
      currDigit = (list->val / rangepow) % range;
 
      // получаем ссылку на хвост текущего кармана
      temp = tail[currDigit];
 
      // Если карман пуст, то текущий элемент
      // будет его головой, иначе добавляем текущий элемент
      // в конец кармана
      if head[currDigit]=NULL   head[currDigit] = list;
      else                      temp->next      = list;
 
      // Обновляем хвост текущего кармана
      // чтобы теперь он указывал на новый добавленный 
      // элемент
      temp = tail[currDigit] = list;
      temp->next = NULL;
 
      // Переходим к следующему элементу списка
      list = list->next;
    end while
 
 
    // Находим в переменную i первый непустой карман, 
    // чтобы с него начать сборку. 
    for i = 0 to (range - 1)
      if ( head[i] != NULL ) break;
 
    // СБОРКА >>
    list = head[i];
    temp = tail[i];
    for currDigit = i+1 to range
      if head[currDigit] != NULL
        temp->next = head[currDigit];
        temp       = tail[currDigit];
 
    // !!! важный момент: чтобы на след. итерации в currDigit
    // при "распределении" получить следующий разряд - возводим
    // в степерь вспомогательную переменную:
    rangepow *= range;
  end for
 
  // Возвращаем ссылку на первый элемент отсортированного списка
  return out;

// Возвращает ссылку на отсортированный односвязный список
// Передается: та же ссылка list, но на неотсортированный список и width
function radixList(list, width, range)

  // Дополнительные переменные типа списка(listtype)
  // out - результирующий список, который пока идиентичен
  // исходному
  out  = list;

  // Массивы ссылок на головы и хвосты списков карманов                 
  head = newArrayOfList[range]
  tail = newArrayOfList[range]

  // Вспомогательная переменная
  rangepow = 1;

  for step = 0 to (width - 1)
    // Обнуляем все карманы
    for i = 0 to range - 1
      head[i] = NULL
      tail[i] = NULL
    
    // РАСПРЕДЕЛЕНИЕ >>
    // Проходимся по всему исходному списку
    // пока не будет достигнут конец 
    //(ссылка на текущий элемент - в никуда)
    while list != NULL
      // Получаем значение step-го разряда текущего элемента(ключа)
      // ("/" - целочисленное деление)
      currDigit = (list->val / rangepow) % range;

      // получаем ссылку на хвост текущего кармана
      temp = tail[currDigit];

      // Если карман пуст, то текущий элемент
      // будет его головой, иначе добавляем текущий элемент
      // в конец кармана
      if head[currDigit]=NULL   head[currDigit] = list;
      else                      temp->next      = list;
      
      // Обновляем хвост текущего кармана
      // чтобы теперь он указывал на новый добавленный 
      // элемент
      temp = tail[currDigit] = list;
      temp->next = NULL;

      // Переходим к следующему элементу списка
      list = list->next;
    end while

    
    // Находим в переменную i первый непустой карман, 
    // чтобы с него начать сборку. 
    for i = 0 to (range - 1)
      if ( head[i] != NULL ) break;

    // СБОРКА >>
    list = head[i];
    temp = tail[i];
    for currDigit = i+1 to range
      if head[currDigit] != NULL
        temp->next = head[currDigit];
        temp       = tail[currDigit];

    // !!! важный момент: чтобы на след. итерации в currDigit
    // при "распределении" получить следующий разряд - возводим
    // в степерь вспомогательную переменную:
    rangepow *= range;
  end for

  // Возвращаем ссылку на первый элемент отсортированного списка
  return out;

Скорость, производительность данных алгоритмов пропорциональна ~ O(width*(n + range)), где n - количество сортируемых элементов. Объем потребляемой памяти в случае с массивами пропорционален ~ (range + n), в случае оптимизированной версии для списков ~(n).

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

О том какую именно информацию, и что потом с ней делать - читайте в задаче поразрядная сортировка подсчетом.

Реализации:

C++(1) +добавить

1) Поразрядная сортировка, оптимизированная версия на списках на C++, code #12[автор:-]

Поразрядная сортировка, оптимизированная версия на списках ссылка |режим:

// Тип: элемент списка
typedef struct slist_ { 
  long val;
  struct slist_ *next; 
} slist;
 
slist *radix_list(slist *l) {
    // Вспомогательные переменные
    int i, j, d;
 
    // Параметры сортировки
    int range = 10, width = 2;
    slist *temp, *out, *head[10], *tail[10];
 
    // результирующий массив
    out=l;
 
    int rangepow = 1;
    for (j = 0; j < width; j++) {
        for (i = 0; i < range; i++)
            head[i] = (tail[i] = NULL);
 
        // РАСПРЕДЕЛЕНИЕ
        while ( l != NULL ) {
            // Значение текущего разряда
            d = ((int)(l->val / rangepow)) % range;
            temp = tail[d];
            if (head[d]==NULL) {
              head[d] = l;
            } else {
              temp->next = l;
            }
            temp = tail[d] = l;
            l = l->next;
            temp->next = NULL;
        }
 
        // Находим первый непустой карман
        for (i=0; i < range; i++)
          if ( head[i] != NULL ) break;
 
        // СБОРКА
        l = head[i];
        temp = tail[i];
        for (d = i+1; d < range; d++) {
            if ( head[d] != NULL) { 
                temp->next = head[d];
                temp = tail[d];
            }
        }
        rangepow*=10;
    }
    return (out);
}

// Тип: элемент списка
typedef struct slist_ { 
  long val;
  struct slist_ *next; 
} slist;

slist *radix_list(slist *l) {
    // Вспомогательные переменные
    int i, j, d;

    // Параметры сортировки
    int range = 10, width = 2;
    slist *temp, *out, *head[10], *tail[10];

    // результирующий массив
    out=l;
  
    int rangepow = 1;
    for (j = 0; j < width; j++) {
        for (i = 0; i < range; i++)
            head[i] = (tail[i] = NULL);
    
        // РАСПРЕДЕЛЕНИЕ
        while ( l != NULL ) {
            // Значение текущего разряда
            d = ((int)(l->val / rangepow)) % range;
            temp = tail[d];
            if (head[d]==NULL) {
              head[d] = l;
            } else {
              temp->next = l;
            }
            temp = tail[d] = l;
            l = l->next;
            temp->next = NULL;
        }

        // Находим первый непустой карман
        for (i=0; i < range; i++)
          if ( head[i] != NULL ) break;

        // СБОРКА
        l = head[i];
        temp = tail[i];
        for (d = i+1; d < range; d++) {
            if ( head[d] != NULL) { 
                temp->next = head[d];
                temp = tail[d];
            }
        }
        rangepow*=10;
    }
    return (out);
}

Возвращает указатель на начало отсортированного списка.
slist - тип элемента списка. Может меняться, но главное конечно чтобы в нем присутствовали целочисленное val и ссылка next.

Производительность: ~ O(width*(n + range))
Расход памяти: ~ (n)

Тестировалось на: MS Visual Studio 2005, .NET Framework 2.0

<< назад наверх

*	можно кириллицей (недопустимые символы:?&+=\/%#)
**	только для зарегистрированных пользователей

Популярные задачи:

Поразрядная сортировка, общий принцип

Реализации: