(C언어) 8. 정렬 방식

<정렬 방식>

정렬의 방식은 매우매우 많은 것으로 들었다. 버블, 퀵, 선택, ... 하지만 오늘은 두가지만 다뤄볼 것이다. 버블, 그리고 선택.

[[버블 정렬]]

사실 버블정렬은 앞의 이진 탐색에서 써먹었다.

for (i = 0; i < input - 1; ++i) {//숫자 정렬
        for (j = 0; j < input - 1; ++j) {
            if (arr[j] > arr[j + 1]) {
                temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }

http://sunrinnote.tistory.com/9

요기에 있는 내용이다. 

버블 정렬은 자신과 바로 옆에 있는 값을 비교해서 (오름차순이면) 뒤에 있는 값이 자신보다 작다면 자리를 바꾸는 알고리즘이다.

2번째 줄에서 input-1을 한 이유는 '맨 끝에서 바로 앞' 수와 '맨 끝'수를 비교하고 끝내려고 했기 때문이다.

만약 input-1이 아니라 그냥 input을 썻다면?

컴퓨터 : 야 프로그래머! 이거 맨끝수랑 그 다음수 비교해야되는데 그 다음수가 '\0'인데 괜찮을까?

프로그래머 : 음? 아 미안....

[[선택 정렬]]

선택정렬은 이런거다: 자신이 최소값이 아니라면 가장 작은 값과 바꾸어 나아가는 것이다.

코드를 짜보았다:

#include <stdio.h>
 
int main() {
    int arr[5] = { 9, 7, 1, 8, 3 };
    int i, j;
    int temp;
    int from = 0;//현재 바꾸려고 하는 arr[from]
    int smallest = 0;//최솟값


    for (i = 0; i < 5; ++i) {
        for (j = from + 1; j < 5; ++j) {
            if (arr[j]<arr[smallest]) {
                smallest = j;
            }
        }
        if (arr[smallest]<arr[i]) {
            temp = arr[smallest];
            arr[smallest] = arr[i];
            arr[i] = temp;
        }
        ++from;
    }
 
    for (i = 0; i < 5; ++i) {
        printf("%d", arr[i]);
    }
    return 0;
}

여기서 smallest는 특정 정수가 입력되는것이 아니라, 배열 arr[]의 값을 읽을 떄 arr[smallest]같은 식으로 쓴다. 그래서 smallest를 0으로 초기화 시킨 것이다.

12~16줄은 현재 자기 자신 이후의 값들 중에서 최솟값을 찾는 코드이다. 

17~21줄은 현재 자기 자신(arr[i])와 최솟값의 자리를 바꾸는 코드이다.