#include <cstdio> #include <iostream> using namespace std; void Swap(int arr[], int idx1, int idx2) { int temp = arr[idx1]; arr[idx1] = arr[idx2]; arr[idx2] = temp; } int Partition(int arr[], int left, int right) { int pivot = arr[left]; int low = left + 1; int high = right; while (low <= high) { while (pivot >= arr[low] && low <= right) low++; while (pivot <= arr[high] && high >= (left + 1)) high--; if (low <= high) { Swap(arr, low, high); } } Swap(arr, left, high); return high; } void QuickSort(int arr[], int left, int right) { if (left <= right) { int pivot = Partition(arr, left, right); QuickSort(arr, left, pivot - 1); QuickSort(arr, pivot + 1, right); } } int main() { int arr[] = { 3,2,4,1,7,6,5 }; int len = sizeof(arr) / sizeof(int); int i; QuickSort(arr, 0, len - 1); for (i = 0; i < len; i++) { cout << arr[i] << " "; } cout << endl; return 0; } |
1. 메인문에서 처음에 퀵소트 함수를 호출합니다. 2. 퀵소느 함수의 파라미터에는 배열과, 제일 처음 레프트값과, 제일 오른쪽 라이트값이들어 갑니다. 3. 이 레프트와 라이트가 left<=right 조건에 만족한다면 안으로 들어갑니다. 4. 그리고 피봇 값을 찾습니다. 피봇값은 파티션이라는 함수를 호출합니다. 5. 이 함수에는 배열과 레프트 라이트 값이 들어갑니다. 6. 들어가서 피보값은 가장 왼쪽에 있는 값이고, 로우와 하이 변수를 선언하게 되는데, 이는 로우는 레프트+1, 하이는 라이트 +1 입니다. 7. 그리고 로우와 하이가 만날때까지 와일 문을 돌립니다. 피봇 보다 값이 큰값을 찾습니다. 오른쪽에서는 하이는 피벗보다 작은 값을 찾습니다. 그리고 이것이 레프트보다는커야 합니다. 로우보다는 라이트가 커야 합니다. 오께이. 8 그리고 스왑을 해줍니다. 9. 스왑 어레이 레프트와 하이를 해주는 이유는 무엇인가요? 피봇값이 바뀌었다 이것입니다. 그리고 하이값을 리턴해줍니다. 10. 그리고 새로운 퀵 소트를 시작합니다. 배열을 넣고 레프트와 피봇 -1 까지의 범위에 대해서 그리고. 11. 그리고 그 아래에는 피봇 +1 과 가장 오른쪽을 넣어서 합니다. 오께이. 12 |