퀵 정렬(QuickSort)

배열을 정렬하는 여러가지 알고리즘에 대해 공부중이었다.
여러가지 알고리즘을 테스트하기 쉽도록 배열을 입력받고, 정렬한 후 출력하는 메서드를 만들었다.

		// 처음에 배열의 크기를 입력받고, 이후 받는 입력들을 배열에 저장한다.
        void SortNumber()
        {
        	// 배열의 크기를 입력받음.
            var arraySize = int.Parse(Console.ReadLine()!);
            var inputArray = new int[arraySize];
           
          	// 한줄씩 입력할 때 마다 배열에 순서대로 저장한다.
           	for (int i = 0; i < inputArray.Length; i++)
            {
                inputArray[i] = int.Parse(Console.ReadLine()!);
            }
            
            // 여기에 알고리즘 적용!!!!!
            inputArray = QuickSort(inputArray);
            
            // 출력한다.
            Console.WriteLine("===================");
            Console.WriteLine("최종:");
            foreach (var item in inputArray)
                Console.WriteLine(item);
        }

배열을 정렬할때에는 그 배열의 요소끼리 서로 바꾸는 경우가 많다.
반복되는 기능이므로 메서드로 만들었다.

		// swapArray 안에서 left와 right를 서로 바꾼다.
        void SwapItem(int[] swapArray, int left, int right)
        {
            Console.WriteLine("===================");
            Console.WriteLine
            ($"{left}자리의{swapArray[left]} 와 {right}자리의{swapArray[right]} 위치 변경");
            Console.WriteLine();

            var temp = swapArray[left];
            swapArray[left] = swapArray[right];
            swapArray[right] = temp;
            foreach (var item in swapArray)
                Console.WriteLine(item);
        }

아래에서 배열을 정렬한 후 리턴한다.

        int[] QuickSort(int[] inputArray)
        {
            Quick_QuickSort(inputArray, 0, inputArray.Length - 1);
            return inputArray;
        }

        void Quick_QuickSort(int[] inputArray, int left, int right)
        {
            var pivot = left;
            var low = left + 1;
            var high = right;

            while (low <= high)
            {               
                if (inputArray[low] < inputArray[pivot])
                {
                    low++;
                    continue;
                }

                if (inputArray[pivot] < inputArray[high])
                {
                    high--;
                    continue;
                }

                if (low < high)
                {
                    SwapItem(inputArray, low, high);
                }
            }
            if (left < right)
            {
                SwapItem(inputArray, pivot, high);
                Quick_QuickSort(inputArray, left, high - 1);
                Quick_QuickSort(inputArray, high + 1, right);
            }
        }
        

테스트로 크기가 9인 배열을 만들고 [5,3,8,4,9,1,6,2,7] 로 입력받았고,
이해를 돕기위해 실행되는 절차를 시각화 해보았다.

약간 헷갈리는 부분이 있었는데
엑셀에 한칸한칸 찍으면서 디버깅 하면서 보니까 이해가 잘 되었다.

재귀함수도 개념적으로는 알고있었는데 막상 쓸 일이 없었는데, 처음 써봤는데 재미있다.