알고리즘 정렬(C++)

1972 : 정렬(SORT)

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 1425 회    시도횟수: 4289 회   

입력으로 주어진 자연수들을 오름차순 또는 내림차순으로 정렬하여 출력하여보자.

 

첫 줄에 N이 주어진다. N은 정렬 할 자연수의 개수이다. (1≤N≤100,000)
정렬방법 C가 주어진다. C값이 0이면 오름차순, 1이면 내림차순으로 출력해야한다.
N개의 자연수가 주어진다. 각 자연수는 10억 이하의 수이다.

정렬한 수들을 출력한다.

[Copy] 5 0 9 2 5 1 100

[Copy] 1 2 5 9 100

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

/************************************************************** Problem: 1972 User: a132034 Language: C++ Result: Success Time:84 ms Memory:2132 kb ****************************************************************/ #include <iostream> using namespace std; int partition(int *arr, int start, int end) { int pivot = arr[start]; int left = start; int right = end; while (left <= right) { while (left <= end && pivot >= arr[left]) left++; while (right >= start+1 && pivot <= arr[right]) right--; if (left <= right) swap(arr[left], arr[right]); } swap(arr[start], arr[right]); return right; } void quickSort(int *arr, int start, int end) { if (start < end) { int pivot = partition(arr, start, end); quickSort(arr, pivot + 1, end); quickSort(arr, start, pivot - 1); } } int main() { int N; int *arr; cin >> N; arr = new int[N + 1]; int order; cin >> order; for (int i = 1; i <= N; ++i) cin >> arr[i]; quickSort(arr, 1, N); if (order == 0) { for (int i = 1; i <= N; ++i) printf("%d\n", arr[i]); } else { for (int i = N; i > 0; --i) printf("%d\n", arr[i]); } }

?

타 라이브러리를 안쓰고 한번 구현해 보았다. 역시 맨날 사용하던 편한 sort함수를 구현하려 하니... 정렬 알고리즘 종류도 까먹어서 정렬알고리즘을 다시보는 계기가 되었다. 각종 자료구조도 그렇고 이런 간단한 알고리즘들은 구현해보는것도 좋은 것 같다. 

구현은 quick sort로 하였다. 

출력 자체는 cout으로 출력하게 되면 printf보다 느리기 때문에 시간초과가 난다. 

특히 printf, scanf와의 sync를 중지하더라도 ( ios::sync_with_stdio(false) ) endl자체가 상당히 느리기 떄문에 이렇게 endl이 많이 나오는 경우 시간이 오래 걸린다.