Алгоритм сортировки выбором, реализованный на 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 по сортировке выбором.

Пожалуйста, опубликуйте ваши комментарии по текущей теме статьи. За комментарии, лайки, подписки, отклики, дизлайки огромное вам спасибо!

Данная публикация является переводом статьи «Selection Sort Algorithm Implemented in Python, Java, and C/C++» , подготовленная редакцией проекта.

Меню