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

 

오늘은 저번에 작성했던 선택 정렬 개념을 바탕으로 코딩을 해보려고 한다.

 

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

알고리즘 - 선택 정렬에 대해서 알아보자

 

 

데이터의 형태는 저번 버블솔트 때와 같이 배열로 진행하려고 한다.

가장먼저 고민하게 된 부분은 최솟값을 어떻게 찾고 지정할건가였는데 생각해보던중에 예전에 점수 등수를 정하는 프로그램을 코딩했던 기억이 났다.

그걸 이용하면 최소값을 찾을 수 있는 것같다.

그 방법이란 바로 이것인데.

각 각의 데이터마다 전체 데이터를 비교하여 자신이 더 큰 수일때마다 카운트를 늘리는 것이다.

기본 값을 1이라고 했을때 자신이 가장 작은 수라면 그대로 1일 것이고, 자신이 가장 큰 수라면 1 + (n-1) = n으로 정해질 것이다.

그러면 그걸 보고 순위를 정할 수가 있을 것같다.

데이터 값과 순위값을 저장해야 함으로 이번에 지인에게 새롭게 배운 구조체 배열을 사용해보려 한다.

 

 

#include <stdio.h>

typedef struct data{
    int value;
    int rank;
}DATA;

int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    DATA dt[num];
    for (int i = 0; i <num; i++){
        printf("%d번째 데이터 입력 : ", i+1);
        scanf("%d", &(dt[i].value));
        dt[i].rank = 1;
    }
    for(int i = 0; i<num; i++){
        printf("%d\n", (dt[i].value));
    }
    return 0;
}

 

일단은 데이터 삽입과 프린트를 해보았다.

(사실 함수로 다 나눠서 깔끔하게 정리하려 했지만 스택에서 다 초기화됨으로 포인터가 필연적으로 사용되게 됨으로 뭔가 보기에 괴랄해 지려해서 그냥 메인에서 작업하게 되었다.)

 

데이터를 집어넣고 rank값을 1로 다 초기화를 시켜주는 작업까지 완료했다.

이제 rank 값을 변화 시키고 새롭게 정렬시키면 될 것 같다.

 

#include <stdio.h>

typedef struct data{
    int value;
    int rank;
}DATA;

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

tmp 변수까지 생성해서 선택정렬을 완성시켰다.

 

이중 for문이 2번이나 있다는게 조금 마음에 걸린다.

이렇게까지 복잡해야만 하는가 생각이 들게 됬다.

구조체를 만들지 않고 그냥 배열하나와 새로운 배열 하나를 생성해도 바로 옮기는게 가능하지 않을까?

 

 

#include <stdio.h>

int main(int argc, const char * argv[]) {
    int num;
    printf("데이터 개수 입력 : ");
    scanf("%d", &num);
    int first[num];
    for(int i=0; i<num; i++){
        printf("%d번째 데이터 입력 : ", i+1);
        scanf("%d", &(first[i]));
    }
    int result[num];
    for(int i=0; i<num; i++){
        int cnt = 0;
        for(int k=0; k<num; k++){
            if (first[i] > first[k]){
                cnt++;
            }
        }
        result[cnt] = first[i];
    }
    for (int i=0; i<num; i++){
        printf("%d\n", result[i]);
    }
    return 0;
}

확실히 더 간결해 졌다.

 

다만 차이가 있다면 배열을 두개를 사용한다는 것인데 결론적으로 봤을 때 후자가 더 메모리 사용이 적을 것 같다.

후자에 경우는 코드도 짧기도 하지만 배열 두개와 int형 한개, stack에서 돌아가는 int형들로 이루어져있다.

 

하지만 전자에 경우에는 배열자체가 int형 두개로 이루어진 구조체 배열이여서 이미 구조체 배열 한개가 후자의 배열 두개와 비슷한 크기가 된다.

for문 또한 전자가 더 복잡함으로 후자가 더 간결한 듯하다.

이제 내가 짠 선택 정렬 알고리즘 코드는 여기까지이다.

다음 시간에는 앞선 선배들이 짜온 알고리즘을 보고 수정하는 시간을 가져보려고 한다.