Информатика и технология программирования

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


Одним из способов сортировки разделением (см.3.7) является поразрядная сортировка разделением. Массив сортируемых значений делится на две части так, что в левой оказываются значения со старшим значащим битом, равным 0, а в правой -со значением 1. Затем обе части массива делятся в свою очередь каждая на 2 части по значению следующего правого бита и так далее. В результате, когда мы доберемся до младшего бита, массив окажется упорядоченным. Покажем это на примере с небольшим количеством разрядов:


13 6 11 15 8 14 Исходный
1101 0110 1011 1111 1000 1110 массив
-- ------------------------ Разделение
6 15 13 11 8 14 по биту 3
-- --------- --------- Разделение
6 11 8 15 13 14 по биту 2
-- -- -- -- --------- Разделение
6 8 11 13 15 14 по биту 1
-- -- -- -- -- -- Разделение
6 8 11 13 14 15 по биту 0

В нашем примере после выполнения разделения по 3-у биту массив делится на две части, границей которых является значение 8. Затем обе части делятся пополам со значениями границ, определяемых 2-м битом, т.е. 4 и 12 и т.д..


void bitsort(int A[],int a,int b, unsigned m)
{
int i;
if (a+1 &#62= b) return; // Интервал сжался в точку


if (m == 0) return; // Проверяемые биты закончились


// Маска после сдвига стала 0


// Разделить массив на две части по значению бита,


// установленного в m, i - граница разделенных частей


bitsort(A,a,i,m &#62&#62 1);
bitsort(A,i+1,b,m &#62&#62 1);
}

Приведенная функция выполняет поразрядную сортировку части массива A, ограниченного индексами a и b. Этот интервал разделяется на две части (интервалы a..i, i+1..b), в которые попадают значения элементов массива соответственно с нулевым и единичным значением проверяемого бита. Сам бит задается маской m -переменной, в котором его значение установлено в 1. Затем функция вызывает самое себя для обработки полученных частей, для которых выполняется разделение по следующему правому биту. Для этого текущая маска m сдвигается на 1 разряд вправо. Вызов функцией самой себя называется рекурсией (см.5.4).


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

void mainsort(int B[], int n)
{
int max,i;
unsigned m;
for(max = 0, i=0; i&#60 n; i++)
if (B[i] &#62 max) max = B[i];
for (m=1; m &#60 max; m &#60&#60= 1);
m &#62&#62=1;
bitsort(B,0,n-1,m);
}

Для разделения интервала массива по заданному биту происходит по принципу "сжигания свечи с двух концов". Два индекса (i и j) движутся от концов интервала к середине, оставляя после себя слева и справа разделенные элементы. На каждом шаге производится сравнение битов по маске m в элементах массива, находящихся по указанным индексам (граница неразделенной части массива). В зависимости от комбинации битов (4 варианта) производится перестановка элементов и перемещение одного или обоих индексов к середине:

СОСТОЯНИЕ ПАРЫ ЭЛЕМЕНТОВ СДВИГ ГРАНИЦ
Оба на месте 0 1 Сдвинуть обе
Размещены наоборот 1 0 Переставить элементы, сдвинуть обе
Левый на месте 0 0 Сдвинуть левую
Правый на месте 1 1 Сдвинуть правую

{
int j,vv; // Цикл разделения массива
for (i=a, j=b; i&#60j; ) // в поразрядной сортировке
if ((A[i] &#38 m) ==0)
{
if ((A[j] &#38 m) !=0) i++,j--; // Вариант 0,1
else i++; // Вариант 0,0
}
else
{
if ((A[j] &#38 m) !=0) j--; // Вариант 1,1
else // Вариант 1,0
{
vv = A[i]; A[i]=A[j]; A[i]=vv;
i++, j--;
}
}
if ((A[i] &#38 m)!=0) i--; // Уточнить границу разделения


Содержание раздела