[자료구조] 선택정렬

#include <stdio.h>
void select(int arr[], int len){ // len은 4다.
int i;
int j;
int min; // 배열의 최소값 가진 인덱스 구하는 변수
int temp; // 고정값과 가장 작은값 교환변수

for(i=0; i<len-1; i++){ // 고정할 값은 배열 끝의 바로 전까지
min = i; // 고정할 값을 바꾼다.
for(j=i+1; j<len; j++){ // len인 이유는 비교할 변수는 배열 끝까지 비교해야하기 때문
// i+1인 이유는 고정할 배열값과 겹치면 안되기 때문

if(arr[min] > arr[j]){ // 배열 끝까지 가장 작은 값을 가진 인덱스를 구한다.
min = j;
}
}
temp = arr[min]; // 이제 고정한 값과 가장 작은 값을 교환해준다.
arr[min] = arr[i]; // 교환할 것이 없으면? 자기 자신에게 넣기 때문에 값은 안변함
arr[i] = temp;
}
}

int main(){
int arr[] = {5,9,8,7};
int i;
select(arr, sizeof(arr)/sizeof(int));
for(i=0; i<4; i++){
printf("%d ", arr[i]);
}
return 0;
}

// 선택정렬은 i를 0부터 마지막 바로 전까지 하나씩 이동하며
// 자기 앞에 있는 배열 인자들과 비교하여 가장 작은 것부터 차례로 채워넣는 것이다.
// 그림 - 핵심은 i와 min을 교환하는 것이다.

i j min
0 1 0
0 2 0
0 3 0 -> 5987 (변화없음)
1 2 2
1 3 3 -> 5789 (인덱스1의 7과 인덱스 3의 9를 교환한다.)
2 3 2 -> 5789 (변화없음)

시간 복잡도 - O(n)