Сортуваня

(впорядкування) масивів

Під сортуванням розуміють процес розміщення об'єктів масиву у заданому порядку(зростання чи спадання) з метою полегшення подальшого пошуку елементів множини для обробки та використання.

Розрізняють декілька видів сортування.

  • сортування бульбашкою(обмінне сортування ),

  • сортування вибором,

  • сортування вставками,

  • швидке сортування,

  • сортування Шелла,

  • пірамідальне сортування,

  • сортування обчисленням адреси,

  • сортування порозрядним групуванням тощо.

Ці методи відрізняються швидкістю отримання результату, складністю і універсальністю. Перші два методи прості і зрозумілі, проте для переважної кількості масивів неефективні.

Сортування "бульбашкою"

Такий метод сортування масивів полягає в тому, що ми знаходимо найбільший елемент і переміщаємо його в кінець масиву. Це один з найпростіших для розуміння методів.

Особливості застосування сортування бульбашкою.

  • алгоритм сортування як за зростанням, так і за спаданням відрізняються тільки знаками порівняння a[j]>a[j+1] для зростання і a[j]<a[j+1] для спадання

  • одинакові елементи масиву не впливають на правильність результату

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

Сортування вставкою

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



Особливості застосування сортування.

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



Алгоритм сортування "бульбашкою" за зростанням

  1. Порівняти два сусідні елементи масиву.

  2. Якщо наступний елемент менший за попередній, то міняємо їх місцями.

  3. Процедуру повторюємо до тих пір, доки всі елементи не стануть в порядку зростання.

  4. Кількість повторів даної процедури буде n-1, оскільки останній елемент не буде з чим порівнювати.

Завдання 1. Задано масив з 10 натуральних чисел від 1 до 10 записаних випадковим чином. Впорядкувати масив за допомогою сортування бульбашкою.


from random import randrange

n=int(input("Введіть кількість елементів масиву"))

a=[randrange(1,10) for i in range(n)]

print(a)

for i in range(n):

for j in range(n-i-1):

if a[j]>a[j+1]:

x=a[j]

a[j]=a[j+1]

a[j+1]=x

print(a)

Реалізувати обмін значень сусідніх елементів можна в один рядок, використавши множинне присвоєння. Тоді код буде виглядати так:

a[i],a[j]=a[j],a[i]

Приклад 2.