|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Artur Mogozov 2:5002/7.6 24 Dec 2002 23:06:06
To : Alexx Ovodov
Subject : Re: быстpая соpтиpовка
--------------------------------------------------------------------------------
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)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
