Обсуждение:Сортировка перемешиванием
Последнее сообщение: 11 лет назад от Mileikovskij
Уважаемые участники! В данной статье алгоритм не соответствует описанию! Проблема в том, что на каждой итерации граница смещается только на единицу, а в тексте статьи четко сказано: "Во-первых, если при движении по части массива перестановки не происходят, то эта часть массива уже отсортирована и, следовательно, ее можно исключить из рассмотрения." Поэтому предлагается взять за основу алгоритм с Викиучебника на Паскале и C: ( ru.wikibooks.org/wiki/Примеры_реализации_сортировки_перемешиванием ) Мои комментарии набраны всеми большими буквами. Код на Паскале:
k:= 25; {Индекс последнего изменения}
s:= 1; {Первый элемент массива}
e:= 25; {Последний элемент массива}
while e > s do
begin
for i:= e downto s+1 do if Arr[i] < Arr[i-1] then
begin
tmp := Arr[i];
Arr[i] := Arr[i-1];
Arr[i-1] := tmp;
k := i; {ЗАПОМИНАЕМ ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!}
end;
s:=k; {СМЕЩАЕМ ГРАНИЦУ НА ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!}
for i:= s to e-1 do if Arr[i]>Arr[i+1] then
begin
tmp := Arr[i];
Arr[i] := Arr[i+1];
Arr[i+1] := tmp;
k := i; {ЗАПОМИНАЕМ ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!}
end;
e:=k; {СМЕЩАЕМ ГРАНИЦУ НА ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!}
end;
Код на С:
#define SWAP(A,B) {(A)=(A)^(B); (B)=(A)^(B); (A)=(A)^(B);}
void m_sheker(int mas[], int n)
{
int last = n-1, left = 1, right = n-1, j;
do
{
for(j = right; j >= left; j--)
{
if(mas[j-1] > mas[j])
{
SWAP(mas[j-1], mas[j]);
last = j; //ЗАПОМИНАЕМ ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!
}
}
left = last + 1; //СМЕЩАЕМ ГРАНИЦУ НА ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!
for(j = left; j <= right; j++)
{
if(mas[j-1] > mas[j])
{
SWAP(mas[j-1], mas[j]);
last = j; //ЗАПОМИНАЕМ ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!
}
}
right = last-1; //СМЕЩАЕМ ГРАНИЦУ НА ПОСЛЕДНИЙ ОТСОРТИРОВАННЫЙ ЭЛЕМЕНТ!
} while(left < right);
}