퀵 정렬(Quick Sort)

• 퀵 정렬
  

리스트의 데이터 중 기준이 되는 하나의 데이터를 선정 => 기준(Pivot)

기준(Pivot)을 선택하는 방법은 많지만, 아래의 설명과 코드에선 중간에 있는 데이터를 기준(Pivot)으로 선정

기준(Pivot)보다 작은 데이터들을 왼쪽, 큰 데이터들을 오른쪽으로 정렬

정렬 완료 후 기준(Pivot)을 기점으로 좌우로 분할하여
다시 정렬

분할된 그룹의 크기가 1이하가 될때까지 반복

//재귀 함수 이용

//*Array : 정렬할 데이터 배열, LeftRange : 가장 왼쪽의 위치, RightRange : 가장 오른쪽의 위치

void Sort::QuickSort(int *Array, int LeftRange, int RightRange)

{

       

        int copy; //자리 변경용 저장 변수

        int left = LeftRange; //검색할 데이터의 위치 : 왼쪽부터 시작, 기준보다 큰 데이터를 찾는다

        int right = RightRange; //검색할 데이터의 위치 : 오른쪽부터 시작, 기준보다 작은 데이터를 찾는다

        int pivot = Array[(left + right) / 2]; //기준

 

       //left가 right보다 작거나 같으면 반복 계속

        while (left <= right)

        {

               //pivot보다 큰 데이터를 찾을때까지 반복

               while (Array[left] < pivot)

                       left++;

 

               //pivot보다 작은 데이터를 찾을때까지 반복

               while (Array[right] > pivot)

                       right--;

 

               //left가 right보다 작거나 같으면 데이터 교환

               if (left <= right)

               {

                       copy = Array[left];

                       Array[left] = Array[right];

                       Array[right] = copy;

 

                       left++;

                       right--;

               }      

        }

 

        //입력된 범위 중 가장 왼쪽 위치(LeftRange)보다 right의 위치가 더 크면 정렬 실행

        if (LeftRange < right)

               QuickSort(Array, LeftRange, right);

 

        //입력된 범위 중 가장 오른쪽 위치(RightRange)보다 left의 위치가 더 작으면 정렬 실행

        if (left < RightRange)

               QuickSort(Array, left, RightRange);

}