Пример карманной сортировки написаный на паскале

Меню сайта

Наш опрос

Статистика

Онлайн всего: 1

Гостей: 1

Пользователей: 0

   program Sort;
   var
      i,j,n,k:longint;
      a:array[1..100000] of longint;
      b:array[1..1000,1..1000] of longint;
      razmer:array[1..1000] of integer;

{с помощью QSort мы будем сортировать карманы}
      procedure QSort(first,last:integer);
      var
         L,R,c,X:integer;
      begin
         if first < last then
         begin
            X:= b[i,(first + last) div 2];
            L:= first;
            R:= last;
            while L <= R do
            begin
                while b[i,L] < X do
                   L:= L + 1;
                while b[i,R] > X do
                   R:= R - 1;
                if L <= R then
                begin
                   c:=b[i,L];
                   b[i,L]:=b[i,R];
                   b[i,R]:=c;
                   L:=L+1;
                   R:=R-1;
                end;
             end;
     QSort(first, R);
     QSort(L, last);
     end;
   end;


{заполняем массив}
   begin
      read(n);
      for i:=1 to n do
         a[i]:=random(10000);

{выводим исходный массив}
      for i:=1 to n do
         write(a[i],' ');

{раббиваем массив на карманы}
      for i:=1 to n do
      begin
         b[(a[i] div 10)+1,razmer[(a[i] div 10)+1]+1]:=a[i];
         razmer[(a[i] div 10)+1]:=razmer[(a[i] div 10)+1]+1;
      end;

{сортируем карманы}

      for i:=1 to 1000 do
         if razmer[i]<>0 then Qsort(1,razmer[i]);

{восстанавливаем массив}
      k:=0;
      for i:=1 to 1000 do
      for j:=1 to razmer[i] do
      begin
         k:=k+1;
         a[k]:=b[i,j];
      end;

{выводим отсортированный массив}
      writeln;
    writeln;
      for i:=1 to n do
      write(a[i],' ');
   end.

Форма входа

Поиск

Мы в сети

Для того чтобы не видеть рекламу в правом верхнем углу сайта пройдите простую процедуру регистрации

ФОРУМ

Форум

У нас наконецто появился форум! Добро пожаловать! Будьте первыми, задайте направление форуму! =)

--- Не стесняемся - заходим на форум! ---