Warning: Illegal string offset 'html' in /var/www/lvp37/data/www/lvp37.ru/cache/skin_cache/cacheid_1/skin_topic.php on line 909
Быстрая сортировка - олимпиадники-информатики

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


- - - - -

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


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

#1 Санек

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

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

Отправлено 21 December 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 December 2011 - 07:01

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

#3 Илья М.

    Новичок

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

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

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

#4 Я. Илья

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

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

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

Не вылезет

#5 Lenmult

    Новичок

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

Отправлено 28 August 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

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

#6 StepPemia

    Новичок

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

Отправлено 08 March 2020 - 17:31

Cialis Et Glaucome Buy Cialis Levitra 20mg Bayer Cialis Cheap Viagra No Perscription

#7 StepPemia

    Новичок

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

Отправлено 08 March 2020 - 17:32

Pillenpharm Viagra Strips Buy Cialis Viagra Naturale Femminile Buy Cialis Viagra Oder Cialis Was Ist Besser

#8 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:40 PM

Интим-услуги – вот что вам нужно! http://silich.ru/for...24249#post24249 Индивидуалки https://saharokclub....icheskij-sponzh

#9 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:41 PM

Проститутки https://www.synthoni...=user&id=590208 Мы приглашаем девушек поместить своё объявление на ресурс. http://5zet.ru/commu...new#message3063

#10 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:41 PM

Индивидуалки http://www.korolev.3...php?p=7872#7872 найти идеальную проститутку http://www.xn--80aad...=new#message642

#11 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:42 PM

найти идеальную проститутку https://saharokclub....icheskij-sponzh Индивидуалки https://kazan.ros-sp...ew#message58099

#12 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:42 PM

найти идеальную проститутку http://forum.compute...ost/1324/#p1324 Интим-услуги – вот что вам нужно! https://www.5lb.ru/p...php?f=2&t=14365

#13 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:43 PM

Путаны есть на любой изысканный вкус http://24shop7.ru/fo...elyabinska#6152 от дешевых до элитных http://holodonline.c...ew#message65955

#14 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:43 PM

Путаны есть на любой изысканный вкус https://mir09.info/t...stitutki-kazani Путаны есть на любой изысканный вкус http://www.sitebs.ru/blogs/61109.html

#15 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:44 PM

найти идеальную проститутку http://xn--90ahc1ac7...ew#message47297 Проститутки http://www.mamalipet...owtopic&id=4514

#16 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:44 PM

Путаны https://forum.b-m-w....tki-krasnodara/ элитные индивидуалки по вызову http://payhotel.ru/f...new#message5224

#17 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:45 PM

Мы приглашаем девушек поместить своё объявление на ресурс. http://autoclub36.ru...php?f=23&t=6868 Путаны есть на любой изысканный вкус http://energo-sibir....new#message1336

#18 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:45 PM

Индивидуалки http://komiwiki.sykt...tle=Проститутки Челябинска Проститутки http://kids289.ru/pr...ki-chelyabinska

#19 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:46 PM

элитные индивидуалки по вызову http://electro-mn.ru/node/19079 Мы приглашаем девушек поместить своё объявление на ресурс. http://ucps-ekb.ru/f...00138/10026590/

#20 Forexomike

    Новичок

  • Пользователи
  • Pip
  • 2 сообщений
  • Городexcel training

Отправлено Сегодня, 01:46 PM

Интим-услуги – вот что вам нужно! http://www.mystoma.o...-ekaterinburga/ Мы приглашаем девушек поместить своё объявление на ресурс. http://wiki.kinokadr...tle=Проститутки Екатеринбурга





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

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