코딩 공부 일기

//병합 정렬

//*Array : 정렬할 데이터 배열, Start : 데이터 시작위치, End : 데이터 마지막 위치

void Sort::MergeSort(int * Array, int Start, int End)

{

        //분할된 그룹의 크기가 1이하면 수행안함

        if (End <= Start)

               return;

        int mid = (Start + End) / 2;      //중간 데이터의 위치

        int length = End - Start + 1;     //분할된 그룹의 크기

        int *copyArray = new int[length]; //임시 저장공간

        int first = Start;    //첫번째 그룹의 시작 지점

        int second = mid + 1; //두번째 그룹의 시작 지점

        int copy = 0;         //임시 저장공간 인덱스

        //분할

        MergeSort(Array, Start, mid);    //첫번째 그룹

        MergeSort(Array, mid + 1, End);  //두번째 그룹

        //분할한 두 그룹을 다시 병합

        while (first <= mid && second <= End)

        {

               //임시 저장공간에, 데이터가 작은 순서대로 입력

               copyArray[copy++] =

                       Array[first] < Array[second] ? //첫번째 그룹의 데이터가 두번째 그룹의 데이터 보다 작은가?

                       Array[first++] :               //작다면 첫번째 그룹의 데이터 입력

                       Array[second++];               //아니라면 두번째 그룹의 데이터 입력

        }

        //입력이 되지 않고 남아 있는 데이터 처리

        //      어떤 그룹의 데이터가 남았는지 찾고

        int i = first <= mid ? first : second;

        //      순서대로 임시저장 공간에 입력

        for (; copy < length; copy++, i++)

               copyArray[copy] = Array[i];

        //데이터 목록에 임시저장한 데이터들 입력

        for (i = Start, copy = 0; i <= End; i++, copy++)

               Array[i] = copyArray[copy];

        //입시저장공간 메모리 해제

        delete[] copyArray;

        copyArray = NULL;

}

//기수 정렬

//*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수), MaxNum : 배열에서 가장 큰 수

void Sort::RadixSort(int * Array, const int Length, int MaxNum)

{

        int *store[10];          //각 자리수를 저장하는 공간

        int rear[10];            //각 저장공간에서 가장 늦게 입력된 데이터의 위치

        int radix;               //어떤 큐에 데이터를 입/출력 할건지 지정하는 변수

        int MaxMultiples = 1;    //최대 자릿수

        //저장 공간 초기화

        for (int i = 0; i < 10; i++)

        {

               store[i] = new int[Length];

               rear[i] = -1;

        }

        //최대 자릿수 계산

        while (MaxNum > 0)

        {

               MaxNum /= 10;

               MaxMultiples *= 10;

        }

        //정렬 시작

        for (int multiples = 10; multiples <= MaxMultiples; multiples *= 10)

        {             

               //비교하고자 하는 자릿수를 구하기 위해 나눠야 하는 수

               int div = multiples / 10;

               //기수 별로 데이터 분류

               for (int i = 0; i < Length; i++)

               {

                       //기수 계산

                       radix = Array[i] % multiples;

                       radix /= div;

                       //구한 기수의 저장소에 데이터 저장

                       //데이터를 저장 할 수록 그 기수의 rear가 한칸씩 뒤로 밀린다.

                       store[radix][++rear[radix]] = Array[i];

               }

               //데이터를 기수0 -> 기수9 순으로 순차적으로 입력

               int index = 0;

               for (radix = 0; radix < 10; radix++)

               {

                       //각 기수 순서대로 데이터 입력(각 기수 안에선 입력 받은 순으로 입력)

                       for(int  i = 0; i <= rear[radix]; i++)

                       {

                              Array[index++] = store[radix][i];

                       }

                       //입력이 완료된 기수의 rear는 -1로 초기화

                       rear[radix] = -1;

               }

        }

        //저장소의 메모리 해제

        for (int i = 0; i < 10; i++)

        {

               delete[] store[i];

               store[i] = NULL;

        }

}

//재귀 함수 이용

//*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);

}