TechCodeview

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

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

Робота Selection Sort

Нижче наведено кроки для пояснення роботи сортування Selection у Python.

Візьмемо невідсортований масив, щоб застосувати алгоритм сортування вибору.

громадянство Піта Девідсона

[30, 10, 12, 8, 15, 1]

Крок 1: Отримайте довжину масиву.

підключення java

довжина = len(масив) → 6

Крок 2: Спочатку ми встановлюємо перший елемент як мінімальний.

Крок - 3: Тепер порівняйте мінімум з другим елементом. Якщо другий елемент менший за перший, ми призначаємо його як мінімум.

Ми знову порівнюємо другий елемент із третім і, якщо третій елемент менший за другий, призначаємо його як мінімум. Цей процес триває, поки ми не знайдемо останній елемент.

кордон css

Крок - 4: Після кожної ітерації мінімальний елемент міняється перед невідсортованим масивом.

Крок - 5: Другий-третій кроки повторюються, поки ми не отримаємо відсортований масив.

Алгоритм сортування вибору

Алгоритм сортування вибору наступний.

Алгоритм

іменування для java

 selection_sort(array) repeat (0, length - 1) times set the first unsorted element as the minimum for each of the unsorted elements if element <currentminimum set element as new minimum swap with first unsorted position end selection_sort < pre> <h2>Selection Sort Program using Python</h2> <p>The following code snippet shows the selection sort algorithm implementation using Python.</p> <p> <strong>Code -</strong> </p> <pre> def selection_sort(array): length = len(array) for i in range(length-1): minIndex = i for j in range(i+1, length): if array[j] <array[minindex]: minindex="j" array[i], array[minindex]="array[minIndex]," array[i] return array print('the sorted is: ', selection_sort(array)) < pre> <p> <strong>Output:</strong> </p> <pre> The sorted array is: [3, 6, 9, 21, 33] </pre> <p> <strong>Explanation -</strong> </p> <p>Let&apos;s understand the above code -</p> <ul> <li>First, we define the <strong>selection_sort()</strong> function that takes array as an argument.</li> <li>In the function, we get the length of the array which used to determine the number of passes to be made comparing values.</li> <li>As we can see that, we use two loops - outer and inner loop. The outer loop uses to iterate through the values of the list. This loop will iterate to 0 to (length-1). So the first iteration will be perform (5-1) or 4 times. In each iteration, the value of the variable i is assigned to the variable</li> <li>The inner loop uses to compare the each value of right-side element to the other value on the leftmost element. So the second loop starts its iteration from i+1. It will only pick the value that is unsorted.</li> <li>Find the minimum element in the unsorted list and update the minIndex position.</li> <li>Place the value at the beginning of the array.</li> <li>Once the iteration is completed, the sorted array is returned.</li> <li>At last we create an unsorted array and pass to the <strong>selection_sort()</strong> It prints the sorted array.</li> </ul> <h2>Time Complexity of Selection Sort</h2> <p>Time complexity is an essential in term of how much time an algorithm take to sort it. In the selection sort, there are two loops. The outer loop runs for the n times (n is a total number of element).</p> <p>The inner loop is also executed for n times. It compares the rest of the value to outer loop value. So, there is n*n times of execution. Hence the time complexity of merge sort algorithm is O(n<sup>2</sup>).</p> <p>The time complexity can be categorized into three categories.</p> <hr></array[minindex]:></pre></currentminimum>

Пояснення -

Давайте розберемося з кодом вище -

• Спочатку ми визначимо selection_sort() функція, яка приймає масив як аргумент.
• У функції ми отримуємо довжину масиву, який використовувався для визначення кількості проходів, які необхідно зробити для порівняння значень.
• Як ми бачимо, ми використовуємо два цикли - зовнішній і внутрішній. Зовнішній цикл використовується для перебору значень списку. Цей цикл повторюватиметься від 0 до (довжина-1). Отже, перша ітерація буде виконана (5-1) або 4 рази. У кожній ітерації значення змінної i присвоюється змінній
• Внутрішній цикл використовується для порівняння кожного значення правого елемента з іншим значенням крайнього лівого елемента. Отже, другий цикл починає свою ітерацію з i+1. Він вибере лише невідсортоване значення.
• Знайдіть мінімальний елемент у несортованому списку та оновіть позицію minIndex.
• Розмістіть значення на початку масиву.
• Після завершення ітерації повертається відсортований масив.
• Нарешті ми створюємо несортований масив і переходимо до selection_sort() Він друкує відсортований масив.

Часова складність сортування вибору

Часова складність має важливе значення з точки зору того, скільки часу потрібно алгоритму для сортування. У сортуванні виділення є два цикли. Зовнішній цикл виконується n разів (n – загальна кількість елементів).

Внутрішній цикл також виконується n разів. Він порівнює решту значення зі значенням зовнішнього циклу. Отже, є n*n разів виконання. Отже, часова складність алгоритму сортування злиттям дорівнює O(n²).

Часову складність можна розділити на три категорії.