선택 정렬

선택 정렬

선택 정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다. 가장 작은 것을 선택하는 데 N번, 앞으로 보내는 데 N번의 연산으로 O(N²)의 시간 복잡도를 가진다.

2

4

3

1

9

6

7

8

10

5

1

4

3

2

9

6

7

8

10

5

1

2

3

4

9

6

7

8

10

5

---

1

2

3

4

5

6

7

8

9

10

 

한번 정렬할 때마다 발견하는 최솟값을 앞으로 보내고, 최솟값을 넣은 index 부터 시작하여 다시 최솟값을 탐색하여 앞으로 보내는 과정을 반복한다.

#include <stdio.h>
#include <limits.h>
#define SIZE 1000

int a[SIZE];

void swap(int *a, int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}

int main(){
    
    int n, min, index;      					// min : 한번 정렬할때마다 찾는 최소값
    printf("정렬할 숫자 갯수를 입력해주세요\n");
    scanf("%d", &n);
    printf("정렬할 숫자 배열을 입력해주세요\n");
    for(int i = 0; i < n; i++){
        scanf("%d", &a[i]);
    }
    for(int i = 0; i < n; i++){
        min = INT_MAX;
        for(int j = i; j < n; j++){
            if(min > a[j]){
                min = a[j];
                index = j;
            }
        }
        swap(&a[i], &a[index]);
    }
    
    // 정렬된 숫자 배열 프린트
    for(int i = 0; i < n; i++){
        printf("%d  ", a[i]);
    }
   }