[C언어 선택정렬 알고리즘] 선택정렬 구현하기

💡 이번에는 선택정렬 하는 법을 배워보았다.

문제

💡 사용자가 입력한 값이 오름차순으로 선택정렬되게 코드를 구현하시오

당연히 없는 문제기에 대충 내가 만들었다.

해답

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

int a[SIZE];

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

int main(void) {
    int n, min, index;
    scanf("%d", &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]);
    }

    return 0;
}

설명

선택정렬이란 가장 작은 것을 선택해서 앞으로 보내는 정렬 기법이다.

가장 작은 것을 선택하는 데에 N번, 앞으로 보내는 데에 N번의 연산으로 𝑂(𝑁제곱)의 시간 복잡도를 가진다.

swap 함수

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

1. temp에 a값을 넣어준다.
2. a에 b값을 넣어준다.
3. b에 temp(이전에 넣어주었던 a값)을 넣어준다.

main 함수

int main(void) {
    int n, min, index;  // min은 한번 검색 할때마다 가장 작은 값
    scanf("%d", &n);

		// a배열에 값을 넣어주는 역할
    for (int i = 0 ; i < n ; i++) {
        scanf("%d", &a[i]);
    }

    for (int i = 0 ; i < n ; i++) {
        min = INT_MAX;  // 작은값을 항상 선택하기 위해 일단 가장 큰 값을 넣어준다.

        // i부터 출발해서 n까지 가면서
        for (int j = i ; j < n ; j++) {
            // 현재 보고있는 원소가 min값보다 작다면
            if (min > a[j]) {
                min = a[j];
                // 가장 작은 값이 위치하는 곳이 index
                index = j;
            }
        }
        // 해당 i번째 값과 index의 값을 바꿔주면 됨
        swap(&a[i], &a[index]);
    }

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

    return 0;
}

도대체 n 의 정체가 무엇인지 전혀 모르겠다.

다른 변수들과 코드들은 이해하였으나 n 이 이해가 되지 않으니 찜찜한 기분이다.

length를 뜻하는 것 같기는 한데 흠…

---

마치며..

나중에 내가 이 포스팅을 보면서 이것도 몰랐구나 하는 날이 왔으면 좋겠다.

지금은 너무 어려워서 쩔쩔매는 중이다.

끝까지 검색해서 찾아보고싶으나 이것만 찾아볼 수는 없고 똑같은 예제에 설명이 되어있는 것이 없어서 답답하다.