2750) 11. 정렬 : 수 정렬하기

문제

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

풀이

   시간복잡도가 O($n^2$)인 정렬 알고리즘 중에 아무거나 쓰면 된다. Bubble Sort와 Insert Sort 둘 다 짜봤다(기본 개념은 여기를 참고함). 5 2 3 4 1 이란 숫자를 정렬하는 방법을 설명하는 건 아날로그적 방식으론 바로 설명할 수 있는데, 코드로 구현하는 과정은 전혀 다른 문제다. 다음에 풀어볼 Merge Sort나 Quick Sort는 특히나..

   C++이라면 #include "algorithm"의 sort함수를 이용해 훨씬 간단하게 처리할 수 있다. 예를 들어 vector 배열을 정렬한다면

sort(v.begin(), v.end());				// default : ascending order

한 줄로 해결된다.

 

#include "cstdio"

void iSort(int* data, int size) {
    // Insert Sort
    // 5 2 3 4 1 -> 2 3 5 4 1
    int j(0), temp(0);
  
    // ex. i == 3
    for(int i(1); i < size; i++) {
        temp = data[i];						// temp == 4
        
        for(j = i - 1; j >= 0 && data[j] > temp; j--) data[j + 1] = data[j];
        // 5 > 4 -> data[4]  = data[3] (5 = 4 덮어쓰기)
        data[j + 1] = temp;					// data[3] = 4
    }
}

void bSort(int* data, int size) {
    // Bubble Sort
    int temp(0);
    for(int i(size - 1); i > 0; i--) {
        for(int j(0); j < i; j++) {
            if(data[i] < data[j]) {
                temp = data[j];
                data[j] = data[i];
                data[i] = temp;
            }
        }
    }
}


int main() {
    int* data(NULL), repeat(0);
    
    scanf("%d", &repeat);
    data = new int[repeat];
    
    for(int i(0); i < repeat; i++) scanf("%d", &data[i]);
    iSort(data, repeat);
    //bSort(data, repeat);
    for(int i(0); i < repeat; i++) printf("%d\n", data[i]);
    
    delete data;
    return 0;
}