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


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


Одним из способов сортировки разделением (см.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).




Начало  Назад  Вперед



Книжный магазин