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

-입력 리스트에서 가장 작은 원소를 선택하여 해당 위치로 이동시키는 과정을 반복하여 정렬을 수행 

-해당 순서에 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선태하는 알고리즘이다

-해당 자리를 선택하고 -> 그 자리에 올 원소를 선택한다 

 

수행단계

1. 입력 리스트의 첫 번째 원소를 선택

2. 선택한 원소를 제외한 나머지 리스트에서 가장 작은 원소를 찾는다

3. 가장 작은 원소와 첫 번째 원소를 교환

4. 두 번째 원소부터 위의 과정을 반복 

 

제일 무난하고 간단해보이는 문제를 선택 정렬을 이용해서 풀어봤다

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream> 
#include <algorithm>
#include <string>
#include <vector>
#include <math.h>
#include <cmath>
#include <cstring>
using namespace std;


int main() {

    int n;
    scanf("%d", &n);
    int a[1000] = { 0, };

    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = 0; i < n - 1; i++) {
        int min = i;

        //최솟값을 탐색 
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[min]) { 
                min = j;
            }
        }

        //정렬한다 
        swap(a[i], a[min]);
    }

    for (int i = 0; i < n; i++) {
        printf("%d\n", a[i]);
    }
    

  
    return 0;
}

가장 간단한 오름차순으로 정렬하는 문제이다

 

먼저 가장 바깥 for문은 0부터 n-1까지 돈다

n-1까지 돌면 정렬이 끝나기 때문이다

배열의 마지막 원소는 이미 이전 n-1개의 원소들 중 가장 크거나 작은 값이므로, 마지막 원소를 대상으로 다시 비교할 필요가 없다

 

이건 안쪽 for문을 도는 방법이다

안쪽 for을 돌면서 최솟값을 찾는것이다

 

최솟값을 찾았으면 swap으로 정렬을 하면 된다

 

이 정렬알고리즘은 i=0일때는 0번째 인덱스에 들어가는 원소를 찾기만 하면 된다 자리는 이미 정해져있따