[C] Selection Sort in Ascending & Descending Order ::: 선택정렬

 

 

---

까다로운 부분 알아가기

---

[1] array size를 설정하지 않으면 자꾸 어디선가 에러가 난다...

▶ 직접 대괄호안에 숫자를 넣어주거나 const int로 제한해준다. 다른 방법은 아직 모르기로 함.

 

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

▶ 오름차순인경우에는 매 루프마다 가장 작은 값을 '선택'해서 얘랑 맨 앞 값이랑 바꿔준다. 그러면 가장 작은 애가 계속 앞으로 오게되므로 오름차순으로 정렬이 되는 것. 여기까지는 어딜가도 설명이 되어있다. 문제는 그래서 코드를 어케 만든다는겨...

▶ 일단, 가장 작은 애를 선택 하려면 뭔가랑 비교해서 얘가 작은지 큰지를 알아야 할텐데 어떻게 알지? 선택정렬 알고리즘에서는 계속 루프를 돌면서 더 작은 애, 더 작은 애로 계속 업데이트 해나가면서 찾아나선다. 특정 고정된 애랑 비교하는 게 아님. 하지만 바꿔줄 대상이 되는 맨 앞 값은 고정이어야 나중에 제일 작은 애를 찾아냈을 때 서로 바꿔치기 해줄 수 있다. 이게 난 이해가 안가서 수십번 반복한 후에 겨우 조금 이해한 것 같다. 개초보.

[3] 이렇게 선택정렬 설명에 따라 변수를 선언하면,

▶ 오름차순 정렬인 경우에는, 최솟값을 맨 앞과 바꿀거라 min으로 선언해주고 min을 계속 더 작은 애로 업데이트한다.

▶ 내림차순 정렬인 경우에는, 최댓값을 맨 앞과 바꿀거라 max로 선언해주고 max를 계속 더 큰 애로 업데이트 한다.

▶ 이렇게 찾아낸 최솟값 or 최댓값을 맨 앞 값과 '교체' 해줄 때 잠깐 쓰는 변수 temp도 선언해준다.

 

[4] min과 max는 어쨌든 최초에 비교가 시작되려면 초기화를 해주어야 한다.

▶ min을 최초에 array의 index(i)와 동일하게 선언해주고(인덱스를 따라가므로 outer for loop안에서 초기화 되어있음) 그 다음 값(i+1)과 비교해서 그 다음값이 min보다 더 작다고 판단하면, 엇 내가 제일 작은 줄 알았는데 아니었음. 하면서 황급히 min을 그 더 작은 애로 교체해준다. max는 엇 내가 제일 큰 줄 알았는데 아니었음. 인 경우이다.

 

[5] 두 변수를 교체(swap)하려면 코드 3줄이 필요하다.

▶ temp=variable1; variable1=variable2; variable2=temp; 이 3줄이며 이해할 필요없이 그냥 암기하면 된다.

 

[6] input을 non-number(숫자가 아닌 무언가)가 있을 때까지 계속 받으라고 되어있다.

▶ scanf(입력)가 있으면 계속 받을 수 있게 while loop로 구성해주면서(input을 받아서 구성할 array의 길이를 미리 알면 for loop로도 할 수 있지만 우린 모르므로) length를 계산해준다.

 

[7] 그럼 non-number를 어떻게 처리해야 할까?

▶ "%*s"를 사용한다. 여기서 중요한 것은 *(asterisk symbol)이다. scanf에서 *의 의미는 'read but ignore'이다. 즉, 읽어는 들이되 변수에 넣지는 않는다는 뜻이다. 왜 갑자기 이걸 쓸까? 문제에 있는 예시에 보면 'end'라는 string을 입력해서 input을 끝낸 것을 알 수 있다. 즉, 뭔가 non-number가 나오면 에러가 없이 입력자체는 되어야 하는데, 그 값이 array에 들어가버리면 안되기 때문이다.

 

#include <stdio.h>
const int MAX = 1001; ------------------ [1]

void ascSelectionSort(int A[], int n){
    int i,j,min,temp; ------------------ [3]
    for(i=0;i<n;i++){
        min=i; ------------------------- [4]
        for(j=i+1;j<n;j++){
            if(A[j]<A[min]){
                min=j; ----------------- [4]
            }
        }
        temp=A[i]; --------------------- [5]
        A[i]=A[min];
        A[min]=temp;
    }
    printf("Ascending Order: ");
    for(i=0;i<n;i++){
        printf("%d ",A[i]);
    }
}

void descSelectionSort(int A[], int n){
    int i,j,max,temp; ------------------ [3]
    for(i=0;i<n;i++){
        max=i; ------------------------- [4]
        for(j=i+1;j<n;j++){
            if(A[j]>A[max]){
                max=j; ----------------- [4]
            }
        }
        temp=A[i]; --------------------- [5]
        A[i]=A[max];
        A[max]=temp;
    }
    printf("\nDescending Order: ");
    for(i=0;i<n;i++){
        printf("%d ",A[i]);
    }
}

int main(){
    int A[MAX];
    printf("Values of A separated by spaces (non-number to stop): ");
    int n;
    while(scanf("%d",&A[n])==1){ ------- [6]
        n++;
    }
    scanf("%*s"); ---------------------- [7]
    ascSelectionSort(A,n);
    descSelectionSort(A,n);
    return 0;
}

 

---

출력결과

---