코딩 공부 일기

//힙 정렬

//*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수)

void Sort::HeapSort(int * Array, const int Length)

{

        //힙 사이즈 조절 & 초기화

        m_Heap.Resize(Length);

        //힙에 데이터 입력

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

               m_Heap.Insert(Array[i]);

        //힙에서 데이터 다시 수령하여 입력

        //오름차순 정렬을 위해 최소 힙 사용(최대 힙을 사용하고, 데이터를 역순으로 넣어도 된다)

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

               Array[i] = m_Heap.Get();

}

//병합 정렬

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

}

//셸 정렬(*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수), div : 그룹화 배수)

void Sort::ShellSort(int * Array, const int Length, const int div)

{

        int target, k;

        int begin;

        //간격 계산

        for (int interval = Length / 2; interval > 0; interval /= div)

        {

               //그룹에서 포지션 -> 그룹에서 첫번째, 두번째 ...

               for (int posInGroup = 0; posInGroup < interval; posInGroup++)

               {

                       begin = posInGroup;

                       //삽입정렬

                       for (int i = begin + interval; i < Length; i += interval)

                       {

                              target = Array[i];

                              for (k = i - interval; k >= begin && target < Array[k]; k -= interval)

                              {

                                      Array[k + interval] = Array[k];

                              }

                              Array[k + interval] = target;

                       }

               }

        }

}

//버블 정렬(*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수))

void Sort::BubbleSort(int * Array, const int Length)

{

        //자리 변경용

        int copy;

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

        {

               for (int j = 0; j < Length - i- 1; j++)

               {

                       //뒷자리 데이터가 더 작으면 자리 변경

                       if (Array[j+1] < Array[j])

                       {

                              copy = Array[j + 1];

                              Array[j + 1] = Array[j];

                              Array[j] = copy;

                       }

               }

        }

}

//삽입 정렬(*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수))

void Sort::InsertSort(int *Array, const int Length)

{

        int target, j;

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

        {

               //현재 데이터 저장

               target = Array[i];

               //(현재 데이터 < 앞자리 데이터)라면 자리 변경

               for (j = i; j > 0 && Array[j - 1] > target; j--)

               {

                       //데이터를 뒤로 한칸씩 밀어냄

                       Array[j] = Array[j - 1];

               }

               //자리 변경이 없었으면 패스

               if (i == j)

                       continue;

               Array[j] = target;

        }

}

//선택 정렬(*Array : 정렬할 데이터 배열, Length : 배열 길이(데이터의 수))

void Sort::SelectionSort(int * Array, const int Length)

{

        //최소값 위치

        int min;      

        //자리 변경용 임시저장

        int copy;

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

        {

               //현재 자리를 최소값 위치로 지정

               min = i;

               //최소값 검색

               for (int j = i+ 1; j < Length; j++)

               {

                       //현재 최소값보다 지금 자리의 데이터가 더 작으면, 최소값으로 지정

                       if (Array[min] > Array[j])

                              min = j;

               }

               //최소값 자리가 변경 안됐으면 패스

               if (min == i)

                       continue;

               //최소값과 현재 위치 병경

               copy = Array[min];

               Array[min] = Array[i];

               Array[i] = copy;

        }

}