//https://www.acmicpc.net/problem/2751 #include <iostream> | |
using namespace std; | |
int arr[1000001]; | |
int n; | |
void swap(int a, int b){ | |
int tmp=arr[a]; | |
arr[a]=arr[b]; | |
arr[b]=tmp; | |
return; | |
} | |
int partition(int low, int high){ | |
int pivotidx=low+(high-low)/2; | |
int pivotval=arr[pivotidx]; | |
swap(pivotidx, high);//pivot을 오른쪽으로 보내줌 | |
int stridx=low; | |
for(int i=low; i<high; i++){ | |
if(arr[i]<pivotval){ | |
swap(i, stridx); | |
stridx+=1; | |
} | |
} | |
swap(stridx, high); | |
return stridx; | |
} | |
void quick_sort(int low,int high){ | |
if(low<high){ | |
int pivot=partition(low, high); | |
quick_sort(low, pivot-1); | |
quick_sort(pivot+1, high); | |
} | |
return; | |
} | |
int main(){ | |
//int n; | |
/*첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. | |
둘째 줄부터 N개의 줄에는 숫자가 주어진다. | |
이 수는 절대값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다.*/ | |
cin >>n; | |
for(int i=0; i<n; i++) | |
cin >> arr[i]; | |
quick_sort(0,n-1); | |
for(int i=0; i<n; i++){ | |
cout << arr[i]<<'\n'; | |
} | |
return 0; | |
} |
'알고리즘 문제 풀이 > 1DP_과제(~180615)' 카테고리의 다른 글
18505_2751_수 정렬하기 2(합병정렬) (0) | 2018.05.05 |
---|---|
180505_6679_싱기한 네자리 숫자 (0) | 2018.05.05 |
180503_3460_이진수 (0) | 2018.05.03 |
180502_2576_홀수 (0) | 2018.05.02 |
180501_2587_대표값2 (0) | 2018.05.01 |