 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Сортування вибором (модифіковане)
|
Читайте также: |
Сортування передбачає два завдання:
1)пошук у таблиці min i max елементів і їхніх порядкових номерів;
2)перестановка min елементів у початок таблиці, а max – у кінець.
Знаходимо спочатку у всій таблиці min i max елемнти і їхні порядкові номери. У нашому випадку мінімальний елемент 2, він стоїть на 4-му місці в таблиці, а максимальний елемент 11, він стоїть на 2-му місці в таблиці. Проводимо обмін min елемента з першим і max елемента з останнім елементом таблиці.
ПЕРЕД ОБМІНОМ max ЕЛЕМЕНТА ОБОВ’ЯЗКОВО ТРЕБА ПЕРЕВІРИТИ, ЧИ НЕ БУВ У РЕЗУЛЬТАТІ ОБМІНУ МІНІМАЛЬНОГО ЕЛЕМЕНТА ПЕРЕМІЩЕНИЙ МАКСИМАЛЬНИЙ ЕЛЕМЕНТ. ЯКЩО ТАК, ТО ЗНАЧЕННЮ ІНДЕКСУ МАКСИМАЛЬНОГО ЕЛЕМЕНТА ПРИСВОЮЄТЬСЯ ЗНАЧЕННЯ ІНДЕКСУ МІНІМАЛЬНОГО ЕЛЕМЕНТА!
Потім повторюються ті самі дії, але вже без першого і останнього елементів таблиці (рис.4).
| Основний алгоритм: | Допоміжний алгоритм: |
| АЛГУск(цілK, N, дійсн таб A[K:N]) АРГ K, N, A РЕЗ А ПОЧ ціл і, j, L, m, дійсн MIN, MAX, R i:=K; j:=N поки і<j пц MIN_MAX(i, j, A, MIN, MAX, L, m) R:=A[i]; A[i]:=A[L]; A[L]:=R якщо A[L]=MAX тоm:=L все R:=A[j]; A[j]:=A[m]; A[m]:=R i:=i+1; j:=j – 1 кц КІН | АЛГ MIN_MAX(ціл і, j, L, m, MIN, MAX, дійсн таб A[i:j]) АРГ і, j, A РЕЗ MIN, MAX, L, m ПОЧ ціл d MIN:=A[i]; l:=i MAX:=A[i]; m:=i для d від і до j пц якщо A[d]<=MIN то MIN:=A[d] L:=d все якщо A[d]>=MAX то MAX:=A[d] m:=d все кц КІН |
Сортування методом прямого вибору (модифіковане) мовою Паскаль має вигляд:
Program Sort;
const n=200;
type arr = array [1..n] of real;
Procedure Min_Max(M: arr; var Min, Max: word, left, right: word);
var i: word;
Begin
Min:=left;
Max:=left;
for i:=left to right do
Begin
if M[i]<M[Min]
then Min:=i;
if M[i]>M[Max]
then Max:=i;
end;
end;
var A: arr;
j: word;
e1: real;
L, R: word; Min, Max: word;
Begin
for j:=1 to n do
Begin
A[j]:=random*200 – random*100;
write (A[j]:8:2);
end;
L:=1; R:=n; writeln;
while L<R do
Begin
Min_Max (A, Min, Max, L, R);
e1:=A[L]; A[L]:=A[Min]; A[Min]:=e1;
if Max=L
then Max:=Min;
e1:=A[R]; A[R]:=A[max]; A[Max]:=e1;
L:=L+1; R:=R – 1;
end;
for j:=1 to n do
write (A[j]:8:2);
end.
Оскільки процедура Min_Max знаходить номери найменшого та найбільшого елементів, необхідно після переміни місцями мінімального та найлівішого елементів перевірити, чи не був цей найлівіший елемент максимальним. Якщо таке трапилось, очевидно, що максимальний елемент тепер зайняв місце мінімального, і тому необхідно змінити номер максимального елемента.
Поиск по сайту: