 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Сортування методом вибору
Сортування передбачає два завдання:
1)пошук у таблиці порядкового номера елемента з найменшим значенням (вибір);
2)перестановка знайденого елемента з черговим (першим, другим і т.д.) елементом таблиці.
Покажемо роботу алгоритму на конкретному прикладі. Хай дана таблиця з 5 елементів (рис. 3). Її необхідно впорядкувати в порядку зростання.
Знаходимо порядковий номер мінімального елемента всієї таблиці (якщо мінімальних елементів кілька, то перший з них). У нашому випадку мінімальний елемент 2, він стоїть на 4-му місці в таблиці. Міняємо його з першим за допомогою робочої комірки R. Після першого проходу найменший елемент таблиці посів перше місце в таблиці. Потім повторюються ті самі дії, але вже без першого елемента таблиці і т.д.
| Основний алгоритм: | Допоміжний алгоритм: |
| АЛГ ІЗ1(цілN, L, дійсн таб A[1:N]) АРГ N, A РЕЗ А ПОЧ ціл і, L, M, дійсн R M:=N – 1 для і від 1 до М пц IMIN(i, N, A, L) R:=A[i]; A[i]:=A[L]; A[L]:=R кц КІН | АЛГIMIN (ціл M, N, L, дійсн таб A[M:N]) АРГ M, N, A РЕЗ L ПОЧ ціл і, дійснMIN MIN:=A[M] для і від М до N пц якщо A[i]<MIN то MIN:=A[i]; L:=i все кц КІН |
Мовою Паскаль алгоритм прямого вибору має такий вигляд:
Program Sort_Selection;
const n=100;
type arr = array [1..n] of real;
Function Min (M: arr); R: word): word;
var i: word; k:word;
Begin
k:=1;
for i:=2 to R do
if M[k]>M[i]
then k:=i;
Min:=k;
end;
var A: arr; L, j: word; еl: real;
Begin
{ заповнення масиву та виведення його на екран }
for j:=1 to n do
Begin
A[j]:=random*200 – random*100;
write (A[j]:8:2);
end;
writeln:
for j:=n downto 2 do
Begin
L:=min (A,j);
e1:=A[j];
A[L]:=A[j];
A[j]:=e1;
end;
for j:=1 to n do
write (A[j]:8:2);
end.
Функція Min знаходить номер найменшого елемента в масиві серед перших R елементів (з 1-го до R-го). Оскільки нам не потрібне значення найменшого елемента, ми запам’ятовуємо тільки його номер, а саме значення знаходимо за номером.
В основній програмі спочатку заповнюється масив дійсними числами з діапазону від 100 до 100 (random генерує числа від 0 до 1, а random*200 – у діапазоні від 0 до 200). А потім у підмасивах, що після кожного виконання циклу зменшуються на один елемент, шукають найменший елемент, який потім міняється місцями з останнім елементом підмасиву.
В кінці програми відсортований масив виводиться на екран для контролю.
Поиск по сайту: