C-Programm zur rekursiven Blasensortierung

Bubble Sort ist einer der einfachsten Sortieralgorithmen, der zum Sortieren von Daten durch Vergleich benachbarter Elemente verwendet wird. Alle Elemente werden stufenweise verglichen. In der ersten Stufe wird der größte Wert am Ende platziert, in der zweiten Stufe wird das zweitgrößte Element an der vorletzten Position platziert und so weiter, bis die vollständige Liste sortiert ist.

Blasensortierungsalgorithmus

• int arr[5]= { 5,4,2,1,3 };

• int i, j ;

• Traverse vom Index i=0 zum i

  • Durchlauf vom Index j=0 zur Array-Größe - i - 1

  • If arr[i]>arr[j] Tausche arr[i] mit arr[j]

• Ende

Rekursive Blasensortierung

• Wenn die Array-Länge 1 ist, geben Sie zurück

• Durchlaufen Sie das Array einmal und legen Sie das maximale Element am Ende fest​​p>

• Der Rest der Schritte wird bis auf den letzten rekursiv ausgeführt Elementarray

Beispiel

Eingabe − Arr[] = {5,7,2,3, 1,4}; Länge=6

Ausgabe − Sortiertes Array: 1 2 3 4 5 7

Beschreibung −

First Pass
5 7 2 3 1 4 → swap → 5 2 7 3 1 4
5 2 7 3 1 4 → swap → 5 2 3 7 1 4
5 2 3 7 1 4 → swap → 5 2 3 1 7 4
5 2 3 1 7 4 → swap → 5 2 3 1 4 7
Second Pass
5 2 3 1 4 7 → swap → 2 5 3 1 4 7
2 5 3 1 4 7 → swap → 2 3 5 1 4 7
2 3 5 1 4 7 → swap → 2 3 1 5 4 7
2 3 1 5 4 7 → swap → 2 3 1 4 5 7
Third Pass
2 3 1 4 5 7 → swap → 2 1 3 4 5 7
2 1 3 4 5 7 no swap
Fourth Pass
2 1 3 4 5 7 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 no swap in further iterations

Eingabe− Arr[] = { 1, 2, 3, 3, 2 };

Ausgabe− Sortiertes Array: 1 2 2 3 3

Beschreibung -

r reee

Die im folgenden Programm verwendete Methode lautet wie folgt:

Bei der rekursiven Methode der Blasensortierung ist die Grundsituation Array-Länge = 1. Andernfalls verwenden Sie eine einzelne for-Schleife, um das Array zu durchlaufen und die Elemente entsprechend auszutauschen.

• Nehmen Sie das Eingabearray Arr[] und die Länge als Anzahl der darin enthaltenen Elemente.

• Die Funktion recurbublSort(int arr[], int len) ruft das Array und seine Länge ab und verwendet Bubble Sort, um das Array rekursiv zu sortieren.

• Erhalten Sie die variable Temperatur.

Wenn die Array-Länge 1 ist, wird void zurückgegeben.

• Andernfalls verwenden Sie eine einzelne for-Schleife, um das Array zu durchlaufen und für jedes Element arr[i]>arr[i+1] die Elemente auszutauschen.

• Setze temp=arr[i], arr[i]=arr[i+1] und arr[i+1]=temp.

• Verringern Sie nun die Länge um 1, da in der vorherigen Schleife das größte Element an der letzten Position platziert wurde.

• Rekursiv recurbublSort(arr,len) aufrufen.

• Am Ende aller Aufrufe, wenn len 1 wird, beenden wir die Rekursion und sortieren das Array.

• Drucken Sie das sortierte Array in main.

Beispiel

First Pass
1 2 3 3 2 → swap → 1 2 3 2 3
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 no swap in further iterations
Second Pass
1 2 2 3 3 no swap in further iterations

Ausgabe

Wenn wir den obigen Code ausführen, wird die folgende Ausgabe generiert

#include <stdio.h>
void recurbublSort(int arr[], int len){
   int temp;

   if (len == 1){
      return;
   }
   for (int i=0; i<len-1; i++){
      if (arr[i] > arr[i+1]){
         temp=arr[i];
         arr[i]=arr[i+1];
         arr[i+1]=temp;
      }
   }
   len=len-1;
   recurbublSort(arr, len);
}
int main(){
   int Arr[] = {21, 34, 20, 31, 78, 43, 66};
   int length = sizeof(Arr)/sizeof(Arr[0]);

   recurbublSort(Arr, length);

   printf("Sorted array : ");
   for(int i=0;i<length;i++){
      printf("%d ",Arr[i]);
   }

   return 0;
}

Das obige ist der detaillierte Inhalt vonC-Programm zur rekursiven Blasensortierung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!