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


- - - - -

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


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

#1 Санек

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

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

Отправлено 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
  • 1 сообщений

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

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

#3 Илья М.

    Новичок

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

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

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

#4 Я. Илья

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

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

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

Не вылезет

#5 Lenmult

    Новичок

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

Отправлено 28 августа 2019 - 03:49

Наткнулся на ошибку в коде второго примера.. запуск программы вывел мне странный реультат:
До сортировки:
549
593
716
845
603
858
545
848
424
624

После сортировки:
424
549
545
845
603
858
716
848
593
629


Из примера видно, что элементы попеременно поменялись местами:
2 с 9 , 1 со 2 , 3 с 6

Не пойму отчего так произошло? код переписан из примера полностью.





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

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