C program for recursive bubble sort

# Bubble sort is one of the simplest sorting algorithms used to sort data by comparing adjacent elements. All elements are compared in stages. The first stage puts the largest value at the end, the second stage puts the second largest element at the second to last position, and so on until the complete list is sorted.

Bubble sort algorithm

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

• int i, j ;

• Traverse from index i=0 to i
  • Traverse from index j=0 to array size - i - 1

  • If arr[i]>arr[j] swap arr[i] with arr[j]

• End

Recursive bubble sort

• If the array length is 1, return

• Traverse the array once, fixing the largest element at the end

  ​​p>

• The rest of the array recursively executes step 2 except the last element

Example

Input − Arr[] = { 5,7,2,3, 1,4}; length=6

Output − Sorted array: 1 2 3 4 5 7

Description −

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

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

Output− Sorted array: 1 2 2 3 3

Explanation -

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

The following program The method used in is as follows

In the recursive method of bubble sort, the basic situation is that the array length = 1. Otherwise use a single for loop to iterate through the array and swap elements accordingly.

< /p>

• Take input array Arr[] and length as the number of elements in it.

• Function recurbublSort(int arr[], int len) gets the array and its length, and uses bubble sort to recursively sort the array.

• Get the variable temp.

< li>If the array length is 1, void is returned.
• Otherwise use a single for loop to iterate over the array and, for each element arr[i]>arr[i 1], swap the elements.

• Set temp=arr[i], arr[i]=arr[i 1] and arr[i 1]=temp.

  < /p>

• Now reduce the length by 1 since the previous loop placed the largest element at the last position.

• Recursively call recurbublSort(arr,len).

• At the end of all calls, when len becomes 1, we exit the recursion and sort the array.
  < /li>
• Print the sorted array in main.

Example

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

Output

If we run the above code it will generate the following output

Sorted array: 20 21 31 34 43 66 78

The above is the detailed content of C program for recursive bubble sort. For more information, please follow other related articles on the PHP Chinese website!