Рекурсивная пузырьковая сортировка
Фон :
Пузырьковая сортировка - это простейший алгоритм сортировки, который работает, многократно меняя местами соседние элементы, если они находятся в неправильном порядке.
Пример:
Первый проход:
( 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, вернуть.
- Сделайте один проход обычной пузырьковой сортировки. Этот проход исправляет последний элемент текущего подмассива.
- Повторяется для всех элементов, кроме последнего из текущего подмассива.
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.