[백준] 2751번 : 수 정렬하기 2

안녕하세요 주인장 H입니다. 

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

2751번: 수 정렬하기 2

 

문제

N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 숫자가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.

출력

첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다.

예제 입력 1 복사

5 5 4 3 2 1

예제 출력 1 복사

1 2 3 4 5

 

해당 문제는 퀵정렬로 풀어볼 수 있습니다. 

하지만 퀵정렬의 문제는 언제나 시간복잡도 O(N*log N)가 되진 않아요. 

그렇기 때문에 해당 문제는 아래는 문제는 없지만 정답 처리가 되지 않습니다. 

그렇기 때문에 C++ 의 sort함수를 이용해서 사용해야지만 언제나 O(N*log N)가 됩니다.

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int number, data[1000000];

void quickSort(int* data, int start, int end) {
    if (start >= end) { // 원소가 1개인 경우 그대로 두기 
        return;
    }

    int key = start; // 키는 첫 번째 원소
    int i = start + 1, j = end, temp;

    while (i <= j) { // 엇갈릴 때까지 반복
        while (data[i] <= data[key]) { // 키 값보다 큰 값을 만날 때까지 
            i++;
        }
        while (data[j] >= data[key] && j > start) { // 키 값보다 작은 값을 만날 때까지 
            j--;
        }
        if (i > j) { // 현재 엇갈린 상태면 키 값과 교체 
            temp = data[j];
            data[j] = data[key];
            data[key] = temp;
        }
        else { // 엇갈리지 않았다면 i와 j를 교체 
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    quickSort(data, start, j - 1);
    quickSort(data, j + 1, end);
}

int main(void) {
    scanf("%d", &number);
    for (int i = 0; i < number; i++) {
        scanf("%d", &data[i]);
    }
    quickSort(data, 0, number - 1);
    for (int i = 0; i < number; i++) {
        printf("%d\n", data[i]);
    }
    return 0;
}

#include <stdio.h>
#include <algorithm>

int number, data[1000000];

int main(void) {
	scanf("%d", &number);
	for (int i = 0; i < number; i++) {
		scanf("%d", &data);
	}

	std::sort(data, data + number);
	for (int i = 0; i < number; i++) {
		printf("%d\n", data[i]);
	}
	return 0; 
}