Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 22.11.2006, 01:05
незарегистрированный

 
Сообщений: n/a

двоичная (поразрядная) быстрая сортировка
добрый вечер! помогите, надо написать человеку реализацию алгоритма двоичной сортировки (еще она называется поразрядная).
на этом сайте нашел описание и приведеный код на си. но мне надо писать на паскале. а описалово очень мутное и непонятное.
подскажите, где можно найти блок-схему метода, или хотя бы его нормальное описание?
  #2  
Старый 22.11.2006, 08:52
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

в книгах седжвика "фундаментальные алгоритма на..." хорошо описано, с простыми и понятными исходниками
  #3  
Старый 23.11.2006, 12:06
Пользователь

Отправить личное сообщение для AndreySUrSU Посмотреть профиль Найти все сообщения от AndreySUrSU
 
Регистрация: 06.10.2006
Адрес: Челябинск
Сообщений: 66

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

for i:=0 to 9 do
count[i]:=0;

for i:=0 to N-1 do
inc(count[getRazr(a[i],k)]); k - текущий разряд

Теперь подсчитываем начальную позицию каждого разряда в резйльтирующем массиве.

pos[0]:=0;
for i:=1 to 9 do
pos[i]:=pos[i-1]+count[i-1];

Переносим во временный массив
for i:=0 to N-1 do begin
tmp[pos[getRazr(a[i],k)]] = a[i];
inc(pos[getRazr(a[i],k)]);
end;

Потом копируем тмп в а. Далее сортируем по след разряду.
Тут я использовал нумерацию с 0.
  #4  
Старый 24.11.2006, 00:47
незарегистрированный

 
Сообщений: n/a

спасибо, но эт я видел. подобные конструкции на паскале и си встречал.
а вот обычной блок-схемы, из которой стало бы понятно как писать на любом языке - не встречал...
  #5  
Старый 24.11.2006, 08:22
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

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

Код:
procedure BQuickSort(var A: array of Integer; l, r, Bit: Integer);
var
  i, j, Mask, Temp: Integer;
begin
  if (r <= l) or (Bit > 8 * SizeOf(Integer)) then
    Exit;
  i := l;
  j := r;
  Mask := 1 shl (8 * SizeOf(Integer) - Bit - 1);
  while i <> j do begin
    while ((A[i] and Mask) = 0) and (i < j) do Inc(i);
    while ((A[j] and Mask) <> 0) and (i < j) do  Dec(j);
    Temp := A[i];
    A[i] := A[j];
    A[j] := Temp;
  end;
  if ((A[r] and Mask) = 0) then Inc(j);
  BQuickSort(A, l, j - 1, Bit + 1);
  BQuickSort(A, j, r, Bit + 1);
end;
  #6  
Старый 22.05.2010, 22:56
гость

 
Сообщений: n/a

дОБРЫЙ ВЕЧЕР!! ПОМОГИТЕ НАПИСАТЬ ПРОГРАММУ ПОРАЗРЯДНОЙ СОРТИРОВКИ,ВВОД/ВЫВОД ДАННЫХ.....ПОЖАЛУЙСТА..ОЧЕНЬ НАДО
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра