Сортування вибором.

Сортування масивів методом вибору (виділення) здійснюються таким чином.

Знаходимо (вибираємо) у масиві елемент із мінімальним значенням на інтервалі від 1- го елемента до n-го (останнього) елемента й міняємо його місцями з першим елементом. На другому кроці знаходимо елемент із мінімальним значенням на інтервалі від 2-го до n-го елемента й міняємо його місцями із другим елементом.

І так далі для всіх елементів до n-1-го.

Розглянемо схему алгоритму прямого вибору.

Малюнок 5.4

5.4 Сортування обміном ("бульбашкове" сортування).

Сортування масивів методом вибору (виділення) здійснюються таким чином:

Зліва направо по черзі рівняються два сусідніх елементи, і якщо їх взаємне розташування не відповідає заданій умові впорядкованості, то вони міняються місцями. Далі беруться два наступних сусідніх елементи й так далі до кінця масиву.

Після одного такого проходу на останній n-ій позиції масиву буде стояти максимальний елемент ("сплила" перша "бульбашка"). Оскільки максимальний елемент уже знаходиться на своїй останній позиції, то другий прохід обмінів виконується до n-1-ого елемента. І так далі. Усього потрібно n-1 прохід.

Розглянемо схему алгоритму сортування методом прямого обміну за неубуванням.

Малюнок 5.5

5.5 Порівняння прямих методів сортування

Теоретичні й практичні дослідження алгоритмів прямих методів сортування показали, що як за числом порівнянь, так і за числом присвоєнь вони мають квадратичну залежність від довжини масиву n. Винятком є метод вибору, що має число присвоєнь порядку n*ln(n). Це властивість алгоритму вибору корисно застосовувати у задачах сортування в складних структурах даних, коли на одне порівняння виконується більше число присвоювань. У таких задачах метод вибору успішно конкурує з найшвидшими поліпшеними методами сортування.

Якщо порівняти розглянуті прямі методи між собою, то в середньому методи вставки й вибору виявляються приблизно еквівалентними й у кілька разів (залежно від довжини масиву) кращими, ніж метод обміну ("бульбашки").

5.6 Двовимірні масиви

Двовимірний масив являє собою прямокутну матрицю, що складається з m - рядків й n - стовпців. Для визначення елементів у двовимірному масиві треба вказувати два індекси, номер рядка й номер стовпця. Елементи двовимірного масиву позначаються a[n, m], де a - ім'я масиву, n - номер рядка, m - номер стовпця.

У розділі описів масив треба описати так:

Перший спосіб

type <назва типу> = array[1..m, 1..n] of <тип>;

var <ім'я змінної> : < назва типу >;

Другий спосіб

var <ім'я змінної> :array[1..m, 1..n] of <тип>;

Наприклад:

¨ Type mas : array[1..10,1..15] of real; {описуємо новий тип даних: двовимірний масив з 10 рядків й 15 стовпців дійсних чисел }

Var x:mas;

( Var x : array [1..10,1..15] of real;

Приклад.Сформувати одномірний масив З, кожен елемент якого дорівнює добутку елементів стовпців матриці Х(10x10), помноженому на максимальний елемент цього стовпця.

uses wincrt;
var x: array[1..10, 1..10] of real;
i, j, m, n: integer;
p, xmax: real;
c: array[1..10] of real;
begin
{Уведення матриці}
writeln ('_ВВІД МАТРИЦІ_');
write('кількість рядків m=');
readln(m);
write('кількість стовпців n=');
readln(n);
for i:=1 to m do
for j:=1 to n do read(x[i,j]);
{Цикл за i задає номера рядків масиву. Після цього починає працювати цикл за j -
за кількістю елементів у рядку, тобто за кількістю стовпців. Після
уведення
елементів одного рядка (елементи вводяться через пробіл, наприкінці
рядка
натиснути ENTER), цикл за i повторюється, вводяться елементи
наступного рядка й
так далі. }
for j:=1 to n do
begin
p:=1;
xmax:=x[1,j];
for i:=1 to m do
begin
if xmax<x[i,j] then xmax :=x[i,j];{Знаходимо максимальний

елемент
стовпця}
p:=p*x[i,j]; {Обчислюємо добуток елементів стовпця}
end;
c[j]:= p*xmax;
end;
{Друк отриманого масиву }
writeln('масив C:');
for i:=1 to n do write(' ', c[i]:2:1);
end.

Приклад.Транспонування матриці.

uses wincrt;
var i, j, m, n: integer;
x: real;
Matr: array [1..10,1..10] of real;
begin
writeln ('___ВВЕДЕННЯ МАТРИЦІ___');
write ('кількість рядків m='); readln(m);
write ('кількість стовпців n='); readln(n);
for i:=1 to m do read(Matr[i,j]);
{Транспонування матриці}
for i:=1 to m do
for j:=i+1 to n do
begin
x:=Matr [i,j];
Matr[i,j]:=Matr [j,i];
Matr[j,i]:=x;
end;
{Вивід транспонованої матриці на екран Для
виводу елементів масиву на екран організовані два цикли, але після
завершення
внутрішнього циклу за j включений порожній оператор writeln, щоб
наступні
елементи виводилися з початку нового рядка.}
for i:=1 to m do begin
for j:=1 to n do write (' ',Matr[i,j]:2:1);
writeln;
end;
end.

Читайте також:

<== попередня сторінка	\|	наступна сторінка ==>
Сортування вставкою.	\|	Множини

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.