삽입 정렬은 카드 한 벌과 같은 요소를 삽입하여 데이터를 정렬하는 데 사용되는 정렬 알고리즘 중 하나입니다. 모든 요소는 왼쪽에서 오른쪽으로 정렬되고 첫 번째 요소는 이미 정렬된 것으로 간주하고 나머지는 왼쪽의 정렬된 목록에 삽입합니다. 각 요소는 올바른 위치에 삽입될 때까지 왼쪽 목록의 각 요소와 비교됩니다.
삽입 정렬 알고리즘
-
정수 arr[5]={ 5,4,2,1,3 };
-
정수 i, j;
-
인덱스 j=i+1에서 j<배열 크기
로 트래버스 -
각 요소 arr[j]에 대해 arr[i]
-
목록에 arr[j]를 배치하고 더 큰 모든 요소를 오른쪽으로 한 위치 이동합니다.
-
끝
재귀 삽입 정렬
-
배열 길이가 1이면 반환합니다.
-
인덱스 0의 요소를 배열 크기 1로 재귀적으로 정렬
-
정렬된 배열의 마지막 요소 삽입
예시
입력 - Arr[] ={ 5,7,2,3,1,4 }; 길이=6
출력 − 정렬된 배열:1 2 3 4 5 7
설명 -
5 7 2 3 1 4 → 5 already sorted 5 7 2 3 1 4 → 7 at correct place 2 5 7 3 1 4 → 2 compared with 5,7 and inserted 2 3 5 7 1 4 → 3 compared with 5,7 and inserted 1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted 1 2 3 4 5 7 → 4 compared with 5,7 and inserted
입력 - Arr[] ={ 1, 2, 3, 3, 2 };
출력 − 정렬된 배열:1 2 2 3 3
설명 -
1, 2, 3, 3, 2 → 1 already sorted 1, 2, 3, 3, 2 → 2 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
버블 정렬의 재귀적 접근 방식에서 기본 케이스는 배열 길이 =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 <bits/stdc++.h>
using namespace std;
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);
cout<<"Sorted array : ";
for(int i=0;i<length;i++){
cout<<Arr[i]<<" ";
}
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Sorted array : 20 21 31 34 43 66 78