Informazioni sulla ricorsione (applicandola a Bubble Sort)

Question

Sto cercando di capire come utilizzare la ricorsione nei programmi. Capisco come funziona la ricorsione in esempi classici come "fattoriale", ma non sono sicuro di come applicarlo da solo ...

Sto iniziando con la conversione di un codice di ordinamento a bolle iterativo in un codice ricorsivo ... ho cercato in rete per lo stesso .... ma non sono in grado di trovare una soluzione convincente/spiegazione ..

esempio di codice iterativo per bubble sort IS:

arr [n] -> array con elementi (1..n) che devono essere ordinati

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

Sarebbe utile se qualcuno potesse dare un suggerimento su come procedere ...

Answer 1

Non sono sicuro che Bubblesort sia un buon algoritmo per praticare la ricorsione su. Sarebbe piuttosto brutto convertirlo in ricorsione perché è un ciclo annidato. Sembrerebbe qualcosa del genere:

function pass(i,j,n,arr) 
{ 
    if(arr[i]>arr(j)) 
    swap(arr[i],arr[j]); 

    if(j==n) 
    { 
    j=0; 
    i=i+1; 
    } 
    if(i==n+1) 
    return arr; 

    return pass(i,j+1,n,arr); 
} 

È lo stesso per il ciclo, solo più lungo da definire, utilizzando molta più memoria.

Si dovrebbe invece provare a implementare QuickSort. Ha bisogno di ricorsione, ed è molto più veloce nella maggior parte dei casi rispetto a BubbleSort. La maggior parte delle piattaforme lo ha già implementato, quindi non è necessario scriverlo da soli, ma è utile sapere come funziona e aiuta a comprendere la ricorsione.

Se si desidera si potrebbe anche provare a risolvere questo problema utilizzando la ricorsione:
Hai una tabella NxM di numeri e una coordinata di partenza (posizione). È una posizione da viaggiatore. Il viaggiatore può viaggiare verso una cella adiacente (destra, sinistra, su o giù) che ha un numero inferiore a quello in cui si trova. Devi scrivere un programma che calcoli il percorso più lungo che il viaggiatore può superare in base a questi vincoli. Usa random per generare l'array o generarlo manualmente.

Answer 2

La ricorsione è una tecnica di progettazione basata su prove induttive. Considera uno o più casi (semplici) di base per il tuo problema e uno o più modi per spostare il problema più vicino a un problema di base. Quindi, ad ogni passo dell'algoritmo, o riconosci il completamento (e gestisci in modo appropriato con un caso base), il problema diventa un po 'più vicino all'essere un caso base.

Bubble sort è solo un'applicazione dell'osservazione che un array ordinato ha tutte le coppie adiacenti di elementi in ordine. Definito in modo ricorsivo, funziona come:

1. caso base: c'è una matrice di dimensione 1 (o inferiore) da ordinare. È risolto, ovviamente.
2. Caso induttivo: bolla l'elemento più grande nella parte superiore della matrice. Ora c'è un array a un elemento più piccolo da ordinare, che fa.

È possibile scrivere quell'idea nel linguaggio di programmazione di propria scelta, e si ottiene una sorta di bolla. Oh, ma devi definire cosa significa "bolla l'elemento più grande". Bene, questa è un'altra opportunità per il design ricorsivo. Penso che tu abbia l'idea, però.

Gli ordini più veloci si basano principalmente su osservazioni su come ci si avvicina all'obiettivo in meno lavoro.L'ordinamento rapido, per esempio, si basa sul concetto che, se un array è ordinato, allora c'è un elemento P, e tutti gli elementi meno di P sono a sinistra di P, e tutti gli elementi più di P sono a destra di P. Se è possibile stabilire tale proprietà su un array e anche selezionare P, è possibile suddividere il problema approssimativamente a metà in ogni passaggio invece che semplicemente di uno.

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; 
} 

ritardo per 2 anni, ma forse sarà utile a qualcuno

Answer 4

perché ho trovato questa domanda come uno dei primi esempi, vorrei fornire un altro modo di fare la ricorsione, senza ulteriori argomenti:

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 

In questo modo, verrà ordinata l'intera sequenza per ogni chiamata.

Perché funziona? Poiché ogni serie di bolle viene eseguita, inseriremo almeno l'elemento più grande nell'indice più a destra.
Sappiamo che tutti gli elementi fino all'ultimo scambiatore sono in stato sconosciuto, tutti dopo l'ultimo scambio sono ordinati.

implementazioni in Java (array/lista di argomenti-modifica/no) potrebbe essere trovato qui: 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

Ecco la mia risposta. È essenzialmente la stessa della risposta di VladimFromUa (una variante ricorsiva di bubble sort), ma invece di eseguire un numero fisso di esecuzioni, le esecuzioni aggiuntive vengono eseguite solo se viene rilevato che l'array è stato riordinato nella corsa precedente.

altro paio di differenze sono di seguito:

1. parametro indicizzare il punto di partenza nella matrice è stato eliminato mediante compensazione l'indirizzo della matrice in chiamate ricorsive. 2.Il controllo "se (prima < ultimo & & ultimo> 0)" in Vlad o "if (--p_length == 1)" nel mio codice viene eseguito meglio prima della chiamata ricorsiva che comporterebbe la lunghezza dell'array essere 1, poiché è una chiamata in meno nello stack.

Ho aggiunto un codice per leggere l'input dalla riga di comando e stampare entrambi gli array non ordinati e ordinati, per comodità.

#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

Qui è un bubblesort ricorsivo 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); 
    } 
} 

Le prime 2 righe all'interno della funzione consentono all'utente di chiamare bubbleSortRecursive(array) e la funzione definirà la index1 e index2

Answer 8

Ecco un altro modo semplice per ordinare l'array recursively utilizzando Bubble-Sort.

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

ne dite di questo tipo di soluzione:

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

Ecco codice funzionale Scala. Tutto è immutabile. E questa è la ricorsione della coda.Così la pila dovrebbe andare bene

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

Ecco un altro javascript versione ricorsione con un po 'ES6/7 sintassi come parametri di argomento di default:

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);