Рубрики

Выбор сортировки

Алгоритм сортировки выбора сортирует массив путем многократного нахождения минимального элемента (с учетом возрастания) из несортированной части и положить его в начале. Алгоритм поддерживает два подмассива в данном массиве.

1) Подмассив, который уже отсортирован.
2) Оставшийся подмассив, который не отсортирован.

На каждой итерации сортировки выбора минимальный элемент (с учетом возрастающего порядка) из несортированного подмассива выбирается и перемещается в отсортированный подмассив.

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64 

Блок-схема выбора сортировки:

C ++

// C ++ программа для реализации селекционной сортировки
#include <bits/stdc++.h>

using namespace std;

  

void swap(int *xp, int *yp) 

    int temp = *xp; 

    *xp = *yp; 

    *yp = temp; 

  

void selectionSort(int arr[], int n) 

    int i, j, min_idx; 

  

    // Один за другим передвигаем границу несортированного подмассива

    for (i = 0; i < n-1; i++) 

    

        // Находим минимальный элемент в несортированном массиве

        min_idx = i; 

        for (j = i+1; j < n; j++) 

        if (arr[j] < arr[min_idx]) 

            min_idx = j; 

  

        // Меняем найденный минимальный элемент на первый элемент

        swap(&arr[min_idx], &arr[i]); 

    

  
/ * Функция для печати массива * /

void printArray(int arr[], int size) 

    int i; 

    for (i=0; i < size; i++) 

        cout << arr[i] << " "

    cout << endl; 

  
// Программа драйвера для проверки вышеуказанных функций

int main() 

    int arr[] = {64, 25, 12, 22, 11}; 

    int n = sizeof(arr)/sizeof(arr[0]); 

    selectionSort(arr, n); 

    cout << "Sorted array: \n"

    printArray(arr, n); 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

// C программа для реализации селекционной сортировки
#include <stdio.h>

  

void swap(int *xp, int *yp)

{

    int temp = *xp;

    *xp = *yp;

    *yp = temp;

}

  

void selectionSort(int arr[], int n)

{

    int i, j, min_idx;

  

    // Один за другим передвигаем границу несортированного подмассива

    for (i = 0; i < n-1; i++)

    {

        // Находим минимальный элемент в несортированном массиве

        min_idx = i;

        for (j = i+1; j < n; j++)

          if (arr[j] < arr[min_idx])

            min_idx = j;

  

        // Меняем найденный минимальный элемент на первый элемент

        swap(&arr[min_idx], &arr[i]);

    }

}

  
/ * Функция для печати массива * /

void printArray(int arr[], int size)

{

    int i;

    for (i=0; i < size; i++)

        printf("%d ", arr[i]);

    printf("\n");

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    int arr[] = {64, 25, 12, 22, 11};

    int n = sizeof(arr)/sizeof(arr[0]);

    selectionSort(arr, n);

    printf("Sorted array: \n");

    printArray(arr, n);

    return 0;

}

питон

# Python программа для реализации Selection
# Сортировать

import sys

A = [64, 25, 12, 22, 11]

  
# Обход всех элементов массива

for i in range(len(A)):

      

    # Найти минимальный элемент в оставшихся

    # несортированный массив

    min_idx = i

    for j in range(i+1, len(A)):

        if A[min_idx] > A[j]:

            min_idx = j

              

    # Поменять найденный минимальный элемент на

    # первый элемент

    A[i], A[min_idx] = A[min_idx], A[i]

  
# Код драйвера для проверки выше

print ("Sorted array")

for i in range(len(A)):

    print("%d" %A[i]), 

Джава

// Java-программа для реализации Selection Sort

class SelectionSort

{

    void sort(int arr[])

    {

        int n = arr.length;

  

        // Один за другим передвигаем границу несортированного подмассива

        for (int i = 0; i < n-1; i++)

        {

            // Находим минимальный элемент в несортированном массиве

            int min_idx = i;

            for (int j = i+1; j < n; j++)

                if (arr[j] < arr[min_idx])

                    min_idx = j;

  

            // Меняем найденный минимальный элемент на первый

            // элемент

            int temp = arr[min_idx];

            arr[min_idx] = arr[i];

            arr[i] = temp;

        }

    }

  

    // печатает массив

    void printArray(int arr[])

    {

        int n = arr.length;

        for (int i=0; i<n; ++i)

            System.out.print(arr[i]+" ");

        System.out.println();

    }

  

    // Код драйвера для проверки выше

    public static void main(String args[])

    {

        SelectionSort ob = new SelectionSort();

        int arr[] = {64,25,12,22,11};

        ob.sort(arr);

        System.out.println("Sorted array");

        ob.printArray(arr);

    }

}
/ * Этот код предоставлен Раджатом Мишрой * /

C #

// C # программа для реализации
// выбора сортировки

using System;

  

class GFG

    static void sort(int []arr)

    {

        int n = arr.Length;

  

        // Один за другим передвигаем границу несортированного подмассива

        for (int i = 0; i < n - 1; i++)

        {

            // Находим минимальный элемент в несортированном массиве

            int min_idx = i;

            for (int j = i + 1; j < n; j++)

                if (arr[j] < arr[min_idx])

                    min_idx = j;

  

            // Меняем найденный минимальный элемент на первый

            // элемент

            int temp = arr[min_idx];

            arr[min_idx] = arr[i];

            arr[i] = temp;

        }

    }

  

    // печатает массив

    static void printArray(int []arr)

    {

        int n = arr.Length;

        for (int i=0; i<n; ++i)

            Console.Write(arr[i]+" ");

        Console.WriteLine();

    }

  

    // Код драйвера

    public static void Main()

    {

        int []arr = {64,25,12,22,11};

        sort(arr);

        Console.WriteLine("Sorted array");

        printArray(arr);

    }

  
}
// Этот код предоставлен Sam007

PHP

<?php
// PHP программа для реализации
// выбора сортировки

function selection_sort(&$arr, $n

{

    for($i = 0; $i < $n ; $i++)

    {

        $low = $i;

        for($j = $i + 1; $j < $n ; $j++)

        {

            if ($arr[$j] < $arr[$low])

            {

                $low = $j;

            }

        }

          

        // меняем минимальное значение на $ ith узел

        if ($arr[$i] > $arr[$low])

        {

            $tmp = $arr[$i];

            $arr[$i] = $arr[$low];

            $arr[$low] = $tmp;

        }

    }

}

  
// Код драйвера

$arr = array(64, 25, 12, 22, 11);

$len = count($arr);

selection_sort($arr, $len);

echo "Sorted array : \n"

  

for ($i = 0; $i < $len; $i++) 

    echo $arr[$i] . " "

  
// Этот код добавлен
// Дипика Гупта.
?> 

Выход:

Sorted array: 
11 12 22 25 64

Сложность времени: O (n 2 ), поскольку есть два вложенных цикла.

Вспомогательное пространство: O (1)
Хорошая вещь в сортировке выбора состоит в том, что она никогда не делает больше, чем O (n) перестановок и может быть полезна, когда запись в память является дорогостоящей операцией.

Упражнение:
Сортировать массив строк, используя Выбор сортировки

Стабильность: реализация по умолчанию не является стабильной. Однако это можно сделать стабильным. Пожалуйста, смотрите стабильный выбор сортировки для деталей.

На месте: Да, это не требует дополнительного места.

Фотосъёмка:





Тест по выбору сортировки

Другие алгоритмы сортировки на GeeksforGeeks / GeeksQuiz:

  • Пузырьковая сортировка
  • Сортировка вставки
  • Сортировка слиянием
  • Куча сортировка
  • QuickSort
  • Radix Sort
  • Подсчет Сортировка
  • Ковш сортировать
  • ShellSort
  • Практика кодирования для сортировки.

    Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

    Рекомендуемые посты:

    Выбор сортировки

    0.00 (0%) 0 votes