сортировка

[topo]

Предложить алгоритм сортировки за время n log n (число операций при сортировке n элементов не больше C n log n для некоторого C ы для всех n).


Пример :
Пусть k – положитэльноэ целое число. Разобьем массив x[1]….x[n] на отрезки длины k.
(Первый – x[1]…..x[n], затем x[k+1]…x[ 2k] и так далее) .последний отрезок будет неполным , если n не делится на k. Назовем массив k-упорядоченным, если каждый ыз этих отрезков в отдельности упорядочен. Любой массив 1-упорядочен. Если массив k- упорядочен и n≤ k, то он упорядочен.
Мы опишем, как преобразовать k-упорядоченный массив в 2k- упорядоченный (из тех же элементов). С помощью этого преобразования алгоритм записывается так:
K:=1 ;
{массив x является к- упорядоченным}
While k< n do begin
….. преобразовать к- упорядоченным массив в 2к-упорядоченний ;
K := 2 *k ;
End ;
Требуемое преобразование состоит в том, что мы многократно “сливаэм ” два упорядочених отрезка длины не больше k в один упорядоченный отрезок. Пусть процедура
Слияние( p, q, r: integer )
При p<равно q< равно r сливает отрезки x[p+1]….x[q] x[q+1]….x[r] в упорядочений отрезок x[p+1]….. x[r] ( не затрагивая других частей массива x).

P q r

упорядоченный упорядоченный
↓

упорядоченный

Тогда преобрезование k-упорядоченного массива в 2k упорядочений осуществляется так:

t=0 ;
{t кратно 2k или t=n, x[1]……..x[t] является 2k- упорядоченним ж остаток массива х не изменился}
While t + k < n do begin
p:=t ;
q:=t=k ;
r:= min (t+2*k, n) ;
{min(a,b) – минимум из a и b}
t:=r ;
end ;

слияние требует вспомогательного массива для записи результатов слияния- обозначим его b. Через p0 и q0 обозначим номера последних элементов участков, подвергшихся слиянию, s0- последний записанный в массив b элемент. На каждом шаге слияния производится одно из двух действий:

b[s0+1]:=x[p0+1] ;
p0:=p0+1 ;
b0:=-b0+1 ;

или
b[s0+1]:=x[q0+1] ;
q0:=0+1 ;
b0:=b0+1 ;
(любителі язика с написали бы в этом случае b[++s0]=x[++p0] b b[++s0]=x[++q0].) первое действие (взятие элемента из первого отрезка) может производиться при одновременном выполнении двух условий:
(1) первый отрезок не кончился (p0<q) ;
(2) второй отрезок кончился (q0=r) или не кончился, но элемент в нем не меньше очередного элемента первого отрезка [(q0<r) b (x[p0+1]≤ x [q0+1])].
Аналогично для второго действия. Итак, получаем
p0 :=p ; q0:=q ; s0 :=p ;
while (p0 <> q ) or (q0<> r ) do begin
if ( p0<q) and ((q0=r) or ((q0<r) and (x[p+1] <= x[q0+1]))) then begin
b [s0+1] :=x [p0+1] ;
p0 :=p0+1 ;
s0 :=s0+1 ;
end else begin
{(q0<r) and ((p0=q) or ((p0=r) and (x[p0+1] >=x [q0+1])))}
b [s0+1] :=x [q0+1] ;
q0 :=q0+1 ;
s0 :=s0+1 ;
end ;
end ;
( Если оба отрезка не кончены и первые невыбранные элементы в них равны то допустимы оба действия , в программе выбрано первое .)
Остается лишь переписать результат слияния обратно в массив х.
(Предупреждение. Если обратное копирование выполняется вне процедуры слияния, то не забудьте про последний отрезок.)
Программа имеет привычный дефект : обращение к несуществующим элементам массива при вычислении булевских выражений.

[WinMain]

Слишком много написано, у меня так и не хватило терпения дочитать до конца (или это я уже такой ленивый стал)...
Что касается алгоритма сортировки, у которого время выполнения характеризуется O(N log N), то для этого вполне подходит алгоритм "быстрой сортировки" (QuickSort), которая применяется в большинстве стандартных библиотек C/C++. Там исходный массив сначала делится пополам, потом каждая из этих половинок делится ещё пополам и так до тех пор, пока каждый их отдельных кусочков массива не достигнет минимальной длины, необходимой для его сортировки каким-нибудь из простых известных способов (например, методом вставок). Потом все отсортированные куски массива объединяются в один массив.
Похожий способ применяется в алгоритме так называемой "карманной" сортировки, или как её ещё называют "корзинная" сортировка (BucketSort). В отличие от алгоритма быстрой сортировки, карманная сортировка делит исходный массив на отдельные подмассивы (карманы) по диапазону значений элементов. Так, например: значениея от 0 до 99 могут располагаться в первом кармане, значения от 100 до 199 - во втором, от 200 до 299 - в третьем и т.д. Далее идёт сортировка в каждом карамене каким-то известным способом (например: методом Шелла или методом подсчёта для целочисленных элементов). Потом все элементы, начиная с первого кармана, по порядку записываются в один общий массив.
Суть этих методов состоит в том, что быстрее отсортировать 100 массивов по 10 элементов, чем один массив из 1000 элементов.

[Romeo]

Перемещено из "С и С++".