재귀적 버블 정렬을 위한 C 프로그램

버블 정렬은 인접 요소를 비교하여 데이터를 정렬하는 데 사용되는 가장 간단한 정렬 알고리즘 중 하나입니다. 모든 요소는 단계적으로 비교됩니다. 첫 번째 단계에서는 가장 큰 값을 끝에 배치하고 두 번째 단계에서는 두 번째로 큰 요소를 두 번째 마지막 위치에 배치하는 식으로 전체 목록이 정렬될 때까지 계속됩니다.

버블 정렬 알고리즘

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

• 정수 i, j;

• 인덱스 i=0에서 i<배열 크기

  로 트래버스

  • 인덱스 j=0에서 배열 크기 - i - 1까지 순회

  • arr[i]>arr[j] arr[i]를 arr[j]로 바꾸면

• 끝

재귀 버블 정렬

• 배열 길이가 1이면 반환

• 배열을 한 번 탐색하고 끝에서 가장 큰 요소를 수정합니다.

• 마지막 요소를 제외한 나머지 배열에 대해 2단계를 재귀적으로 수행

예시

입력 - Arr[] ={ 5,7,2,3,1,4 }; 길이=6

출력 − 정렬된 배열:1 2 3 4 5 7

설명 -

퍼스트 패스5 7 2 3 1 4 → 스왑 → 5 2 7 3 1 45 2 7 3 1 4 → 스왑 → 5 2 3 7 1 45 2 3 7 1 4 → 스왑 → 5 2 3 1 7 45 2 3 1 7 4 → 교환 → 5 2 3 1 4 7Second Pass5 2 3 1 4 7 → 교환 → 2 5 3 1 4 72 5 3 1 4 7 → 교환 → 2 3 5 1 4 72 3 5 1 4 7 → 교환 → 2 3 1 5 4 72 3 1 5 4 7 → 스왑 → 2 3 1 4 5 7Third Pass2 3 1 4 5 7 → 스왑 → 2 1 3 4 5 72 1 3 4 5 7 스왑 없음Fourth Pass2 1 3 4 5 7 → 스왑 →1 2 3 4 5 71 2 3 4 5 7 추가 반복에서 스왑 없음

입력 - Arr[] ={ 1, 2, 3, 3, 2 };

출력 − 정렬된 배열:1 2 2 3 3

설명 -

첫 번째 패스1 2 3 3 2 → 스왑 → 1 2 3 2 31 2 3 2 3 → 스왑 → 1 2 2 3 31 2 2 3 3 추가 반복에서 스왑 없음두 번째 패스1 2 2 3 3 추가 반복에서 스왑 없음 
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
 

 버블 정렬의 재귀적 접근 방식에서 기본 케이스는 배열 길이 =1입니다. 그렇지 않으면 단일 for 루프를 사용하여 배열을 순회하고 그에 따라 요소를 교체합니다.
 
 
 

 입력 배열 Arr[] 및 길이를 요소 수로 가져옵니다.
 
 
 

 recurbublSort(int arr[], int len) 함수는 배열과 그 길이를 가져오고 버블 정렬을 사용하여 배열을 재귀적으로 정렬합니다.
 
 
 

 가변 온도를 취하십시오.
 
 
 

 배열 길이가 1이면 void를 반환합니다.
 
 
 

 그렇지 않으면 단일 for 루프를 사용하여 배열을 탐색하고 각 요소 arr[i]>arr[i+1]에 대해 해당 요소를 교환합니다.
 
 
 

 temp=arr[i], arr[i]=arr[i+1] 및 arr[i+1]=temp로 설정합니다.
 
 
 

 이전 루프가 마지막 위치에 가장 큰 요소를 배치했기 때문에 이제 길이를 1 감소시킵니다.
 
 
 

 recurbublSort(arr,len)에 대한 재귀 호출을 수행합니다.
 
 
 

 모든 호출이 끝나면 len이 1이 되면 재귀에서 벗어나 배열이 정렬됩니다.
 
 
 

 main 내부에 정렬된 배열을 인쇄합니다.
 
 
 
예
 
#include  무효 recurbublSort(int arr[], int len){ int temp; if (len ==1){ 반환; } for (int i=0; i arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=온도; } } len=len-1; recurbublSort(arr, len);}int main(){ int Arr[] ={21, 34, 20, 31, 78, 43, 66}; int 길이 =sizeof(Arr)/sizeof(Arr[0]); recurbublSort(Arr, 길이); printf("정렬된 배열 :"); for(int i=0;i<길이;i++){ printf("%d ",Arr[i]); } 반환 0;}
 
출력
 

 위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
 
정렬된 배열:20 21 31 34 43 66 78