Одновимірний масив — це пронумерована послідовність значень одного типу, що мають спільне ім'я. Спільне ім'я t послідовності значень температури означає, що ці дані належать до одного масиву, а розрізнити їх можна за номером (індексом). У мові Python для зберігання масивів даних використовуються списки.
Маси́в — впорядкований набір фіксованої кількості однотипних елементів, що зберігаються в послідовно розташованих комірках оперативної пам'яті, мають порядковий номер і спільне ім'я, що надає користувач.
Масиви бувають одновимірними (у вигляді послідовності чисел), двовимірними (у вигляді таблиць чисел розміром m x n) і багатовимірними (3-,4-вимірні і т. д.
CОРТУВАННЯ ВСТАВКАМИ
Алгоритми сортування вставками відрізняються від наведених вище алгоритмів тим, що шукаються не «елементи для місць», а «місця для елементів». З сімейства цих алгоритмів розглянемо алгоритм прямих вставок. У масиві виділяємо дві частини: відсортовану та невідсортовану. Спочатку відсортована частина містить тільки перший елемент (сам по собі впорядкований). Далі щоразу беремо перше значення з невідсортованої частини та «перетягуємо» його до відсортованої так, щоб вона не втратила впорядкованості. Для цього пересуваємо поточне значення ліворуч доти, доки воно не займе своє правильне місце у відсортованій частині масиву, тобто коли значення ліворуч і праворуч поточного стоятимуть «правильно» відносно нього. Отже, елемент «вставляється» у відсортовану частину масиву (звідки й назва методу).
procedure insertSort(var A:alnt; n:word);
var i, k : word;
begin
for k: =2 to n do begin
і : =k ;
while (A[i]l) do begin
swap(A[i], A[i-1]); dec(i);
end;
end ;
end;
Оскільки зсув елемента на одну позицію ліворуч «коштує» три команди присвоювання, рекомендуємо запам'ятати еталонний елемент (той, для якого шукається місце у відсортованій частині) у додатковій змінній. Тоді зсув можна виконати одним присвоюванням, а
запам'ятований елемент потім одним присвоюванням поставити на звільнене місце.
procedure insertSort(var A:alnt; n:word);
var i, k : word;
etalon :integer;
begin
for k:=2 to n do begin
etalon:=A[k]; i:=k;
while (i>l) and (A[i-1]>etalon) do begin
A[i]:=A[i-l]; dec(i);
end;
A[i]:=etalon;
end;
end ;
Складність цього методу також має оцінку У ньому, як і в сортуванні «бульбашкою»,виконується багато обмінів сусідніх елементів. У 1959 році Д.Шелл запропонував удосконалення алгоритму прямих вставок. Його ідея - порівнювати елементи, що знаходяться на певній відстані один від одного і покроково зменшувати цю відстань.
Розглянемо приклад. Нехай масив має такий вигляд
Алгоритм впорядкування елементів масиву
Під час опрацювання сукупностей даних часто виникає потреба впорядкувати ці дані за деякою ознакою. Числові дані можна відсортувати за
величиною (наприклад, створити рейтинг навчальних досягнень), рядкові
дані — в алфавітному порядку (упорядкувати список учнів).
Сортування елементів масиву — це впорядкування їх за деякою ознакою.Розглянемо два найпростіші методи сортування масиву.
Нехай потрібно впорядкувати масив X: аrray[1..10] оf Real; за неспаданням: X[1] ≤ X[2] ≤ ... ≤ X[10].
Сортування вибором максимального елемента
Цей метод заснований на тому, що під час кожного проходу циклу
переглядається частина масиву завдовжки К елементів. Наприклад, для
масиву X[1..10] під час першого проходу К = 10.Алгоритм сортування за зростанням (рис. 36.1):• відшукати максимальний з елементів X[1]..X[10];• максимальний елемент поміняти місцями з X[10];• відшукати максимальний елемент із частини масиву X[1]..X[9];• максимальний елемент із цієї частини поміняти місцями з X[9];<…>• максимальний елемент із частини масиву X[1]..X[2] поміняти місцями
з X[2].
фрагмент програмного модуля виглядатиме саме так:
For K := 10 downto 2 do
begin{ пошук М — номера Мах(X[1..K] }
M := 1; Max := X[1];For i := 2 to K do
If X[i] > Max Then beginMax := X[i]; M := i;end;{ перестановка X[K] і X[M] з використанням допоміжної комірки С }
C := X[M]; X[M] := X[K]; X[K] := C;end;
Розглянемо алгоритм сортування, який вважається найпростішим. Нехай А[1],А[2],...,А[n] — елементи масиву, які треба відсортувати за неспаданням. Порівняємо А [ 1 ] з А [ 2 ] : якщо А[1] >А[2] , поміняємо їх значення місцями. Потім порівняємо А [ 2 ] з А [ 3 ] і, якщо треба, поміняємо місцями їх значення. Тоді А [ 3 ] буде мати найбільше значення серед А [ 1 ] , А [2] , А[3] . Продовжимо ці порівняння та обміни до кінця — А[n] одержить найбільше значення. Наприклад, послідовність значень <3, 4, 2, 1> перетвориться на <3, 2, 1, 4>. Якщо значення елементів уподібнити розмірам бульбашок, то порівняння й обміни будуть схожі на те, як найбільша бульбашка спливає нагору, відтісняючи інші. Тому цей метод називається бульбашковим сортуванням.
В аналогічний спосіб перемістимо друге за величиною значення в елемент А[n-1] , перетворивши, наприклад, <3, 2, 1, 4> у <2, 1, 3, 4>. Потім третє за величиною значення перемістимо в А[n-2] тощо. На останньому кроці порівняємо тільки А[1] з А [2 ] і, якщо треба, поміняємо місцями їх значення.
Уточнимо бульбашкове сортування процедурою bubbleSort { bubble — бульбашка).
procedure bubbleSort(var A:alnt; n:word);
var i, k : word;
begin
for k : =n downto 2 do
for i:=l to k-1 do
if A[i]>A[i+1] then swap(A[i] , A[i+1])
end;
Очевидно, що найбільша кількість елементарних дій прямо пропорційна загальній кількості порівнянь, яких у найгіршому випадку .
Звідси складність сортування n - елементного масиву описаним способом має оцінку .
Сортування вибором максимального елемента
Нехай потрібно впорядкувати масив X: аrray[1..10] оf Real; за неспаданням:
X[1] ≤ X[2] ≤ ... ≤ X[10].
Алгоритм сортування:
• Відшукати максимальний елемент з послідовності X[1]..X[10].
• Максимальний елемент із цієї послідовності поміняти місцями з X[10].
• Відшукати максимальний елемент із послідовності X[1]..X[9].
• Максимальний елемент із цієї послідовності поміняти місцями з X[9].
<…>
• Максимальний елемент із послідовності X[1]..X[2] поміняти місцями з X[2].
Навіщо потрібне сортування?
З відсортованими даними працювати легше, ніж з довільно розташованими:
коли елементи відсортовані, їх простіше знайти;
на відсортованих даних легше визначити, чи є пропущені елементи;
простіше упевнитися, що всі елементи були перевірені;
легше знайти спільні елементи двох множин.
Сортування є потужним засобом прискорення роботи практично будь-якого алгоритму, в якому потрібно часто звертатися до певних елементів даних.
Розглянемо два найпростіші методи сортування масиву.
Сортування обміном (метод бульбашки)
Метод бульбашки ґрунтується на порівнянні та перестановці сусідніх чисел.
Алгоритм сортування:
• Послідовно порівнювати пари сусідніх елементів X[і] і X[і+1] (і:1..N–1), і, якщо X[і] > X[і+1], то поміняти їх місцями, логічній змінній Prap надати значення True. У результаті першого перегляду послідовності на N—му місці буде найбільший з усіх елементів, тобто він, як бульбашка, «спливе» вгору.
• Переглянути елементи від 1 до N–2; на (N–1)му місці з’явиться найбільший серед (N–1) перших елементів і т. д.
23.png
Програмний код, що реалізує описаний алгоритм:
Repeat
Prap := False;
For i := 1 to 9 do
If X[i] > X[i+1] Then begin
C := X[i];
X[i] := X[i+1];
X[i+1] := C;
Prap := True end
Until Prap = False;
Алгоритми сортування - це процес впорядкування елементів у масиві або списку відповідно до певного критерію, такого як зростання або спадання.
Деякі з найпопулярніших алгоритмів сортування масивів включають:
Сортування бульбашкою (Bubble Sort)
Сортування вибором (Selection Sort)
Сортування вставками (Insertion Sort)
Сортування злиттям (Merge Sort)
Швидке сортування (Quick Sort)
Сортування купою (Heap Sort)
Кожен алгоритм має свої переваги та недоліки, але загалом швидкість та ефективність алгоритму залежить від кількості елементів, що сортуються, та структури масиву чи списку.
Сортування елементів масиву — це розстановка елементів масиву в заданому порядку (за зростанням, за зменшенням, за останньою цифрою, в лексикографічному порядку тощо).
Сортування вибором максимального елемента
Нехай потрібно впорядкувати масив X: аrray[1..10] оf Real; за неспаданням:
X[1] ≤ X[2] ≤ ... ≤ X[10].
Алгоритм сортування:
• Відшукати максимальний елемент з послідовності X[1]..X[10].
• Максимальний елемент із цієї послідовності поміняти місцями з X[10].
• Відшукати максимальний елемент із послідовності X[1]..X[9].
• Максимальний елемент із цієї послідовності поміняти місцями з X[9].
<…>
• Максимальний елемент із послідовності X[1]..X[2] поміняти місцями з X[2].
Програмний код, що реалізує описаний алгоритм:
For K := 10 downto 2 do
begin { пошук М — номера Мах(X[1..K])}
M := 1; Max := X[1];
For i := 2 to K do
If [Xi] > Max Then begin
Max := X[i]; M := i; end;
{ перестановка X[K] і X[M] }
C := X[M]; X[M] := X[K]; X[K] := C;
end;
Сортування масиву — це процес впорядкування всіх елементів масиву в певному порядку. Дуже часто це буває корисним. Наприклад, у вашій поштовій скриньці електронні листи відображаються в залежності від часу отримання; нові листи вважаються більш релевантними, ніж ті, які ви отримали півгодини, годину, дві або день назад; коли ви переходите до списку своїх контактів, імена зазвичай знаходяться в алфавітному порядку, тому що так легше щось знайти. Всі ці випадки включають в себе сортування даних перед їх фактичним виведенням
Сортування елементів масиву — це розстановка елементів масиву в заданому порядку (за зростанням, за зменшенням, за останньою цифрою, в лексикографічному порядку тощо).
Навіщо потрібне сортування?
З відсортованими даними працювати легше, ніж з довільно розташованими:
коли елементи відсортовані, їх простіше знайти;
на відсортованих даних легше визначити, чи є пропущені елементи;
простіше упевнитися, що всі елементи були перевірені;
легше знайти спільні елементи двох множин.
Сортування є потужним засобом прискорення роботи практично будь-якого алгоритму, в якому потрібно часто звертатися до певних елементів даних.
Розглянемо два найпростіші методи сортування масиву.
Сортування елементів масиву — це розстановка елементів масиву в заданому порядку (за зростанням, за зменшенням, за останньою цифрою, в лексикографічному порядку тощо).
Навіщо потрібне сортування?
З відсортованими даними працювати легше, ніж з довільно розташованими:
коли елементи відсортовані, їх простіше знайти;
на відсортованих даних легше визначити, чи є пропущені елементи;
простіше упевнитися, що всі елементи були перевірені;
легше знайти спільні елементи двох множин.
Сортування є потужним засобом прискорення роботи практично будь-якого алгоритму, в якому потрібно часто звертатися до певних елементів даних.
Розглянемо два найпростіші методи сортування масиву.
Сортування вибором максимального елемента
Нехай потрібно впорядкувати масив X: аrray[1..10] оf Real; за неспаданням:
X[1] ≤ X[2] ≤ ... ≤ X[10].
Алгоритм сортування:
• Відшукати максимальний елемент з послідовності X[1]..X[10].
• Максимальний елемент із цієї послідовності поміняти місцями з X[10].
• Відшукати максимальний елемент із послідовності X[1]..X[9].
• Максимальний елемент із цієї послідовності поміняти місцями з X[9].
<…>
• Максимальний елемент із послідовності X[1]..X[2] поміняти місцями з X[2].
Як бачимо, об'єктами впорядкування можуть бути найрізноманітніші елементи. Головне, щоб їх можна було порівнювати, тобто існував би закон, який дозволяє довільні два елементи правильно розташувати один відносно іншого («А має стояти після В або перед ним»).
Величину, за якою сортуються елементи, називають ключем сортування. Це може бути число, послідовність символів або складніша величина, наприклад, дата, яка містить рік, місяць та день.
Як відомо, дані в комп'ютері подано в числовому вигляді, тому програмісти під сортуванням традиційно розуміють упорядкування за зростанням або спаданням числових величин.
Методи впорядкування масивів
ПОНЯТТЯ СОРТУВАННЯ
Загальне значення слова «сортування» — це розподіл елементів на групи за деякою ознакою, наприклад, розподіл яблук по сортах за їх якістю, листів за поштовими індексами, банок із фарбами за кольором тощо. Проте у програмуванні під сортуванням розуміють упорядкування елементів (за деякою характеристикою), наприклад, вишикування учнів за зростом на уроці фізкультури, розташування слів у словнику в алфавітному порядку, упорядкування точок площини за зростанням координати х тощо.
Алгоритми впорядкування масивів
