Рекурсивная пузырьковая сортировка

Опубликовано: 20 Января, 2022

Фон :
Пузырьковая сортировка - это простейший алгоритм сортировки, который работает, многократно меняя местами соседние элементы, если они находятся в неправильном порядке.
Пример:
Первый проход:
( 5 1 4 2 8) -> ( 1 5 4 2 8). Здесь алгоритм сравнивает первые два элемента и меняет местами, поскольку 5> 1.
(1 5 4 2 8) -> (1 4 5 2 8), поменять местами, поскольку 5> 4
(1 4 5 2 8) -> (1 4 2 5 8), поменять местами, поскольку 5> 2
(1 4 2 5 8 ) -> (1 4 2 5 8 ). Теперь, поскольку эти элементы уже упорядочены (8> 5), алгоритм не меняет их местами.
Второй проход:
( 1 4 2 5 8) -> ( 1 4 2 5 8)
(1 4 2 5 8) -> (1 2 4 5 8), поменять местами, поскольку 4> 2
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Теперь массив уже отсортирован, но наш алгоритм не знает, завершился ли он. Алгоритм нужен один весь проход без свопа знать сортируется.
Третий проход:
( 1 2 4 5 8) -> ( 1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8) -> (1 2 4 5 8)
(1 2 4 5 8 ) -> (1 2 4 5 8 )
Ниже приводится итеративный алгоритм пузырьковой сортировки:

 // Итеративная пузырьковая сортировка
bubbleSort (arr [], n)
{
  для (я = 0; я <п-1; я ++)      

     // Последние i элементов уже на месте   
     для (j = 0; j <ni-1; j ++)
     {
         если (arr [j]> arr [j + 1])
             своп (arr [j], arr [j + 1]);
     }
}

Дополнительные сведения см. В разделе «Пузырьковая сортировка».
Как это реализовать рекурсивно?
Рекурсивная пузырьковая сортировка не имеет преимуществ в производительности / реализации, но может быть хорошим вопросом для проверки понимания пузырьковой сортировки и рекурсии.
Если мы внимательно рассмотрим алгоритм пузырьковой сортировки, мы можем заметить, что на первом проходе мы перемещаем самый большой элемент в конец (предполагая сортировку в порядке возрастания). Во втором проходе мы перемещаем второй по величине элемент на вторую последнюю позицию и так далее.
Идея рекурсии.

  1. Базовый случай: если размер массива равен 1, вернуть.
  2. Сделайте один проход обычной пузырьковой сортировки. Этот проход исправляет последний элемент текущего подмассива.
  3. Повторяется для всех элементов, кроме последнего из текущего подмассива.

Below is implementation of above idea.

C++

// C/C++ program for recursive implementation
// of Bubble sort
#include <bits/stdc++.h>
using namespace std;
 
// A function to implement bubble sort
void bubbleSort(int arr[], int n)
{
    // Base case
    if (n == 1)
        return;
 
    // One pass of bubble sort. After
    // this pass, the largest element
    // is moved (or bubbled) to end.
    for (int i=0; i<n-1; i++)
        if (arr[i] > arr[i+1])
            swap(arr[i], arr[i+1]);
 
    // Largest element is fixed,
    // recur for remaining array
    bubbleSort(arr, n-1);
}
 
/* Function to print an array */
void printArray(int arr[], int n)
{
    for (int i=0; i < n; i++)
        printf("%d ", arr[i]);
    printf(" ");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr)/sizeof(arr[0]);
    bubbleSort(arr, n);
    printf("Sorted array : ");
    printArray(arr, n);
    return 0;
}

Java

// Java program for recursive implementation
// of Bubble sort
 
import java.util.Arrays;
 
public class GFG
{
    // A function to implement bubble sort
    static void bubbleSort(int arr[], int n)
    {
        // Base case
        if (n == 1)
            return;
      
        // One pass of bubble sort. After
        // this pass, the largest element
        // is moved (or bubbled) to end.
        for (int i=0; i<n-1; i++)
            if (arr[i] > arr[i+1])
            {
                // swap arr[i], arr[i+1]
                int temp = arr[i];
                arr[i] = arr[i+1];
                arr[i+1] = temp;
            }
      
        // Largest element is fixed,
        // recur for remaining array
        bubbleSort(arr, n-1);
    }
     
    // Driver Method
    public static void main(String[] args)
    {
        int arr[] = {64, 34, 25, 12, 22, 11, 90};
      
        bubbleSort(arr, arr.length);
         
        System.out.println("Sorted array : ");
        System.out.println(Arrays.toString(arr));
    }
}

Python3

# Python Program for implementation of
# Recursive Bubble sort
class bubbleSort:
    """
     bubbleSort:
          function:
              bubbleSortRecursive : recursive
                  function to sort array
              __str__ : format print of array
              __init__ : constructor
                  function in python
          variables:
              self.array = contains array
              self.length = length of array
    """
 
    def __init__(self, array):
        self.array = array
        self.length = len(array)
 
    def __str__(self):
        return " ".join([str(x)
                        for x in self.array])
 
    def bubbleSortRecursive(self, n=None):
        if n is None:
            n = self.length
 
        # Base case
        if n == 1:
            return
 
        # One pass of bubble sort. After
        # this pass, the largest element
        # is moved (or bubbled) to end.
        for i in range(n - 1):
            if self.array[i] > self.array[i + 1]:
                self.array[i], self.array[i +
                1] = self.array[i + 1], self.array[i]
 
        # Largest element is fixed,
        #  recur for remaining array
        self.bubbleSortRecursive(n - 1)
 
# Driver Code
def main():
    array = [64, 34, 25, 12, 22, 11, 90]
     
    # Creating object for class
    sort = bubbleSort(array)
     
    # Sorting array
    sort.bubbleSortRecursive()
    print("Sorted array : ", sort)
 
 
if __name__ == "__main__":
    main()
 
# Code contributed by Mohit Gupta_OMG,
# improved by itsvinayak

C#

// C# program for recursive
// implementation of Bubble sort
using System;
 
class GFG
{
 
// A function to implement
// bubble sort
static void bubbleSort(int []arr,  
                       int n)
{
    // Base case
    if (n == 1)
        return;
 
    // One pass of bubble
    // sort. After this pass,
    // the largest element
    // is moved (or bubbled)
    // to end.
    for (int i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
        {
            // swap arr[i], arr[i+1]
            int temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
 
    // Largest element is fixed,
    // recur for remaining array
    bubbleSort(arr, n - 1);
}
 
// Driver code
static void Main()
{
    int []arr = {64, 34, 25,
                 12, 22, 11, 90};
 
    bubbleSort(arr, arr.Length);
     
    Console.WriteLine("Sorted array : ");
    for(int i = 0; i < arr.Length; i++)
    Console.Write(arr[i] + " ");
}
}
 
// This code is contributed
// by Sam007

Javascript

<script>
// javascript program for recursive
// implementation of Bubble sort
 
// A function to implement
// bubble sort
  function bubbleSort(arr, n)
{
 
    // Base case
    if (n == 1)
        return;
  
    // One pass of bubble
    // sort. After this pass,
    // the largest element
    // is moved (or bubbled)
    // to end.
     
    for (var i = 0; i < n - 1; i++)
        if (arr[i] > arr[i + 1])
        {
         
            // swap arr[i], arr[i+1]
            var temp = arr[i];
            arr[i] = arr[i + 1];
            arr[i + 1] = temp;
        }
  
    // Largest element is fixed,
    // recur for remaining array
    bubbleSort(arr, n - 1);
}
  
// Driver code
 
    var arr = [64, 34, 25, 12, 22, 11, 90 ]
    bubbleSort(arr, arr.length);
    document.write("Sorted array : " + "<br>");
    for(var i = 0; i < arr.length; i++) {
    document.write(arr[i] + " ");
    }
     
    // This code is contributed by bunnyram19.
    </script>

Выход :

 Отсортированный массив:
11 12 22 25 34 64 90

Эта статья предоставлена Супротик Дей . Если вам нравится GeeksforGeeks, и вы хотели бы внести свой вклад, вы также можете написать статью, используя write.geeksforgeeks.org, или отправить свою статью по электронной почте: deposit@geeksforgeeks.org. Посмотрите, как ваша статья появляется на главной странице GeeksforGeeks, и помогите другим гикам.
Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по теме, обсужденной выше.

Вниманию читателя! Не прекращайте учиться сейчас. Освойте все важные концепции DSA с помощью самостоятельного курса DSA по приемлемой для студентов цене и будьте готовы к работе в отрасли. Чтобы завершить подготовку от изучения языка к DS Algo и многому другому, см. Полный курс подготовки к собеседованию .

Если вы хотите посещать живые занятия с отраслевыми экспертами, пожалуйста, обращайтесь к Geeks Classes Live и Geeks Classes Live USA.

РЕКОМЕНДУЕМЫЕ СТАТЬИ