[정렬] 선택 정렬 Selection Sort

선택 정렬 Selection Sort

 

선택 정렬이란?

최소 혹은 최댓값부터 찾아 정렬하는 방법

다른 정렬들에 비해 비교적 쉽게 구현이 가능하다.

 

(오름차순일 때)

첫 인덱스부터 정렬하는 방법으로 기준으로부터 오른쪽 값들과 비교하여 가장 작은 수를 찾아 값을 교환한다.

 

-핵심코드

1) A와 B의 값을 교환

tmp = A;  A = B;  B = tmp;

 

2) for문의 범위 설정

for( i=0; i < SIZE -1; i++){      for( j=i+1 < SIZE; j++){          ...      }  }

바깥 for 문

• 현재 기준 인덱스를 가리키는 역할
• 범위는 SIZE-1까지(SIZE-1까지 정렬하면 마지막은 정해지기 때문)

내부 for 문

• 최소(혹은 최대) 값을 찾는 역할
• 범위는 기준+1부터 SIZE까지

 

 

정렬 예시

 

선택 정렬 코드(C언어 기반)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define SIZE 10
 
int main() {
    srand(time(NULL));
    int num[SIZE], idx;
 
    //rand으로 1~50 사이의 숫자를 받음
    printf("[ Before ] \n");
    for (int i = 0; i < SIZE; i++) {
        num[i] = rand() % 50 + 1;
        printf("%-2d ", num[i]);
    }
 
    //선택정렬
    //1번째 방법
    for (int i = 0; i < SIZE - 1; i++) {
        idx = i;
        for (int j = i + 1; j < SIZE; j++) {
            if (num[idx] > num[j]) idx = j;
        }
        //if(i != idx){... swap을 줄이고자 한다면
        int tmp = num[i];
        num[i] = num[idx];
        num[idx] = tmp;
    }
 
    //2번째 방법
    /*
    for (int i = 0; i < SIZE-1; i++) {
        for (int j = i + 1; j < SIZE; j++) {
            if (num[i] > num[j]) {
                int tmp = num[i];
                num[i] = num[j];
                num[j] = tmp;
            }
        }
    }
    */
 
    //정렬 후 출력
    printf("\n\n[ After ]\n");
    for (int i = 0; i < SIZE; i++)
        printf("%-2d ", num[i]);
    printf("\n\n");
    return 0;
}

시간 복잡도

Best	O(n²)
Average	O(n²)
Worst	O(n²)