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

 

이전 글에서는 선택 정렬에 대해 간단히 설명하였다.

https://studywithsheep.tistory.com/6

[알고리즘] 선택 정렬(selection sort) 쉽게 이해하기!

 

이번에는, 선택 정렬을 C언어를 이용해 직접 구현해보겠다.

 

먼저 컴퓨터는 어떤 과정을 거쳐 선택 정렬을 수행할지 생각해보자.

 

지난 글에 적힌 것과 같이, 

 

먼저 이렇게 수를 비교하여 배열의 맨 앞 쪽에 가장 작은 (or 가장 큰) 수가 오도록 한다.

 

 

다음에는 당연히 그 다음으로 작은 (or 큰) 수를 찾은 뒤, 두 번째 자리로 옮겨줄 것이다.

이중 for 문을 사용해야 한다는 것을 눈치챘다면,

 

이중 for 문에 대해 이해를 잘 하고 있는 것이다. 

 

만약 아니더라도 최대한 쉽게 설명할테니 잘 따라와 주었으면 좋겠다. :)

 

 

다음 그림을 보면 이중 for 문을 어떻게 써야하는지 대충 감이 잡힐 것이다. 

 

i=0 일 동안 j는 1부터 4의 값을 가져야 하고,

 

i=1 일 동안 j는 1부터 3의 값을 가져야 한다.

 

i =3 이 될 때까지 이를 반복해주면 되고,

i = 3일 동안 j는 1 의 값만 가지면 된다. 

 

 

이를 만족하는 코드를 적어보면,

 

 for (i = 0; i < 3; i++) 
 {
        for (j = i + 1; j < 4; j++)
        {
        }
 }

 

이렇게 된다. 

 

여기까지만 적어도 선택 정렬의 절반은 구현했다고 봐도 된다.

 

뼈대가 완벽하게 짜여진 것이기 때문이다.

 

 

이제, 숫자를 비교하기 위해 

 

가장 작은 수를 보내줄 자리를 정해준다. (idx_min)

 

i = 0 일때는 배열 arr[0] 의 자리에 올 숫자를 찾아야 하고,

 

i = 1 일 때는 배열 arr[1] 의 자리에 올 숫자를 찾는 것이므로

 

int idx_min = i ; 를 적어주면 된다.

 

    for (i = 0; i < 3; i++) {
        idx_min = i;  // 이 부분을 추가로 작성
        for (j = i + 1; j < 4; j++)
        {
        }

  

하지만, 이 코드대로라면

 

 

이 사진처럼 arr[idx_min]의 값이 arr[j] 의 값보다 커도 바꾸어주지 않고 그냥 지나간다.

 

따라서, if 문을 이용해 조건을 추가해 주어야 한다.

 

    for (i = 0; i < 3; i++) {
        idx_min = i;
        for (j = i + 1; j < 4; j++)
        {
            if (arr[idx_min] > arr[j]) // if 문 추가, 
            {                          // arr[idx_min]의 값이 더 크다면,
                idx_min = j;           // idx_min 에 j 값을 넣어준다.
            }
        }

 

이제 이 코드를 지나준다면,

 

 

idx_min 은 2가 된다. 

 

따라서 최소값은 arr[idx_min]이 맞는데..

 

우리는 이 최소값을 arr[i] 로 옮겨주어야 한다.

 

 

8과 71의 자리를 바꾸어 주어야 한다는 뜻이다. 

 

 

그렇기 때문에 이중 for문을 통해 비교를 모두 거친 뒤 나온 최소값의 인덱스를 

 

arr[i] 와 바꾸어주는 코드를 추가로 작성해준다.

 

 for (i = 0; i < 3; i++) {
        idx_min = i;
        for (j = i + 1; j < 4; j++) 
        {
            if (arr[idx_min] > arr[j])
            {
                idx_min = j;
            }
        }
        temp = arr[idx_min];            // i번째 값 = arr[i] 과
        arr[idx_min] = arr[i];          //  최소값 원소 arr[idx_min] 교환
        arr[i] = temp;
    }

 

여기까지 적었으면

 

 

값이 알맞게 정렬될 수 있다. 

 

눈썰미가 좋은 사람이라면 이미 눈치챘을지도 모르지만, 

 

 for (i = 0; i < input_size - 1; i++) { // 배열의 크기: input_size 
        idx_min = i;
        for (j = i + 1; j < input_size; j++)
        {
            if (arr[idx_min] > arr[j])
            {
                idx_min = j;
            }
        }
        temp = arr[idx_min];          
        arr[idx_min] = arr[i];         
        arr[i] = temp;
    }

 

배열의 크기를 기호상수로 두고 이런 식으로 적어주어도 된다.

 

#define input_size 5
#include <stdio.h>

int main() {

    int i, j, idx_min, temp;
    int arr[input_size] = { 71, 10, 8, 37, 13 };

    for (i = 0; i < input_size - 1; i++) {
        idx_min = i;
        for (j = i + 1; j < input_size; j++)
        {
            if (arr[idx_min] > arr[j])
            {
                idx_min = j;
            }
        }
        temp = arr[idx_min];
        arr[idx_min] = arr[i];
        arr[i] = temp;
    }

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

    return 0;
}

 

이 코드를 실행시키면 정상적으로 배열된 결과를 확인할 수 있다.