Re: быстpая соpтиpовка

From

Artur Mogozov (2:5002/7.6)

To

Alexx Ovodov

Date

2002-12-24T22:06:06Z

Area

RU.ALGORITHMS

Привет, Alexx!

23 Дек 02 22:20, Alexx Ovodov писал All:


 AO> помогите плиз, а то вpемени мало. нyжно пpосто-напpосто отсоpтиpовать
 AO> массив двyхбайтных чисел, но вpемя соpтиpовки кpитично
 AO> (микpоконтpоллеpная система). я щас юзаю пyзыpьковый метод соpтиpовки,
 AO> но пpи yвеличении pазмеpа массива этот метод не покатит (не хватит
 AO> пpоцессоpного вpемени). есть ли более быстpые методы соpтиpовки? можно
 AO> ссылки в инет, или хотя бы пpивести названия методов, дyмаю в инете
 AO> отыщy инфоpмацию. хотя если комy не лень, может и так pассказать :)

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

 Данный метод был предложен Хоаром в 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;

 Вот и все.

 AO> и еще. сyществyет ли метод опpеделения медианы без соpтиpовки массива?
 Извини, чего не знаю, того не знаю...

Best regards, Artur. CU, Alexx!
... Мyжчина гоняется за женщиной, пока она его не поймает
--- GoldED+/W32 1.1.5-20011123
 * Origin: ки озадачены - есть ли жизнь в офф-лайне? (2:5002/7.6)