Re: Алгоритмы сортировк

From

Artur Mogozov (2:5002/7.6)

To

Vlad Salikov

Date

2002-12-11T16:28:30Z

Area

RU.ALGORITHMS

Привет, Vlad!

09 Дек 02 02:39, Vlad Salikov писал Kirill Usatov:

 AV>>> Хотелось бы поиметь ОЧЕНЬ быстрый алгоритм сортировки
 AV>>> одномерного набора чисел (как по возрастанию так и по убыванию).
 AV>>> Набор относительно большой (м.б. до 10000 значений). Смотрю на
 AV>>> Excel и так завидно становится, как там все мгновенно
 AV>>> происходит. :))
 KU>> поимей метод Хоаpа Ж)
 VS>  А где бы его поиметь?

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

 Данный метод был предложен Хоаром в 1962 году. В общем случае его
эффективность довольно высока ( O(n*log n) ), поэтому автор назвал его "быстрой
сортировкой". Такая эффективность достигается за счет отсечения ненужных
перестановок для уже отсортированного массива.

 Алгоритм.

 В исходном массиве А выбирается некоторый элемент Х ("барьерный"). Целью я
вляется запись Х на "свое место" в массиве, пусть это будет место k, такое,
чтобы слева от Х были элементы меньше, либо равные, а справа большие Х. То есть
A[1], A[2], ..., A[K-1], A[K]=X, A[K+1], ..., A[N].
В результате массив А разделен на две неупорядоченные части, барьером между
которыми является A[k]. Далее требуется сортировать полученные части таким же
образом до тех пор, пока в каждой части не останется по одному элементу, то есть
пока не будет отсортирован весь массив.

 Программа.

 Procedure QuickSort(m,t:Integer); {Первый вызов QuickSort(1,N)}
 Var
  i,j,x,w:Integer;
 Begin
  i:=m;
  j:=t;
  x:=a[ (m+t) div 2 ]; {}
  Repeat
   While a[i] < x do Inc(i);
   While a[j] > x do Dec(j);
   If i <= j Then
    Begin
     w:=a[i];
     a[i]:=a[j];
     a[j]:=w;
     Inc(i);
     Dec(j);
    End;
  Until i > j;
  If m<j Then QuickSort(m,j);
  If i<t then QuickSort(i,t);
 End;

 Вот и все.

Best regards, Artur. CU, Vlad!
... Голубые ели, спали и орали
--- GoldED+/W32 1.1.5-20011123
 * Origin: ю жизнь. Сохpанить? (Да/Нет) (2:5002/7.6)