сортировка
Добавлено: 11 апр 2010, 19:04
Предложить алгоритм сортировки за время 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 ;
( Если оба отрезка не кончены и первые невыбранные элементы в них равны то допустимы оба действия , в программе выбрано первое .)
Остается лишь переписать результат слияния обратно в массив х.
(Предупреждение. Если обратное копирование выполняется вне процедуры слияния, то не забудьте про последний отрезок.)
Программа имеет привычный дефект : обращение к несуществующим элементам массива при вычислении булевских выражений.
Пример :
Пусть 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 ;
( Если оба отрезка не кончены и первые невыбранные элементы в них равны то допустимы оба действия , в программе выбрано первое .)
Остается лишь переписать результат слияния обратно в массив х.
(Предупреждение. Если обратное копирование выполняется вне процедуры слияния, то не забудьте про последний отрезок.)
Программа имеет привычный дефект : обращение к несуществующим элементам массива при вычислении булевских выражений.