■ 퀵 정렬하는 방법을 보여준다.
▶ 퀵 정렬하기 예제 (C#)
1 2 3 4 5 6 7 8 9 10 11 12 13 |
using System; int[] array = new int[] { 10, 50, 30, 20, 90, 80, 15, 20 }; QuickSort<int>(array); for(int i = 0; i < array.Length; i++) { Console.Write(array[i]); Console.Write(" "); } |
▶ 퀵 정렬하기 (C#)
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 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
using System; #region 퀵 정렬하기 - QuickSort<T>(itemArray, leftIndex, rightIndex) /// <summary> /// 퀵 정렬하기 /// </summary> /// <typeparam name="T">항목 타입</typeparam> /// <param name="itemArray">항목 배열</param> /// <param name="leftIndex">왼쪽 인덱스</param> /// <param name="rightIndex">오른쪽 인덱스</param> public void QuickSort<T>(T[] itemArray, int leftIndex, int rightIndex) where T : IComparable { if(rightIndex > leftIndex) { int pivotIndex = (leftIndex + rightIndex) / 2; int newPivotIndex = Partition(itemArray, leftIndex, rightIndex, pivotIndex); QuickSort(itemArray, leftIndex , newPivotIndex - 1); QuickSort(itemArray, newPivotIndex + 1, rightIndex ); } } #endregion #region 퀵 정렬하기 - QuickSort<T>(itemArray) /// <summary> /// 퀵 정렬하기 /// </summary> /// <typeparam name="T">항목 타입</typeparam> /// <param name="itemArray">항목 배열</param> public void QuickSort<T>(T[] itemArray) where T : IComparable { QuickSort(itemArray, 0, itemArray.Length - 1); } #endregion #region 분리하기 - Partition<T>(itemArray, leftIndex, rightIndex, pivotIndex) /// <summary> /// 분리하기 /// </summary> /// <typeparam name="T">항목 타입</typeparam> /// <param name="itemArray">항목 배열</param> /// <param name="leftIndex">왼쪽 인덱스</param> /// <param name="rightIndex">오른쪽 인덱스</param> /// <param name="pivotIndex">피벗 인덱스</param> /// <returns>인덱스</returns> private int Partition<T>(T[] itemArray, int leftIndex, int rightIndex, int pivotIndex) where T : IComparable { T pivotItem = itemArray[pivotIndex]; T temporaryItem = itemArray[pivotIndex]; itemArray[pivotIndex] = itemArray[rightIndex]; itemArray[rightIndex] = temporaryItem; int storeIndex = leftIndex; for(int i = leftIndex; i < rightIndex; i++) { if(itemArray[i].CompareTo(pivotItem) <= 0) { temporaryItem = itemArray[i]; itemArray[i ] = itemArray[storeIndex]; itemArray[storeIndex] = temporaryItem; storeIndex++; } } temporaryItem = itemArray[storeIndex]; itemArray[storeIndex] = itemArray[rightIndex]; itemArray[rightIndex] = temporaryItem; return storeIndex; } #endregion |