선택 정렬은 처음부터 배열을 반복하고 각 요소를 목록에서 가장 작은 요소로 교체하여 데이터를 정렬하는 데 사용되는 정렬 알고리즘 중 하나입니다. 앞으로 이동함에 따라 왼쪽 배열은 정렬되고 오른쪽 배열은 정렬되지 않습니다. 각 이동은 교환하여 인덱스의 현재 위치에 다음으로 가장 작은 값을 배치합니다.
선택 정렬 알고리즘
-
정수 arr[5]={ 5,4,2,1,3 };
-
정수 i, j;
-
인덱스 i=0에서 i<배열 크기 -1
로 트래버스-
인덱스 j=i+1에서 배열 크기 - 1까지 순회
-
가장 작은 것을 찾아 index.pos를 저장합니다.
-
-
arr[i]
를 사용하여 발견된 인덱스 pos에서 요소 교체 -
끝
재귀 선택 정렬
-
최소 요소의 인덱스 찾기
-
발견된 가장 작은 요소 인덱스가 배열 크기와 같으면 반환합니다.
-
그렇지 않으면 현재 요소를 가장 작은 요소로 교체합니다.
-
정렬된 요소를 제외한 나머지 배열에 대해 위의 단계를 재귀적으로 수행
예시
입력 - Arr[] ={ 5,7,2,3,1,4 }; 길이=6
출력 − 정렬된 배열:1 2 3 4 5 7
설명 -
First Pass :- 5 7 2 3 1 4 → swap → 1 2 7 3 5 4 1 2 7 3 5 4 → no swap 1 2 7 3 5 4 → swap → 1 2 3 7 5 4 1 2 3 7 5 4 → swap → 1 2 3 4 5 7 1 2 3 4 5 7 → no swap
입력 - Arr[] ={ 1, 2, 3, 3, 2 };
출력 − 정렬된 배열:1 2 2 3 3
설명 -
1 2 3 3 2 → no swap 1 2 3 2 3 → no swap 1 2 3 2 3 → swap → 1 2 2 3 3 1 2 2 3 3 → no swap
아래 프로그램에서 사용된 접근 방식은 다음과 같습니다.
선택 정렬의 재귀적 접근 방식에서 기본 케이스는 최소 인덱스 =배열 크기-1입니다. 그렇지 않으면 현재 인덱스가 있는 배열 스왑에서 최소값을 찾고 정렬되지 않은 오른쪽 배열을 재귀적으로 정렬합니다.
-
입력 배열 Arr[] 및 length를 요소 수로 사용합니다.
-
함수 findMin(int arr[], int i, int j)은 배열과 해당 인덱스를 가져와 arr[i+1]에서 arr[j] 사이의 최소 요소 인덱스를 반환합니다.
-
가변 minpos를 취하십시오.
-
i와 j가 모두 같으면 i를 최소 요소의 인덱스로 반환합니다. 둘 다 같기 때문입니다.
-
그렇지 않으면 minpos =findMin(arr, i + 1, j)을 사용하여 i+1에서 j까지의 위치를 재귀적으로 찾습니다.
-
if(arr[i]
-
recurselectSort(int arr1[], int len1, int pos1) 함수는 입력 배열을 선택 정렬에서 재귀를 사용하여 오름차순으로 정렬합니다.
-
pos1 ==len1이면 최소값이 없으면 반환합니다.
-
그렇지 않으면 minpos1 =findMin(arr1, pos1, len1-1)
을 설정합니다. -
현재 pos1 인덱스와 최소 요소 인덱스 minpos1이 같지 않으면 temp를 사용하여 이 인덱스의 요소를 교환합니다.
-
recurselectSort(arr1, len1, pos1 + 1)를 사용하여 나머지 배열에 대해 재귀합니다.
-
모든 호출이 끝나면 len이 1이 되면 재귀에서 벗어나 배열이 정렬됩니다.
-
main 내부에 정렬된 배열을 인쇄합니다.
예
#include <iostream>
using namespace std;
int findMin(int arr[], int i, int j){
int minpos;
if (i == j){
return i;
}
minpos = findMin(arr, i + 1, j);
if(arr[i]<arr[minpos]){
minpos=i;
}
return (minpos);
}
void recurselectSort(int arr1[], int len1, int pos1){
int temp;
int minpos1;
if (pos1 == len1){
return;
}
minpos1 = findMin(arr1, pos1, len1-1);
if (minpos1 != pos1){
temp=arr1[pos1];
arr1[pos1]=arr1[minpos1];
arr1[minpos1]=temp;
}
recurselectSort(arr1, len1, pos1 + 1);
}
int main(){
int Arr[] = {1,5,3,0,9,3,5};
int length = sizeof(Arr)/sizeof(Arr[0]);
recurselectSort(Arr,length,0);
cout<<"Sorted Array using recursive Selection sort: "<<endl;
for (int i = 0; i<length ; i++){
cout << Arr[i] << " ";
}
return 0;
} 출력
위의 코드를 실행하면 다음과 같은 출력이 생성됩니다.
Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9