[알고리즘] 선택 정렬(Selection Sort)이란?

선택정렬

• 정렬된 왼쪽 리스트와 정렬안된 오른쪽 리스트로 나누어 정렬
• 초기에는 왼쪽 리스트는 비어있고 정렬할 숫자들은 모두 오른쪽 리스트에 존재한다.
• In-place 정렬 알고리즘의 하나 (입력배열 이외의 다른 추가 메모리를 요구하지 않는 정렬 방법)
• 원소를 넣을 위치는 이미 정해져있고 어떤 원소를 넣을지 "선택"하는 알고리즘
• 오른쪽리스트에서 최소값을 선택하여 왼쪽 리스트로 순서대로 옮기는 방식이다.

---

 

선택정렬 알고리즘 과정

1. 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행한다.
2. 1회전을 수행하고 나면 가장 작은 값의 자료가 맨 앞에 오게 되므로 그 다음 회전에서는 두 번째 자료를 가지고 비교한다. 마찬가지로 3회전에서는 세 번째 자료를 정렬한다.
   
   

#include <stdio.h>
#include <stdlib.h>
#pragma warning(disable:4996)

int main() {
    int arr[5] = {9,6,7,3,5};
    int i,j, min, temp;
    for(i=0; i< 5;i++){
        min = i;
        for(j=i+1; j<5; j++)
            if(arr[j] < arr[min])
                min = j;
        temp = arr[i];
        arr[i] = arr[min];
        arr[min] = temp;
    }

    for(int i=0; i< 5;i++){
        printf("%d ", arr[i]);
    }

}

---

 

선택정렬 특징 및 시간 복잡도

비교 횟수
두 개의 for 루프의 실행 횟수

외부 루프: (n-1)번
내부 루프(최솟값 찾기): n-1, n-2, … , 2, 1 번

교환 횟수
외부 루프의 실행 횟수와 동일. 즉, 상수 시간 작업
한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 3(n-1)번
T(n) = (n-1) + (n-2) + … + 2 + 1 = n(n-1)/2 = O(n^2)

---