Алгоритм сортировки выбором, реализованный на Python, Java и C / C++

2023-06-22 0 ∞

В этой статье мы рассмотрим алгоритм сортировки выбором. А также реализуем его на Python, Java, C++ и C.

Этапы реализации алгоритма
Демонстрация работы алгоритма
Сортировка выборки в Python
Сортировка выборки в Java
Сортировка выборки в C ++
Сортировка выбором в C
Временная сложность
Ссылки

Этапы реализации алгоритма

Устанавливаем i = 0.
Находим наименьший элемент несортированного подмассива [i..end]
Меняем его местами с элементом в позиции a[i].
Увеличиваем iи повторяем перечисленные выше шаги, пока i == n

В псевдокоде алгоритм можно представить следующим образом:

PROCEDURE SELECTION_SORT(arr):
    i = -1
    while i < size(arr):
        idx = find_min(arr[i+1..size(arr)])
        swap(i, idx)
        i++
    return arr

Демонстрация работы алгоритма

Рассмотрим приведенный ниже массив. В несортированном виде он выглядит следующим образом:

Сортировка выборки, начало

Во время первой итерации мы находим минимальный элемент массива (из {12, 7, 6, 16, 4}), который равен 4. Затем меняем местами arr[i] с 4.

Сортировка выборки, итерация 1

В следующей итерации мы найдем минимальный элемент подмассива {7, 6, 16, 12}, который равен 6. Поменяем местами 6 и 7.

Сортировка выборки, итерация 2

Теперь переходим к следующему элементу обновленного массива и снова выполняем те же действия.

Сортировка выборки, итерация 3

Во время предыдущей итерации изменений не было, поскольку 7 — это минимальный элемент в оставшемся подмассиве.

Сортировка выборки, итерация 4

Мы достигли конца массива. Весь массив отсортирован!

Сортировка выборки в Python

Приведенный ниже фрагмент кода демонстрирует работу алгоритма с использованием Python.

def find_min(arr, start, end):
    minimum = arr[start]
    min_idx = start
    for idx in range(start, end):
        if arr[idx] < minimum:
            minimum = arr[idx]
            min_idx = idx
    return min_idx
 
def selection_sort(arr):
    i = 0
    arr_size = len(arr)
    while i < arr_size:
        # Находим минимальный элемент в оставшемся несортированном подмасссиве
         min_idx = find_min(arr, i, arr_size)
        # Меняем местами с arr[i]
        arr[min_idx], arr[i] = arr[i], arr[min_idx]
        i += 1
    return arr
 
a = [12, 7, 6, 16, 4]
print(selection_sort(a))

Вывод

[4, 6, 7, 12, 16]

Сортировка выборки в Java

public class SelectionSort {
    int find_min(int arr[], int start, int end) {
        int min_idx = start;
        int minimum = arr[start];
        for (int i=start; i<end; i++) {
            if (arr[i] < minimum) {
                min_idx = i;
                minimum = arr[i];
            }
        }
        return min_idx;
    }
 
    void selection_sort(int arr[], int arr_len) {
        // Сортировка выбором массива
        int start = 0;
        int min_idx;
        while (start < arr_len) {
            min_idx = find_min(arr, start, arr_len);
            // Меняем местами arr[start] и arr[min_idx]
            int temp = arr[start];
            arr[start] = arr[min_idx];
            arr[min_idx] = temp;
            start++;
        }
    }
 
    public static void main(String[] args) {
        int arr[] = {12, 7, 6, 16, 4};
        SelectionSort sel_sort = new SelectionSort();
        sel_sort.selection_sort(arr, 5);
        System.out.println("Array after sorting:");
        for (int i=0; i<5; i++) {
            System.out.printf("%d ", arr[i]);
        }
        System.out.println();
    }
}

Сохраните приведенный выше код, как SelectionSort.java.

Вывод

Array after sorting:
4 6 7 12 16

Сортировка выборки в C ++

Ниже продемонстрирована реализация подобного алгоритма в C ++:

#include <iostream>
 
using namespace std;
 
 
int find_min(int arr[], int start, int end) {
    int min_idx = start;
    int minimum = arr[start];
    for (int i=start; i<end; i++) {
        if (arr[i] < minimum) {
            min_idx = i;
            minimum = arr[i];
        }
    }
    return min_idx;
}
 
 
void selection_sort(int arr[], int arr_len) {
    // Сортировка выбором массива
    int start = 0;
    int min_idx;
    while (start < arr_len) {
        min_idx = find_min(arr, start, arr_len);
        // Меняем местами arr[start] и arr[min_idx]
        int temp = arr[start];
        arr[start] = arr[min_idx];
        arr[min_idx] = temp;
        start++;
    }
}
 
 
int main() {
    int arr[] = {12, 7, 6, 16, 4};
    selection_sort(arr, 5);
    cout << "Array after sorting:n";
    for (int i=0; i<5; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

Вывод

Array after sorting:
4 6 7 12 16

Сортировка выбором в C

#include <stdio.h>
 
int find_min(int arr[], int start, int end) {
    int min_idx = start;
    int minimum = arr[start];
    for (int i=start; i<end; i++) {
        if (arr[i] < minimum) {
            min_idx = i;
            minimum = arr[i];
        }
    }
    return min_idx;
}
 
void selection_sort(int arr[], int arr_len) {
    // Сортировка выбором массива
    int start = 0;
    int min_idx;
    while (start < arr_len) {
        min_idx = find_min(arr, start, arr_len);
        // Меняем местами arr[start] и arr[min_idx]
        int temp = arr[start];
        arr[start] = arr[min_idx];
        arr[min_idx] = temp;
        start++;
    }
}
 
 
int main() {
    int arr[] = {12, 7, 6, 16, 4};
    selection_sort(arr, 5);
    printf("Array after sorting:n");
    for (int i=0; i<5; i++) {
        printf("%d ", arr[i]);
    }
    printf("n");
    return 0;
}

Вывод

Array after sorting:
4 6 7 12 16

Временная сложность

Алгоритм выполняет два цикла итераций, поэтому он имеет временную сложность O(n^2) . То есть, общее количество выполненных операций, если массив содержит n элементов, будет:

(n + (n-1) + (n-2) + (n-3) + … + 1) = n * (n + 1)/2 = O(n^2)

Это не очень хороший алгоритм сортировки. Но зато его легко реализовать и использовать для сортировки массивов с небольшим количеством элементов.

Ссылки

Статья в Wikipedia по сортировке выбором.