fork download
copy 
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int N; // 정려할 숫자의 개수
  6. int arr[10000005]; // 정렬할 숫자 배열
  7.  
  8. // 삽입 정렬
  9. void InsertSort(int left, int right) {
  10.  
  11.   	// 왼쪽+1 부터 key 설정
  12. 	for (int i=left+1; i<=right; i++) {
  13. 		int key = arr[i];
  14. 		int j;
  15.  
  16.       	// key가 배열의 값보다 작은 경우 밀고 큰 경우 삽입
  17. 		for (j=i-1; j>=left; j--) {
  18. 			if (key < arr[j]) {
  19. 				arr[j+1] = arr[j];
  20. 			}
  21. 			else {
  22. 				break;
  23. 			}
  24. 		}
  25. 		arr[j+1] = key;
  26. 	}
  27. }
  28.  
  29.  
  30. // 퀵소트
  31. void QuickSort(int left, int right) {
  32.  
  33. 	if (left >= right) return; // 만약 왼쪽이 오른쪽보다 크다면 종료
  34.  
  35. 	// 크기가 작은 경우 삽입 정렬으로
  36. 	if (right-left<40) { InsertSort(left, right); return; }
  37.  
  38. 	int pivot = left; // 피벗은 처음으로 설정
  39. 	int low = left+1, high = right; // low, high 설정
  40. 	int temp; // 교환을 위한 인자 설정
  41.  
  42. 	// 포인터가 엇갈리면 종료
  43. 	while(low <= high) {
  44.  
  45. 		// low를 pivot보다 큰 수가 나올 때까지 탐색
  46. 		while(low <= right && arr[low] <= arr[pivot]) {
  47. 			low++;
  48. 		}
  49.  
  50. 		// high를 pivot보다 작은 수가 나올 때까지 탐색
  51. 		while (high > left && arr[high] >= arr[pivot]) {
  52. 			high--;
  53. 		}
  54.  
  55. 		// 포인터가 엇갈린 경우 
  56. 		if (low > high) {
  57. 			temp = arr[high];
  58. 			arr[high] = arr[pivot];
  59. 			arr[pivot] = temp;
  60. 		}
  61.  
  62. 		// 그 전에는 계속 스왑
  63. 		else {
  64. 			temp = arr[low];
  65. 			arr[low] = arr[high];
  66. 			arr[high] = temp;
  67. 		}
  68.  
  69.  
  70. 	}
  71.  
  72. 	// 피벗 기준으로 왼쪽과 오른쪽에 대해 퀵소트
  73. 	QuickSort(left, high-1);
  74. 	QuickSort(high+1, right);
  75.  
  76. }
  77.  
  78. int main() {
  79.  
  80. 	ios_base::sync_with_stdio(false);
  81.     cin.tie(NULL);
  82.     cout.tie(NULL);
  83.  
  84. 	cin >> N;
  85.  
  86. 	for (int i=0; i<N; i++) {
  87. 		cin >> arr[i];
  88. 	}
  89.  
  90. 	QuickSort(0, N-1);
  91.  
  92. 	for (int i=0; i<N; i++) {
  93. 		cout <<  arr[i] << endl;
  94. 	}
  95.  
  96.  
  97.  
  98. 	return 0;
  99. }
Success #stdin #stdout 0s 5380KB
comments (?)
stdin
copy 
5
1
4
5
2
3
stdout
copy 
1
2
3
4
5
https://ideone.com/em3nHW
language:
C++ (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!