Школа программиста

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Устанавливаем I=1 и J=N. Сравниваем элементы A[I] и A[J]. Если A[I]<=A[J], то уменьшаем J на 1 и проводим следующее сравнение элементов A[I] с A[J]. Последовательное уменьшение индекса J и сравнение указанных элементов A[I] с A[J] продолжаем до тех пор, пока выполняется условие A[I] <= A[J]. Как только A[I] станет больше A[J], меняем местами элементы A[I] с A[J], увеличиваем индекс I на 1 и продолжаем сравнение элементов A[I] с A[J]. Последовательное увеличение индекса I и сравнение (элементов A[I] с A[J]) продолжаем до тех пор, пока выполняется условие A[I] <= A[J]. Как только A[I] станет больше A[J], опять меняем местами элементы A[I] с A[J], снова начинаем уменьшать J.

Чередуя уменьшение J и увеличение I, сравнение и необходимые обмены, приходим к некоторому элементу, называемому пороговым или главным, характеризующим условие I=J. В результате элементы массива оказываются разделенными на две части так, что все элементы слева - меньше главного элемента, а все элементы справа - больше главного элемента. К этим массивам применяем рассмотренный алгоритм, получаем четыре части и т.д. Процесс закончим, когда массив A станет полностью отсортированным.

При программировании алгоритма "Быстрой сортировки" удобно использовать рекурентные вызовы процедуры сортировки (рекурсию).

{Быстрая сортировка}
var a:array[1..10] of integer; { массив элементов }
    n:integer;

procedure QuickSort( L, R : Integer ); { Быстрая сортировка массива A[] }
var i,j,x,y : integer;
begin
  i := l; j := r;
  x := a[(l+r) div 2];
  repeat
    while (A[i] < x) do inc(i);
    while (x < A[j]) do dec(j);
    if ( i <= j ) then
    begin
      y:=A[i]; a[i]:=a[j]; a[j]:=y;
      inc(i); dec(j);
    end;
  until (i > j);
  if (l < j) then QuickSort(l,j);
  if (i < r) then QuickSort(i,r);
end;

begin
     writeln('введите 10 элементов массива:');
     for n:=1 to 10 do readln(a[n]);
     QuickSort( 1, 10 ); { на входе: левая и правая граница сортировки }
     writeln('после сортировки:');
     for n:=1 to 10 do writeln(a[n]);
end.


Красноярский краевой Дворец пионеров, (c)2006 - 2017, ICQ: 151483