Rekursion verstehen (Anwendung auf Bubble Sort)

Question

Ich versuche herauszufinden, wie Rekursion in Programmen zu verwenden ist. Ich verstehe, wie Rekursion in klassischen Beispielen wie "faktoriell" funktioniert, bin aber nicht sicher, wie ich es selbst anwenden soll ...

Ich beginne mit der Umwandlung eines iterativen Blasensortiercodes in einen rekursiven Code ... ich habe über das Netz für das gleiche gesucht .... aber ich bin nicht in der Lage eine überzeugende Lösung/Erklärung zu finden ..

Beispiel iterativer Code für Blasensortierung heißt:

arr [n] -> Array mit Elemente (1..n), die zu sortieren sind

 
for(i:1 to n) 
    for(j:1 to n-1) 
     if(arr[j+1]>arr[j]) 
     swap(arr[j+1],arr[j]); 

Wäre hilfreich, wenn jemand einen Hinweis geben könnte, wie man vorgeht ...

Answer 1

Ich bin mir nicht sicher, ob Bubblesort ein guter Algorithmus ist, um Rekursion zu üben. Es wäre ziemlich hässlich, es in Rekursion zu konvertieren, weil es ein verschachtelter Zyklus ist. Es würde in etwa so aussehen:

Es ist das gleiche für die Schleife, nur länger zu definieren, mit viel mehr Speicher.

Sie sollten stattdessen versuchen, QuickSort zu implementieren. Es braucht Rekursion, und es ist in den meisten Fällen viel schneller als BubbleSort. Die meisten Plattformen haben es bereits implementiert, so dass Sie es nicht selbst schreiben müssen, aber es ist gut zu wissen, wie es funktioniert, und es hilft Rekursion zu verstehen.

Wenn Sie möchten, können Sie auch versuchen, dieses Problem mit Rekursion zu lösen:
Sie haben eine Tabelle NxM von Zahlen und eine Startkoordinate (Position). Es ist eine^Reisende^Position. Der Reisende kann zu einer benachbarten Zelle (rechts, links, oben oder unten) reisen, die eine kleinere Nummer hat als die, auf der er sich befindet. Sie müssen ein Programm schreiben, das den längsten Pfad berechnet, den der Reisende unter diesen Einschränkungen passieren kann. Verwenden Sie random, um das Array zu generieren, oder generieren Sie es manuell.

Answer 2

Rekursion ist eine Konstruktionstechnik, die auf induktiven Beweisen basiert. Betrachtet einen oder mehrere einfache Basisfälle für Ihr Problem und eine oder mehrere Möglichkeiten, das Problem näher an ein Basisfallproblem zu bringen. Dann erkennen Sie bei jedem Schritt des Algorithmus entweder die Vervollständigung (und gehen Sie angemessen mit einem Basisfall um) und machen das Problem dann etwas näher zum Basisfall.

Blasensortieren ist nur eine Anwendung der Beobachtung, dass ein sortiertes Array alle benachbarten Paare von Elementen in der Reihenfolge hat. Rekursiv definiert, funktioniert es wie folgt:

1. Base Case: Es gibt ein Array der Größe 1 (oder weniger) zu sortieren. Es ist natürlich sortiert.
2. Induktive Fall: Blase das größte Element an die Spitze des Arrays. Jetzt gibt es ein kleineres Array mit einem Element, das sortiert werden muss.

Sie können diese Idee in der Programmiersprache Ihrer Wahl schreiben, und Sie erhalten Blasensortierung. Oh, aber Sie müssen definieren, was es bedeutet, "das größte Element zu sprudeln". Nun, das ist eine weitere Möglichkeit für rekursives Design. Ich denke, Sie verstehen die Idee.

Schnellere Sortierungen basieren meist auf Beobachtungen darüber, wie Sie mit weniger Arbeit dem Ziel näher kommen.Die schnelle Sortierung zum Beispiel beruht auf der Vorstellung, dass, wenn ein Array sortiert ist, dann ein Element P vorhanden ist und alle Elemente, die kleiner als P sind, links von P liegen und alle Elemente, die größer als P sind, rechts von P liegen. Wenn Sie diese Eigenschaft für ein Array ermitteln können und auch P auswählen, können Sie das Problem bei jedem Schritt grob um die Hälfte reduzieren und nicht einfach um eins.

Answer 3

public void sort(int[] arr, int first, int last){ 

    if(first < last && last > 0){ 
     if(arr[first] > arr[first+1]){ 
      int temp = arr[first]; 
      arr[first] = arr[first+1]; 
      arr[first+1] = temp; 
     } 
     sort(arr, first+1, last); 
     sort(arr, first, last-1); 
    } 
    else 
     return; 
} 

Spät für 2 Jahre, aber vielleicht wird es sinnvoll, jemand

Answer 4

Weil ich diese Frage als eines der ersten Beispiele gefunden, ich möchte eine andere Art und Weise, um die Rekursion zu tun, ohne zusätzliche Argumente:

function bubblesort (input: some integer array): 
    if input is empty: 
    return input 
    else: 
    do one bubble sort run for input 
    subarray = bubblesort(unsorted part of input) 
    return subarray append sorted part of input 

Auf diese Weise werden wir das gesamte Array stückweise für jeden Aufruf sortieren.

Warum funktioniert es? Da jede Blasensortierung läuft, werden wir mindestens das größte Element auf den Index ganz rechts setzen.
Wir wissen, dass alle Elemente bis zum letzten Austausch im unbekannten Zustand sind, alle nach dem letzten Austausch sortiert sind.

Implementierungen in Java (Array/list Argument modifizierende/nicht) dort gefunden werden konnte: https://codereview.stackexchange.com/questions/24006/recursive-bubble-sort-in-java/24133#24133

Answer 5

#include <stdio.h> 
#include <stdlib.h> 

void sort(int *arr, int first, int last){ 

    if(first < last && last > 0){ 
     if(arr[first] > arr[first+1]){ 
      int temp = arr[first]; 
      arr[first] = arr[first+1]; 
      arr[first+1] = temp; 
     } 
     sort(arr, first+1, last); 
     sort(arr, first, last-1); 
    } 
    else 
     return; 
} 
int main(void) { 

    int data [] = { 3, 5 , 6, 2, 1, 10, 4}; 
    int len = sizeof(data)/sizeof(int); 
    int i = 0; 
    sort(data,0,len-1); 
    for(i=0;i<len;i++) 
     printf("%d ",data[i]); 

    return EXIT_SUCCESS; 
} 

Answer 6

Hier ist meine Antwort. Es entspricht im Wesentlichen der Antwort von VladimFromUa (einer rekursiven Variante der Blasensortierung), aber statt einer festgelegten Anzahl von Läufen werden zusätzliche Läufe nur ausgeführt, wenn festgestellt wird, dass das Array beim vorherigen Lauf neu geordnet wurde.

Noch ein paar Unterschiede sind unten:

1.Die Parameter, um den Startpunkt in der Array-Indizierung wurde durch Versetzen der Adresse des Arrays in rekursiven Aufrufe weggefallen. 2.Die Prüfung "if (erste < letzte & letzte> 0)" in Vlad oder "if (--p_length == 1)" in meinem Code ist vor dem rekursiven Aufruf besser durchgeführt, die Array-Länge wäre 1, da es einen Anruf weniger auf dem Stapel ist.

Ich habe einen Code hinzugefügt, um die Eingabe von der Befehlszeile zu lesen und die unsortierten und sortierten Arrays zu drucken.

#include <stdio.h> 
#include <stdlib.h> 
#include <assert.h> 

typedef enum { FALSE, TRUE } boolean_t; 

void 
swap_int(int *a, int *b) { 

    int temp = *a; 

    *a = *b; 
    *b = temp; 
} 

boolean_t 
sort_array(int p_array[], int p_length) { 

    boolean_t result; 

    if (p_array[0] > p_array[1]) { 
     swap_int(p_array, p_array + 1); 
     result = TRUE; 
    } else { 
     result = FALSE; 
    } 

    if (--p_length == 1) { 
     return result; 
    } 

    result |= sort_array(p_array + 1, p_length); 

    if (result) { 
     sort_array(p_array, p_length); 
    } 

    return result; 
} 

void 
print_array_int(int p_array[], int p_length) { 

    int n; 

    for (n = 0; n < p_length - 1; n++) { 
     printf("%d, ", p_array[n]); 
    } 

    printf("%d\n", p_array[n]); 
} 

int 
main(int argc, char **argv) { 

    int *array; 
    int array_length = argc - 1; 
    int n; 

    array = malloc(array_length * sizeof(*array)); 

    for (n = 0; n < array_length; n++) { 
     sscanf(argv[n + 1], "%d", array + n); 
    } 

    printf("\nUnsorted array:\n"); 
    print_array_int(array, array_length); 
    sort_array(array, array_length); 
    printf("\nSorted array:\n"); 
    print_array_int(array, array_length); 

return 0; 
} 

Answer 7

Hier ist eine rekursive Bubblesort in JavaScript:

function bubbleSortRecursive(array, index1, index2) { 
    //define index1 and index2 if user doesn't pass them in 
    index1 = typeof index1 == "undefined" ? 0 : index1; 
    index2 = typeof index2 == "undefined" ? array.length : index2; 

    if (index1 > index2) { 
     return array; 
    } else if (index1 == index2 - 1) { 
     return bubbleSortRecursive(array, 0, index2 - 1); 
    } else if (array[index1] > array[index1 + 1]) { 
     //bubble the larger value towards the end of the array 
     var temp = array[index1]; 
     array[index1] = array[index1 + 1]; 
     array[index1+1] = temp; 
     return bubbleSortRecursive(array, index1 + 1, index2); 
    } else { 
     return bubbleSortRecursive(array, index1 + 1, index2); 
    } 
} 

Die ersten 2 Zeilen in der Funktion dem Benutzer erlauben bubbleSortRecursive(array) anrufen und die Funktion wird die index1 und index2

Answer 8

Hier definieren ist eine weitere einfache Möglichkeit, Ihr Array recursively mit Bubble-Sort zu sortieren.

static void RecursiveBubbleSort(int[] Arr, int l) 
{// 'Arr' is the array where 'l' is the length of the array 

    if (l == 0) return; 

    for (int j = 0; j < l - 1; j++) 
     if (Arr[j] > Arr[j + 1]) SWAP(Arr[j], Arr[j + 1]); 

    RecursiveBubbleSort(Arr, l - 1); 
} 

Answer 9

Bubble sort: recursive and efficient 

public static void bubbleSort(int[] ele, int counter, int index) { 
      int temp=-1; 
      if (counter < ele.length) { 
       if (index < ele.length - 1) { 
        if (ele[index] > ele[index+1]) { 
         ele[index] += ele[index+1]; 
         ele[index+1] = ele[index] - ele[index+1]; 
         ele[index] = ele[index] - ele[index+1]; 
         temp = ele[index]; 
        } 
        bubbleSort(ele, counter, index+1); 
        //temp = sortedIndex; 
        return; 
       } 
       if(counter == ele.length-1 && temp==-1){ 
        return; 
       } 
       bubbleSort(ele, counter+1, 0); 
      } 

     } 

Answer 10

Wie über diese Art der Lösung:

package recursive.bubble; 

public class RecursiveBubble { 

    public static boolean sort(int []arr){ 
     if(!bubbleSorted(arr, 0)){ 
      return sort(arr); 
     } 
     return true; 
    } 
    public static boolean bubbleSorted(int []a,int index){  
     if(a.length<2){ 
      return true; 
     } 
     if(index==a.length-2){ 
      if(a[index+1]<a[index]){ 
       swap(a,index,index+1); 
       return false; 
      } 
      return true; 
     } 
     boolean isSorted=false; 
     if(a[index]<=a[index+1]){ 
      isSorted=true; 
     }else{ 
      swap(a,index,index+1); 
     } 
     return isSorted && bubbleSorted(a, index+1); 
    } 
    private static void swap(int[] a, int index, int i) { 
     int tmp=a[index]; 
     a[index]=a[i]; 
     a[i]=tmp; 
    } 
    public static void main(String[] args) { 
     int []a={4,5,6,2,2,3,9,1,8}; 
     if(sort(a)) 
     for (int i = 0; i < a.length; i++) { 
      System.out.println(a[i]); 
     } 
    } 
} 

Answer 11

def bubble_sort(l): 
    for i, num in enumerate(l): 
     try: 
      if l[i+1] < num: 
       l[i] = l[i+1] 
       l[i+1] = num 
       bubble_sort(l) 
     except IndexError: 
      pass 
    return l 

Answer 12

#include <stdio.h> 
void bubbleSort(int *,int ,int ,int); 
void swap(int *, int *); 
void printArray(int *,int); 

int main() 
{ 
    int n,c; 

    printf("Enter number of elements\n"); 
    scanf("%d", &n); 

    int array[n]; 

    printf("Enter %d integers\n", n); 

    for (c = 0; c < n; c++) 
     scanf("%d", &array[c]); 

    printf("Before Sorting:\n"); 
    printArray(array,n); 

    bubbleSort(array,0,0,n); 

    printf("After Soring:\n"); 
    printArray(array,n); 

} 

void bubbleSort(int *array,int i,int j,int n) 
{ 
    if(j==n-i-1) 
    { 
     i = i+1; 
     j = 0; 
    } 
    if(i==n-1) 
     return; 

    if(array[j]>array[j+1]) 
     swap(&array[j],&array[j+1]); 

    j++; 
    bubbleSort(array,i,j,n); 
} 

void swap(int *p,int *q) 
{ 
    int t = *q ; 
    *q = *p; 
    *p = t; 
} 

void printArray(int *array,int n) 
{ 
    int c=0; 
    for (c = 0; c < n; c++) 
     printf("%d ", array[c]); 
    printf("\n"); 
} 

Answer 13

Hier scala Funktionscode ist. Alles ist unveränderlich. Und das ist Tail-Rekursion.So sollte der Stapel

def sort(initial: List[Int], result: List[Int] = Nil): List[Int] = { 

    def getBiggest(list: List[Int], rest: List[Int] = Nil): (List[Int], Int) = list match { 
    case x1 :: x2 :: tail => 
     if(x1 > x2) 
     getBiggest(x1 :: tail, x2 :: rest) 
     else 
     getBiggest(x2 :: tail, x1 :: rest) 
    case x :: Nil => (rest, x) 
    } 

    initial match { 
    case _ :: _ :: _ => 
     getBiggest(initial) match { 
     case (rest, biggest) => sort(rest, biggest :: result) 
     } 
    case x :: Nil => x :: result 
    case Nil => Nil 
    } 
} 

Answer 14

Hier ist eine andere Javascript-Rekursion Version mit einigen es6/7 Syntax wie Standardargument Parameter in Ordnung sein:

let unsorted = [4, 2, 4, 99, 1, 1, 5]; 
 

 
const bubSort = (arr, end = 0) => { 
 
    // base case 
 
    if (end >= arr.length) { 
 
    return arr; 
 
    } 
 

 
    // bubble sort, goes through once 
 
    for (let i = 0; i < arr.length - 1; i++) { 
 
    if (arr[i] > arr[i + 1]) { 
 
     // swap! 
 
     let hold = arr[i + 1]; 
 
     arr[i + 1] = arr[i]; 
 
     arr[i] = hold; 
 
    } 
 
    } 
 

 
    // down the rabbit hole; updating `end` is a small optimization 
 
    return bubSort(arr, ++end); 
 
} 
 

 
const sorted = bubSort(unsorted); 
 
console.log(sorted);