Перейти к содержимому


- - - - -

Быстрая сортировка


Сообщений в теме: 3

#1 Санек

    Продвинутый пользователь

  • Администраторы
  • 41 сообщений
  • ГородВитебск

Отправлено 21 декабря 2011 - 17:52

Словесный алгоритм

1)Устанавливаем левую и правую границу l и r(с какого по какой элемент мы хотим отсортировать) .

2)Находим средний элемент между правой и левой границей x (относительно этого элемента мы будем сортировать наш массив) .


3) Пока индикатор i > индикатора j то:

а) Теперь (если сортируем по возрастанию) то ищем слева , от среднего элемента x , элемент который >=x

б) А справа элемент который <=x

в) И если индикаторы i и j не пересеклись то меняем местами элементы a[ i ] и a[ j ] и увеличиваем(или уменьшаем) индикаторы i и j

4) Если индикатор j < правой границы r то запускаем сортировку от этих границ.

5) И если индикатор j > левой границы l то запускаем сортировку от этих границ.


Теперь сам код:

var a:array [1..1000000] of longint;
    i,n:longint;
procedure qSort(l,r:longint);
  var i,j,z,x:longint;
begin
   i:=l;
   j:=r;
   x:=a[(i+j)div 2];{находим  средний элемент}
   repeat
	while a[i]<x do i:=i+1;{ищем слева элемент который >=x }
	while a[j]>x do j:=j-1;{а справа элемент который <=x }
	if i<=j then begin
                        z:=a[i];
                        a[i]:=a[j];
                        a[j]:=z;
                        i:=i+1;
                        j:=j-1;
                      end; {меняем местами элементы a[i] и a[j] и изменяем индикаторы i и j}
   until (i>j);
   if i<r then qSort(i,r);
   if j>l then qSort(l,j);
end;
begin        
readln(n);
for i:=1 to n do
  read(a[i]);
qSort(1,n); {задаём границы сортировки}
for i:=1 to n do
  write(a[i],' ');
end.


#2 Sasha

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений

Отправлено 24 декабря 2011 - 07:01

лучше сравнивать не с средним элементом, а со случайным. При сравнении с средним часто делают тесты, что сорт ловит тле. http://informatics.m...4&chapterid=665 .

#3 Илья М.

    Новичок

  • Пользователи
  • Pip
  • 9 сообщений

Отправлено 24 января 2012 - 08:10

В задаче Меньшикова Анти QuickSort сравнивают опять же со средним элементом, я думаю что "завальных" тестов на средний элемент гораздо меньше, а на случайный может случайно вылезти плохой тест :)

#4 Я. Илья

    Пользователь

  • Пользователи
  • PipPip
  • 11 сообщений
  • ГородВитебск

Отправлено 31 июля 2012 - 09:27

Не вылезет





Количество пользователей, читающих эту тему: 1

0 пользователей, 1 гостей, 0 анононимных