Delphi-Help

  • Increase font size
  • Default font size
  • Decrease font size
Главная

Алгоритм 6. Быстрая сортировка

Оцените материал
(1 Голосовать)

Алгоритм 6. Быстрая сортировка

Теперь переходим к самому интересному, а именно к одной из самых быстрых и эффективных из известных сортировок, которая так и называется — «быстрая сортировка».

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

Program QuickSort;   
Var A  : array[1..1000] of integer;   
    N,T : integer;    
Procedure Sort(p,q : integer); {p,q — индексы начала и конца сортируемой части массива}  
Var i,j,r : integer;   
Begin   
 if p<q then {массив из одного элемента тривиально упорядочен}  
 begin  
  r:=A[p];   
  i:=p-1;   
  j:=q+1;   
  while i<j do  
   begin  
    repeat  
     i:=i+1;   
    until A[i]>=r;   
    repeat  
     j:=j-1;   
    until A[j]<=r;   
    if i<j then  
     begin  
      T:=A[i];   
      A[i]:=A[j];   
      A[j]:=T;   
     end;   
   end;   
  Sort(p,j);   
  Sort(j+1,q);   
 end;   
End;   
Begin   
 {Определение размера массива A — N) и его заполнение}  
    
 {запуск сортирующей процедуры}  
 Sort(1,N);   
 {Вывод отсортированного массива A}  
     
End.  
 
Program QuickSort;
Var A  : array[1..1000] of integer;
    N,T : integer; 
Procedure Sort(p,q : integer); {p,q — индексы начала и конца сортируемой части массива}
Var i,j,r : integer;
Begin
 if p<q then {массив из одного элемента тривиально упорядочен}
 begin
  r:=A[p];
  i:=p-1;
  j:=q+1;
  while i<j do
   begin
    repeat
     i:=i+1;
    until A[i]>=r;
    repeat
     j:=j-1;
    until A[j]<=r;
    if i<j then
     begin
      T:=A[i];
      A[i]:=A[j];
      A[j]:=T;
     end;
   end;
  Sort(p,j);
  Sort(j+1,q);
 end;
End;
Begin
 {Определение размера массива A — N) и его заполнение}
 {запуск сортирующей процедуры}
 Sort(1,N);
 {Вывод отсортированного массива A}
  
End.

Что же делает данный алгоритм таким быстрым? Ну во-первых, если массив каждый раз будет делится на приблизительно равные части, то для него будет верно то же соотношение, что и для сортировки слиянием, т. е. время работы будет O(nlog2n). Это уже само по себе хорошо. Кроме того, константа при nlog2n очень мала, ввиду простоты внутреннего цикла программы. В комплексе это обеспечивает огромную скорость работы. Но как всегда есть одно «но». Вы, наверное, уже задумались: а что если массив не будет делится на равные части? Классическим примером является попытка «быстро» отсортировать уже отсортированный массив. При этом данные каждый раз будут делиться в пропорции 1 к n-1, и так n раз. Общее время работы при этом будет O(n2), тогда как вставкам, для того чтобы «понять», что массив уже отсортирован, требуется всего-навсего O(n). А на кой нам сортировка, которая одно сортирует хорошо, а другое плохо? А собственно, что она сортирует хорошо? Оказывается, что лучше всего она сортирует случайные массивы (порядок элементов в массиве случаен). И поэтому нам предлагают ввести в алгоритм долю случайности. А точнее, вставить randomize и вместо r:=A[p]; написать r:=A[random(q-p)+p]; т. е. теперь мы разбиваем данные не относительно конкретного, а относительно случайного элемента. Благодаря этому алгоритм получает приставку к имени «вероятностный». Особо недоверчивым предлагаю на своем опыте убедится, что данная модификация быстрой сортировки сортирует любые массивы столь же быстро.

А теперь еще один интересный факт: время O(nlog2n) является минимальным для сортировок, которые используют только попарное сравнение элементов и не использует структуру самих элементов. Тем, кому интересно, откуда это взялось, рекомендую поискать в литературе, доказательство я здесь приводить не намерен, не Дональд Кнут, в конце концов :-). Но вы обратили внимание, что для рассмотренных алгоритмов в принципе не важно, что сортировать — такими методами можно сортировать хоть числа, хоть строки, хоть какие-то абстрактные объекты. Следующие сортировки могут сортировать только определенные типы данных, но за счет этого они имеют рекордную временную оценку O(n).

Прочитано 4474 раз
Авторизуйтесь, чтобы получить возможность оставлять комментарии
Гнев Титанов
Повседневный макияж. colourmebeautiful.com.ua . я уже прикупил себе несколько билетов на guano apes киев покупал с доставкой

Авторизация



Счетчики