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 | // 퀵 정렬 함수 void QuickSort(int data[], int startIndex, int endIndex) { int pivot = 0; // 재귀호출을 감안해서 index 정보를 매개변수로 전달받는다. if (startIndex < endIndex) { // 나누어진 부분에서 startIndex와 endIndex가 만나서 pivot과 교환된 인덱스를 반환. pivot = patitionQuickSort(data, startIndex, endIndex); // 반환된 pivot 인덱스를 기준으로 quicksort 반복 QuickSort(data, startIndex, pivot - 1); QuickSort(data, pivot + 1, endIndex); } } // 실제 pivot 교환 부분 int patitionQuickSort(int data[], int startIndex, int endIndex) { int pivotIndex = endIndex; int leftIndex = startIndex; int rightIndex = endIndex; int temp = 0; // 양쪽의 Index가 만나기 전까지 반복 while (leftIndex < rightIndex) { // left Index 이동, 두 Index가 만나기 전까지 Pivot보다 큰 값을 찾는다. while ((data[leftIndex] < data[pivotIndex]) && (leftIndex < rightIndex)) { leftIndex++; } // right Index 이동, 두 Index가 만나기 전까지 Pivot보다 작은 값을 찾는다. while ((data[rightIndex] > data[pivotIndex]) && (leftIndex < rightIndex)) { rightIndex--; } // pivot보다 큰 값인 leftIndex와 작은 값인 rightIndex의 위치 변경. if (leftIndex < rightIndex) { temp = data[leftIndex]; data[leftIndex] = data[rightIndex]; data[rightIndex] = temp; } } // 두 Index가 만나는 곳과 Pivot의 값 변경 temp = data[pivotIndex]; data[pivotIndex] = data[rightIndex]; data[rightIndex] = temp; // 새로운 pivot의 위치는 rightIndex이다. return rightIndex; } | cs |
'Development > Algorithm' 카테고리의 다른 글
선택정렬 (Selection Sort) (0) | 2018.12.19 |
---|---|
알고리즘 (algorithm) (0) | 2018.12.19 |