티스토리 뷰

알고리즘

[Sort] QuickSort

seunggabi 승가비 2018. 9. 11. 21:24

[Sort] QuickSort


#include <iostream>
using namespace std;

#define SIZE 1000000

int swap(int &a, int &b) {
int temp = a;
a = b;
b = temp;
}

void print(int *arr, int n) {
for(int i=0; i<n; i++) {
cout << arr[i] << " ";
}
cout << endl;
}

void quickSort(int *arr, int left, int right) {
if(left >= right) {
return;
}

int pivot = arr[(left + right) / 2];
int r = right;
int l = left;

while(l <= r) {
while (pivot > arr[l]) l++;
while (pivot < arr[r]) r--;

if(l < r) {
swap(arr[l], arr[r]);
l++;
r--;
}
}

quickSort(arr, left, l-1);
quickSort(arr, l+1, right);
}

int main() {
int n;
int arr[SIZE];

cin >> n;
for(int i=0; i<n; i++) {
cin >> arr[i];
}

quickSort(arr, 0, n-1);

print(arr, n);

return 0;
}


'알고리즘' 카테고리의 다른 글

[BFS & DFS] tomato  (0) 2018.09.16
[DataStructure] Queue?  (0) 2018.09.13
[Sort] QuickSort  (0) 2018.09.11
[DP] changeCoin?  (0) 2018.09.08
[Greedy] jewelryThief - priority_queue(heap)  (0) 2018.09.08
[Math] changeProposition?  (0) 2018.09.08
댓글
댓글쓰기 폼