퀵 정렬( Quick Sort)

퀵 정렬(Quick Sort)
분할 정복 알고리즘의 하나, 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법

과정 설명

    리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
    피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다. (피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
    피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
        분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
        부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
    부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
        리스트의 크기가 0이나 1이 될 때까지 반복한다.

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

https://www.youtube.com/watch?v=7BDzle2n47c

 public class Solution5{
        public Solution5(){
            int[] arr = {3,9,4,7,5,0,1,6,8,2};
            this.QuickSort(arr);
            this.Print(arr);
        }
 
        private void QuickSort(int[] arr){
            this.QuickSort(arr, 0, arr.Length-1);
        }
 
        private void  QuickSort(int[] arr, int start, int end){
            int part2 = this.Partition(arr, start, end);
            if(start<part2-1){
                this.QuickSort(arr, start, part2-1);
            }
            if(part2<end){
                this.QuickSort(arr, part2, end);
            }
        }
 
        private int Partition(int[] arr, int start, int end){
            int pivot = arr[(start+end)/2];
            while(start<=end) {
                while(arr[start] < pivot) start ++;
                while(arr[end] > pivot) end --;
                if(start <= end){
                    this.Swap(arr, start, end);
                    start++;
                    end--;
                }
            }
            return start;
        }
 
        private void Swap(int[] arr, int start, int end){
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;
        }
 
        private void Print(int[] arr){
            foreach(var data in arr){
                Console.Write(data + " ");
            }
        }
    }