알고리즘 - 선택 정렬을 코딩해보자!(2)

https://shineild-security.tistory.com/31

알고리즘 - 선택 정렬을 코딩해보자!(1)

 

1편에 이어서 2편이다.

 

오늘은 다른 사람들의 코드를 참고하고 기존 코드를 수정해보려고 한다.

 

우선 위키백과를 참고해보았다.

 

void selectionSort(int *list, const int n)
{
    int i, j, indexMin, temp;

    for (i = 0; i < n - 1; i++)
    {
        indexMin = i;
        for (j = i + 1; j < n; j++)
        {
            if (list[j] < list[indexMin])
            {
                indexMin = j;
            }
        }
        temp = list[indexMin];
        list[indexMin] = list[i];
        list[i] = temp;
    }
}

내 코드와 다른 점이 있다면 이중 for문을 돌릴 때 j를 0부터 시작하지 않고 i + 1 부터 시작한다는 것인데, 이게 맞는 듯하다.

어차피 i가 한번 끝날때마다 i번째에 있는 데이터는 정렬을 완성하기 때문에 i 이하의 숫자는 이미 정렬된 데이터로 건드리지 않아도 되기 때문이다.

신기한건 indexMin을 사용하여 i 대신 사용한다는 점인데 왜 저렇게하는지 잘 이해가 안된다.

그냥 list[j] < list[i]를 비교 후

indexMin = j 를 해도 상관없을텐데 말이다.

(코드를 다 읽고 사용의 이유를 알게되었다.)

 

그리고 나는 배열을 두개 생성해야 저런 과정이 가능했는데 이번 코드를 보면 배열을 하나만 써도 되는 것 같다.

(흠... 왜 이 생각을 못했지?)

그리고 카운트를 하지 않고 정렬을 하였다.

음 숫자로 표현해서 보게되면

list[1] < list[0]이라면 0을 1로 바꾸고

list[2] < lsit[1]로 다시 비교하게 된다.

많약 [2]의 데이터가 더 크다면 다음 for문에서는 list[3] < list[1]를 비교하게 된다.

결국에는 indexMin에는 for문이 끝나게 되면 i+1 ~ n-1 중에 가장 최솟값이 들어가게 된다.
그렇게 최솟값을 찾으면 temp에 저장하고 i번째 인덱스와 데이터를 바꾸게 된다.

나는 최대값을 찾는 쪽으로 방향을 잡고 rank값을 설정했었는데 한번에 최솟값을 찾아서 바꿔주게 되면 배열을 하나만 이용해도 된다는 것을 알게되었다.

 

 

그래서 나도 다시 배열 하나만 쓰고 할 수 있도록 코딩을 짜보았다.

 

#include <stdio.h>
int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    int data[num];
    for(int i=0; i<num; i++){
        printf("%d번째 데이터 입력 : ", i+1);
        scanf("%d", &(data[i]));
    }
    
    for(int i=0; i<num-1; i++){
        int min = i;
        int tmp;
        for(int k=i+1; k<num; k++){
            if (data[k] < data[min]){
                min = k;
            }
        }
        tmp = data[min];
        data[min] = data[i];
        data[i] = tmp;
    }
    
    for (int i=0; i<num; i++){
        printf("%d\n", data[i]);
    }
    return 0;
}

크흠 위키백과와 별반 다를게 없는 녀석이 되어버렸다;

 

 

선택정렬을 알아보는 도중 추가로 알게된 사실이 몇개 있다.

 

순서 복잡도는 이렇다고 한다.

네, 그냥 이렇데요.

 

 

지난번에 버블솔트에 대해서 나눴던 적이 있었다.

이번 선택정렬은 버블정렬보다 더 효율 적인 정렬이다.

하지만 다음에 알아볼 삽입 정렬보다는 비효율적이라고 한다.