Рубрики

Сортировка по рекурсивному выбору

Алгоритм сортировки выбора поддерживает две части.

  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 <iostream>

using namespace std;

  
// Возвращаем минимальный индекс

int minIndex(int a[], int i, int j)

{

    if (i == j)

        return i;

  

    // Находим минимум оставшихся элементов

    int k = minIndex(a, i + 1, j);

  

    // Возвращаем минимум текущего и оставшегося.

    return (a[i] < a[k])? i : k;

}

  
// Рекурсивная сортировка выбора. n это размер [] и индекса
// индекс начального элемента.

void recurSelectionSort(int a[], int n, int index = 0)

{

    // Возврат, когда старт и размер совпадают

    if (index == n)

       return;

  

    // вызов функции минимального индекса для минимального индекса

    int k = minIndex(a, index, n-1);

  

    // Обмен, когда индекс и минимальный индекс не совпадают

    if (k != index)

       swap(a[k], a[index]);

  

    // Рекурсивный вызов функции сортировки выбора

    recurSelectionSort(a, n, index + 1);

}

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

int main()

{

    int arr[] = {3, 1, 5, 2, 7, 0};

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

  

    // Вызывающая функция

    recurSelectionSort(arr, n);

  

    // печать отсортированного массива

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

        cout << arr[i] << " ";

    cout << endl;

    return 0;

}

Джава

// Рекурсивная Java-программа для сортировки массива
// используя сортировку выбора

  

class Test

{

    // Возвращаем минимальный индекс

    static int minIndex(int a[], int i, int j)

    {

        if (i == j)

            return i;

       

        // Находим минимум оставшихся элементов

        int k = minIndex(a, i + 1, j);

       

        // Возвращаем минимум текущего и оставшегося.

        return (a[i] < a[k])? i : k;

    }

       

    // Рекурсивная сортировка выбора. n это размер [] и индекса

    // индекс начального элемента.

    static void recurSelectionSort(int a[], int n, int index)

    {

           

        // Возврат, когда старт и размер совпадают

        if (index == n)

           return;

       

        // вызов функции минимального индекса для минимального индекса

        int k = minIndex(a, index, n-1);

       

        // Обмен, когда индекс и минимальный индекс не совпадают

        if (k != index){

           // обмен

           int temp = a[k];

           a[k] = a[index];

           a[index] = temp;

        }

        // Рекурсивный вызов функции сортировки выбора

        recurSelectionSort(a, n, index + 1);

    }

       

      

    // Метод драйвера

    public static void main(String args[]) 

    {

        int arr[] = {3, 1, 5, 2, 7, 0};

       

        // Вызывающая функция

        recurSelectionSort(arr, arr.length, 0);

       

        // печать отсортированного массива

        for (int i = 0; i< arr.length; i++)

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

    }

python3

# Рекурсивный код Python3 для сортировки
# массив с использованием сортировки выбора

  
# Возврат минимального индекса

def minIndex( a , i , j ):

    if i == j:

        return i

          

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

    k = minIndex(a, i + 1, j)

      

    # Возвращает минимум тока

    # и оставшиеся.

    return (i if a[i] < a[k] else k)

      
# Рекурсивный выбор сортировки. н это
# размер [] и индекс это индекс
# стартовый элемент.

def recurSelectionSort(a, n, index = 0):

  

    # Возврат при запуске и

    # размер одинаков

    if index == n:

        return -1

          

    # вызов минимальной индексной функции

    # для минимального индекса

    k = minIndex(a, index, n-1)

      

    # Перестановка, когда индекс и минимум

    # Индекс не одинаков

    if k != index:

        a[k], a[index] = a[index], a[k]

          

    # Рекурсивно вызывающий выбор

    # функция сортировки

    recurSelectionSort(a, n, index + 1)

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

arr = [3, 1, 5, 2, 7, 0]

n = len(arr)

  
# Вызов функции
recurSelectionSort(arr, n)

  
# печать отсортированного массива

for i in arr:

    print(i, end = ' ')

      
# Этот код предоставлен "Sharad_Bhardwaj".

C #

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

using System;

  

class GFG

{

    // Возвращаем минимальный индекс

    static int minIndex(int []a, int i, int j)

    {

        if (i == j)

            return i;

      

        // Находим минимум оставшихся элементов

        int k = minIndex(a, i + 1, j);

      

        // Возвращаем минимум текущего и оставшегося.

        return (a[i] < a[k])? i : k;

    }

      

    // Рекурсивная сортировка выбора. п это размер

    // a [] и index это индекс начального элемента.

    static void recurSelectionSort(int []a, int n, 

                                   int index)

    {

          

        // Возврат, когда старт и размер совпадают

        if (index == n)

        return;

      

        // вызов минимальной индексной функции

        // для минимального индекса

        int k = minIndex(a, index, n - 1);

      

        // Меняем местами, когда индекс и минимальный индекс

        // не одинаковы

        if (k != index)

        {

            // обмен

            int temp = a[k];

            a[k] = a[index];

            a[index] = temp;

        }

          

        // Рекурсивный вызов функции сортировки выбора

        recurSelectionSort(a, n, index + 1);

    }

      

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

    public static void Main(String []args) 

    {

        int []arr = {3, 1, 5, 2, 7, 0};

      

        // Вызывающая функция

        recurSelectionSort(arr, arr.Length, 0);

      

        // печать отсортированного массива

        for (int i = 0; i< arr.Length; i++)

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

    }

  
// Этот код предоставлен Принчи Сингхом


Выход:

0 1 2 3 5 7 

Эта статья предоставлена Сахилом Раджпутом . Если вы как GeeksforGeeks и хотели бы внести свой вклад, вы также можете написать статью с помощью contribute.geeksforgeeks.org или по почте статьи contribute@geeksforgeeks.org. Смотрите свою статью, появляющуюся на главной странице GeeksforGeeks, и помогите другим вундеркиндам.

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

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

Сортировка по рекурсивному выбору

0.00 (0%) 0 votes