Быстрая сортировка
Санек 21 дек 2011
Словесный алгоритм
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 то запускаем сортировку от этих границ.
Теперь сам код:
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.
Sasha 24 дек 2011
лучше сравнивать не с средним элементом, а со случайным. При сравнении с средним часто делают тесты, что сорт ловит тле. http://informatics.m...4&chapterid=665 .
Илья М. 24 янв 2012
В задаче Меньшикова Анти QuickSort сравнивают опять же со средним элементом, я думаю что "завальных" тестов на средний элемент гораздо меньше, а на случайный может случайно вылезти плохой тест
Lenmult 28 авг 2019
Наткнулся на ошибку в коде второго примера.. запуск программы вывел мне странный реультат:
До сортировки:
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
Не пойму отчего так произошло? код переписан из примера полностью.
До сортировки:
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
Не пойму отчего так произошло? код переписан из примера полностью.