загрузка...
загрузка...
На головну

Алгоритми впорядкування елементів в масивах

  1. V. наземне відпрацювання ЕЛЕМЕНТІВ СТРИБКА
  2. А.1. Призначення і типи збірних елементів і конструкцій
  3. А.3. Транспорт і монтаж збірних елементів
  4. Автоматичний урівноважений міст. Призначення основних елементів схеми. Принцип роботи приладу
  5. Алгоритми діагностики найбільш поширених моногенних ННСТ.
  6. Алгоритми і виконавці
  7. Алгоритми накопичення суми і твори
 < 28.7. Пошук мінімальних або максимальних ...  28.9. Множення матриці на вектор і матриці на ... >

Алгоритми впорядкування елементів одновимірних масивів за зростанням або спаданням їх величини (сортування) є одними з найважливіших в програмуванні. Існує досить багато різних алгоритмів сортування; тут розглядається лише два з них.

Перший алгоритм досить простий по суті; він будується на основі викладеного в 28.7. Розглянемо його на прикладі упорядкування за зростанням n елементів одновимірного масиву X. Він заснований на наступних діях.

Спочатку знаходиться мінімальний елемент масиву в ряду від першого до останнього, n-ного. цей елемент Xm c індексом im обмінюється місцями з першим. Потім знаходиться новий мінімальний елемент в ряду від другого до останнього. Він обмінюється місцями з другим. І так далі. Цикл пошуку та обміну місцями повторюється до передостаннього елемента, тобто n-1 раз. Блок схема цього алгоритму представлена ??на рис. 28.15.

Якщо знайдений мінімальний елемент збігається з початковим елементом пошуку, то його не потрібно обмінювати місцями. Але для деякого спрощення в блок-схемі виключена перевірка цього випадку і збережений обмін елемента із собою. Обмін елементів місцями виробляється через допоміжну змінну tmp.

Проаналізуємо роботу цього алгоритму на прикладі масиву з чотирьох елементів:

При першому виконанні основного циклу буде знайдений мінімальний четвертий елемент і обміняний місцями з першим:

При другому проходженні буде знайдений мінімальний третій елемент і обміняний місцями з другим:

І нарешті, при останньому проходженні циклу буде знайдений мінімальний четвертий елемент, обміняний місцями з третім і все елементи виявляться впорядковані.

Більш ефективним є інший алгоритм сортування, званий бульбашковим. Його блок-схема приведена на рис. 28.16. Він є більш компактним, ніж попередній. Проаналізуємо його роботу на такому ж прикладі. Для наочності зобразимо вертикальне розташування осередків масиву при зростанні номера зверху вниз.

Початковий стан елементів масиву наступне:

При першому виконання тіла зовнішнього циклу внутрішній цикл буде виконуватися тричі. При цьому спочатку обміняються місцями третій і четвертий елементи, потім - другий і третій і, нарешті, перший і другий. В результаті цих обмінів елемент масиву, рівний 1, як бульбашка повітря, спливає вгору:

При другому виконання тіла зовнішнього циклу внутрішній цикл буде виконуватися два рази. Спочатку обміняються місцями третій і четвертий елементи, а потім - другий і третій.

При останньому виконанні тіла зовнішнього циклу внутрішній цикл виконується один раз і в ньому переставляються місцями третій і четвертий елементи;

Сортування завершена.

Алгоритми впорядкування матриць виявляються більш складними. Наведемо як при-мера алгоритм перестановки рядків матриці, в результаті якої середні значення елементів по рядках зростають від першого рядка до останньої. Він представлений на рис. 28.17.

матриця A має m рядків і n стовпців. Спочатку в циклі за індексом рядки i розраховуються середні значення по рядках; їх значення записуються в масив S. Потім проводиться сортування елементів масиву S по зростанню першим з описаних вище методом. При перестановці елементів масиву S одночасно переставляються пов'язані з ними рядки матриці. Після закінчення сортування масиву S всі рядки матриці A виявляються впорядковані за потрібне чином.

Другий алгоритм, представлений на рис. 28.18 впорядковує елементи матриці A з m рядків і n стовпців так, щоб вони зростали як по рядках, так і по стовпцях. Для цього використовується допоміжний одновимірний масив X. Спочатку елементи матриці A по рядках переписуються в одновимірний масив X, Потім упорядковуються там бульбашковим методом, а потім переписуються назад в тій же послідовності по рядках. При переписуванні даних з двовимірного масиву в одновимірний і назад використані два різних способу встановлення відповідності між індексами двовимірного і одновимірного масивів. У першому випадку індекс одновимірного масиву формується як лічильник, який спочатку обнуляється, а в тілі циклу перезапису збільшується на одиницю. У другому випадку використовується відповідність між індексами i (Рядки) і j (Стовпчик) матриці і індексом k одновимірного масиву:

k = j + (i-1) * n

Обидва ці способи еквівалентні. На блок-схемі фрагмент упорядкування одновимірного масиву не деталізований, тому що він збігається з наведеним на рис. 28.16.

Для виконання цього завдання може бути запропонований більш оптимальний алгоритм, який не використовує одновимірний масив і представляє собою двовимірний варіант алгоритму на рис. 2.15. Однак наведений варіант з одновимірним масивом корисний тим, що показує прийоми перезапису елементів з двовимірного масиву в одновимірний і назад, що іноді потрібно при розробці алгоритмів.

 < 28.7. Пошук мінімальних або максимальних ...  28.9. Множення матриці на вектор і матриці на ... >


Попередня   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37   Наступна

Вступ | Вступ | Вступ | Вступ | Обчислення кінцевих і нескінченних сум і творів | Рішення рівнянь ітераційними методами | Розрахунок таблиць функціональних залежностей | Підрахунок числа позитивних, негативних і нульових елементів масивів | Розрахунок модуля вектора і норми матриці | Розрахунок середнього і дисперсії елементів в масивах |

загрузка...
© um.co.ua - учбові матеріали та реферати