코딩 공부 일기

//Num : 원판 번호 Src : 출발지, mid : 경유지 Dest : 목적지

void Algorithm::TowerOfHanoi(int Num, int Src, int mid, int Dest)

{

        //원판 번호가 1이라면(제일 작은 원판)

        if (Num == 1)

        {

               //원판 이동

               printf("원판 %d : %d -> %d\n", Num, Src, Dest);

        }

        else

        {

               //자신의 위에서 원판들 이동(자신보다 작은 원판)

               //출발지점 => 경유지점

               TowerOfHanoi(Num - 1, Src, Dest, mid);

               //원판 이동

               printf("원판 %d : %d -> %d\n", Num, Src, Dest);

               //경유지로 이동 시켰던 원판들 다시 자신의 위로 이동

               //경유지점 => 도착지점

               TowerOfHanoi(Num - 1, mid, Src, Dest);

        }      

}

int Algorithm::Fibonacci(int length)

{

        if (length < 1)

               return 0;

        if (length < 3)

               return 1;

        return Fibonacci(length - 2) + Fibonacci(length - 1);

}

int Algorithm::Fibonacci(int length)

{

        int prev = 1;

        int now = 0;

        int sum = 0;

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

        {

               sum = prev + now;

               prev = now;

               now = sum;

        }

        return sum;

}

int Algorithm::LeastCommonMultiple(int num01, int num02)

{

//더 큰 수를 시작 점으로

        int num = num01 > num02 ? num01 : num02;

//최소 공배수를 찾을 때까지 반복

        while(true)

        {

//제일 먼저 두 수 모두로 나눠떨어지는 수가 최소 공배수

               if ((num % num01 == 0) && (num % num02 == 0))

               {

                       return num;

               }

               //찾을때까지 1씩 더함

               num++;

        }

}

int Algorithm::LeastCommonMultiple(int num01, int num02)

{

        int Divisor;                    //최대 공약수

        int Multiple = num01 * num02;   //두 수의 곱

        //최대 공약수 구함

        while (num02)

        {

               Divisor = num01 % num02;

               num01 = num02;

               num02 = Divisor;

        }

        Divisor = num01;

        return Multiple / Divisor;

}

//최대 공약수

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

        //방법01

        int max = 1;    //공약수 저장 변수

        int length = num01 < num02 ? num01 : num02;      //작은 숫자 만큼만 반복 수행

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

        {

               //두 수 모두 나누어떨어지면 max대체

               if ((num01 % i == 0) && (num02 % i == 0))

               {

                       max = i;

               }

        }

        return max;

}

}

 //유클리드 호제법_반복문

int Algorithm::GreatestCommonDivisor(int num01, int num02)

{

        int remainder;

        while (num02)

        {

               remainder = num01 % num02;

               num01 = num02;                

               num02 = remainder;

        }

        return num01;

void BinarySearchTree::Insert(int key)

{

        //트리가 비어있다면 루트 생성

        if (IsEmpty())

        {

               m_root->Right = new NODE(key);

               return;

        }

        NODE* parent = m_root;        //부모 노드

        NODE* node = m_root->Right;   //현재 탐색 노드    

        //입력 가능한 곳 검색

        do

        {

               //중복된 키 값은 입력 불가

               if (node->Key == key)

                       return;

               parent = node;

               node = (key < parent->Key) ? parent->Left : parent->Right;

        } while (node != NULL);

        //새 노드 생성

        node = new NODE(key);

        //부모보다 작으면 왼쪽

        if (key < parent->Key)

               parent->Left = node;

        //부모보다 크면 오른쪽

        else

               parent->Right = node;

}

//자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

//자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

void BinarySearchTree::Delete(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return;

        NODE* parent = m_root;          //부모 노드

        NODE* node = m_root->Right;     //자식 노드

        NODE* deleteNode;               //삭제 노드

        //검색

        do

        {

               if (node->Key == key)   //노드를 찾았다면 중지

                       break;

               //현재 노드를 부모 노드로

               parent = node;

               //다음 탐색 노드 설정

               node = (parent->Key > key) ? parent->Left : parent->Right;

        } while (node != NULL);

        //삭제할 노드가 없다면 중지

        if (node == NULL)

               return;

        //삭제할 노드 저장

        deleteNode = node;

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

        //자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

        //자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

        //노드 삭제

        delete deleteNode;

        deleteNode = NULL;

}

#pragma once

class BinarySearchTree

{

private:

        typedef struct _Node

        {

               _Node(int key)

               {

                       Key = key;

                       Left = NULL;

                       Right = NULL;

               }

               int Key;

               struct _Node *Left;

               struct _Node *Right;

        }NODE;

private:

        NODE *m_root;

public:

        BinarySearchTree();

        ~BinarySearchTree();

        void Insert(int);

        NODE* Search(int);

        void Delete(int);

        void Print();

        bool IsEmpty();

        void Clear();

private:

        void Preorder(NODE*);

        void PrintNode(NODE*);

        void Clear(NODE*);

};

#include "stdafx.h"

#include "BinarySearchTree.h"

BinarySearchTree::BinarySearchTree()

{

        //루트 생성(실질적인 루트가 아님)

        //m_root->Right가 진짜 루트

        m_root = new NODE(-1);  

}

BinarySearchTree::~BinarySearchTree()

{

        Clear();

        delete m_root;

        m_root = NULL;

}

void BinarySearchTree::Insert(int key)

{

        //트리가 비어있다면 루트에 입력

        if (IsEmpty())

        {

               m_root->Right = new NODE(key);

               return;

        }

        NODE* parent = m_root;

        NODE* node = m_root->Right;

        //입력 가능한 곳 검색

        do

        {

               //중복된 키 값은 입력 불가

               if (node->Key == key)

                       return;

               parent = node;

               node = (key < parent->Key) ? parent->Left : parent->Right;

        } while (node != NULL);

        //새 노드 생성

        node = new NODE(key);

        //부모보다 작으면 왼쪽

        if (key < parent->Key)

               parent->Left = node;

        //부모보다 크면 오른쪽

        else

               parent->Right = node;

}

BinarySearchTree::NODE* BinarySearchTree::Search(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return NULL;

        NODE* node = m_root->Right;

        while (node != NULL)

        {

               if (node->Key == key)

                       return node;

               node = (node->Key > key) ? node->Left : node->Right;

        }

        return NULL;

}

void BinarySearchTree::Delete(int key)

{

        //트리가 비어있다면 중지

        if (IsEmpty())

               return;

        NODE* parent = m_root;          //부모 노드

        NODE* node = m_root->Right;      //자식 노드

        NODE* deleteNode;                      //삭제 노드

        //검색

        do

        {

               if (node->Key == key)   //노드를 찾았다면 중지

                       break;

               //현재 노드를 부모 노드로

               parent = node;

               //다음 탐색 노드 설정

               node = (parent->Key > key) ? parent->Left : parent->Right;

        } while (node != NULL);

        //삭제할 노드가 없다면 중지

        if (node == NULL)

               return;

        //삭제할 노드 저장

        deleteNode = node;

        //자식이 없는 노드 삭제

        if (deleteNode->Left == NULL && deleteNode->Right == NULL)

        {

               if (parent->Key > key)

                       parent->Left = NULL;    //왼쪽 노드 삭제

               else

                       parent->Right = NULL;   //오른쪽 노드 삭제

        }

        //자식이 한쪽만 있는 노드 삭제

        else if (deleteNode->Left == NULL || deleteNode->Right == NULL)

        {

               //삭제노드의 자식 확인

               node = deleteNode->Left != NULL ? deleteNode->Left : deleteNode->Right;

               //삭제노드 위치에 삭제노드의 자식을 위치

               if (parent->Key > key)

                       parent->Left = node;   

               else

                       parent->Right = node;  

        }

        //자식이 양쪽 다 있는 노드 삭제

        //삭제할 노드의 왼쪽 자식 중 가장 큰 노드를 찾아

        //삭제할 노드의 위치에 둔다.

        else

        {             

               parent = deleteNode;            //최대값 노드의 부모 노드

               node = parent->Left;            //최대값 노드

               //왼쪽 자식 중 가장 큰 노드 찾기

               while (node->Right != NULL)

               {

                       parent = node;

                       node = node->Right;

               }

               //왼쪽에서 가장 큰 노드가 자식이 있다면

               if (node->Left != NULL)

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if(parent->Left == node)

                              parent->Left = node->Left;

                       else

                              parent->Right = node->Left;

               }

               //왼쪽에서 가장 큰 노드가 자식이 없다면

               else

               {

                       //최대 노드가 삭제할 노드의 왼쪽자식 노드라면

                       if (parent->Left == node)

                              parent->Left = NULL;

                       else

                              parent->Right = NULL;

               }

               //삭제할 노드의 데이터를 위에서 찾은 최대값으로

               deleteNode->Key = node->Key;

               //최대값 노드를 삭제 노드로

               deleteNode = node;

        }

        //노드 삭제

        delete deleteNode;

        deleteNode = NULL;

}

void BinarySearchTree::Print()

{

        if (IsEmpty())

        {

               printf("트리 비어 있음\n");

               return;

        }

        printf("전위순회");

        Preorder(m_root->Right);

        printf("\n");

}

bool BinarySearchTree::IsEmpty()

{

        if (m_root->Right == NULL)

               return true;

        else

               return false;

}

void BinarySearchTree::Clear()

{

        if (IsEmpty())

               return;

        Clear(m_root->Right);

        m_root->Right = NULL;

}

void BinarySearchTree::Preorder(NODE *node)

{

        if (node == NULL)

               return;

        //자신을 출력하고

        PrintNode(node);

        //왼쪽 방문

        Preorder(node->Left);

        //마지막으로 오른쪽 방문

        Preorder(node->Right);

}

//노드 데이터 프린트

void BinarySearchTree::PrintNode(NODE* node)

{

        printf(" -> K:%d", node->Key);

}

void BinarySearchTree::Clear(NODE *node)

{

        if (node == NULL)

               return;

        Clear(node->Left);

        Clear(node->Right);

        node->Left = NULL;

        node->Right = NULL;

        delete node;

        node = NULL;

}

//힙 정렬

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

}

//삽입

void Heap::Insert(int data)

{

        //힙이 가득 찼는지 확인

        if (IsFull())

               return;

        //가장 뒷쪽에 데이터 삽입

        m_Heap[m_Last] = data;

        //처음 삽입된 데이터가 아니라면, 업힙 수행

        if (IsEmpty() == false)

               UpHeap(m_Last);

        //last를 뒤로 한칸 밀어냄

        m_Last++;

}

//데이터를 위로 밀어냄

void Heap::UpHeap(int index)

{

        //현재 데이터의 부모 데이터

        int parent = PARENT(index);

        //최대 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        while (m_Heap[parent] < m_Heap[index])

        {

               //부모와 자신의 위치 교환

               SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

               index = parent;                           //위치

               //현재 위치에서 부모 위치 계산                                                               

               parent = PARENT(index);

        }

        //최소 힙

        //자신보다 더 작은 부모를 찾을때까지 반복

        //while (m_Heap[parent] > m_Heap[index])

        //{

        //      //부모와 자신의 위치 교환

        //      SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

        //      index = parent;                           //위치

        //      //현재 위치에서 부모 위치 계산

        //      parent = PARENT(index);

        //}

}

//출력(혹은 삭제)

int Heap::Get(void)

{

        //힙이 비었으면 수행 안함

        if (IsEmpty())

               return -999999;

        //리턴할 데이터 저장, ROOT = 0 <= 즉, 첫번째 데이터

        int data = m_Heap[ROOT];

        //가장 마지막에 위치함 데이터를 첫번째 위치로 이동

        m_Heap[ROOT] = m_Heap[--m_Last];

        //다운 힙 수행

        DownHeap(ROOT);

        return data;

}

//데이터를 아래로 밀어냄

void Heap::DownHeap(int index)

{

        //위치를 교환할 자식의 위치

        int child = 0;

        //왼쪽 자식

        int left = LEFT(index);

        //오른쪽 자식의 위치

        int right = RIGHT(index);

        //최대 힙

        while (left < m_Last)

        {

               //오른쪽 자식이 있다면, 좌우 자식을 비교해 큰 자식을 고름

               if (right < m_Last)

                       child = m_Heap[left] > m_Heap[right] ? left : right;

               else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

                       child = left;

               //자식들 중 큰 수와 비교해, 밀어내릴 대상이 더 크다면 반복 종료

               if (m_Heap[index] >= m_Heap[child])

                       break;

               //자식과 대상을 교환

               SWAP(int, m_Heap[index], m_Heap[child]);

               //자식의 위치를 현재 위치로

               index = child;

               left = LEFT(index);             //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

        }

        //최소 힙

        //while (left < m_Last)

        //{

        //      //오른쪽 자식이 있다면, 좌우 자식을 비교해 작은 자식을 고름

        //      if (right < m_Last)

        //             child = m_Heap[left] < m_Heap[right] ? left : right;

        //      else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

        //             child = left;

        //      //자식들 중 작은 수와 비교해, 밀어내릴 대상이 더 작다면 반복 종료

        //      if (m_Heap[index] <= m_Heap[child])

        //             break;

        //      //자식과 대상을 교환

        //      SWAP(int, m_Heap[index], m_Heap[child]);

        //      //자식의 위치를 현재 위치로

        //      index = child;

        //      left = LEFT(index);             //왼쪽 자식 위치

        //      right = RIGHT(index);   //오른쪽 자식 위치

        //}

}

#pragma once

//매크로 함수들

#define ROOT 0

#define PARENT(n) (n-1)/2  //부모 위치

#define LEFT(n) 2*n + 1    //왼쪽 자식 위치

#define RIGHT(n) 2*n + 2   //오른쪽 자식 위치

//교환

#define SWAP(type, a, b) do{ \

    type temp = a;      \

    a = b;                     \

    b = temp;           \

}while(false)

class Heap

{

public:

        Heap();

        Heap(int size);

        ~Heap();

private:

        int *m_Heap;            //데이터들 저장할 공간

        int m_Last;             //현재 마지막 자료의 위치 + 1(빈 위치)

        int m_Size;             //최대 사이즈

public:

        bool IsEmpty(void);     //힙이 비었는지 확인

        bool IsFull(void);      //힙이 가득 찼는지 확인

        void Insert(int);       //삽입

        int  Get(void);         //데이터 수령

        void Print(void);       //프린트

        void Resize(int size);   //배열 크기 다시설정

        void Clear();            //다시 사용가능한 상태로

        void Reset();            //다시 사용가능한 상태로

private:

        void UpHeap(int);        //업힙 : 데이터를 위로 밀어냄

        void DownHeap(int);      //다운힙 : 데이터를 아래로 밀어냄

        void SetSize(int size);  //사이즈 지정

};

#include "stdafx.h"

#include "Heap.h"

Heap::Heap()

{

        Reset();

        SetSize(10);

}

Heap::Heap(int size)

{

        Reset();

        SetSize(size);

}

Heap::~Heap()

{

        Clear();

}

//힙이 비었는지 확인

bool Heap::IsEmpty(void)

{

        //last가 0이면 데이터가 없음

        if (m_Last == 0)

               return true;

        else

               return false;

}

//힙이 가득 찼는지 확인

bool Heap::IsFull(void)

{

        //last와 최대크기가 같으면, 가득찬 것

        if (m_Last == m_Size)

               return true;

        else

               return false;

}

//삽입

void Heap::Insert(int data)

{

        //힙이 가득 찼는지 확인

        if (IsFull())

               return;

        //가장 뒷쪽에 데이터 삽입

        m_Heap[m_Last] = data;

        //처음 삽입된 데이터가 아니라면, 업힙 수행

        if (IsEmpty() == false)

               UpHeap(m_Last);

        //last를 뒤로 한칸 밀어냄

        m_Last++;

}

//데이터 수령

int Heap::Get(void)

{

        //힙이 비었으면 수행 안함

        if (IsEmpty())

               return -999999;

        //리턴할 데이터 저장, ROOT = 0 <= 즉, 첫번째 데이터

        int data = m_Heap[ROOT];

        //가장 마지막에 위치함 데이터를 첫번째 위치로 이동

        m_Heap[ROOT] = m_Heap[--m_Last];

        //다운 힙 수행

        DownHeap(ROOT);

        return data;

}

//데이터를 위로 밀어냄

void Heap::UpHeap(int index)

{

        //현재 데이터의 부모 데이터

        int parent = PARENT(index);

        //최대 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        while (m_Heap[parent] < m_Heap[index])

        {

               //부모와 자신의 위치 교환

               SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

               index = parent;                                                       //위치

                                                                                                   //현재 위치에서 부모 위치 계산                                                               

               parent = PARENT(index);

        }

        //최소 힙

        ////자신보다 더 큰 부모를 찾을때까지 반복

        //while (m_Heap[parent] > m_Heap[index])

        //{

        //      //부모와 자신의 위치 교환

        //      SWAP(int, m_Heap[parent], m_Heap[index]); //데이터

        //      index = parent;                                                       //위치

        //                                                                                          //현재 위치에서 부모 위치 계산                                                               

        //      parent = PARENT(index);

        //}

}

//데이터를 아래로 밀어냄

void Heap::DownHeap(int index)

{

        //위치를 교환할 자식의 위치

        int child = 0;

        //왼쪽 자식

        int left = LEFT(index);

        //오른쪽 자식의 위치

        int right = RIGHT(index);

        //최대 힙

        while (left < m_Last)

        {

               //left = LEFT(index);           //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

                                                             //오른쪽 자식이 있다면, 좌우 자식을 비교해 큰 자식을 고름

               if (right < m_Last)

                       child = m_Heap[left] > m_Heap[right] ? left : right;

               else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

                       child = left;

               //자식들 중 큰 수와 비교해, 밀어내릴 대상이 더 크다면 반복 종료

               if (m_Heap[index] >= m_Heap[child])

                       break;

               //자식과 대상을 교환

               SWAP(int, m_Heap[index], m_Heap[child]);

               //자식의 위치를 현재 위치로

               index = child;

               left = LEFT(index);             //왼쪽 자식 위치

               right = RIGHT(index);   //오른쪽 자식 위치

        }

        //최소 힙

        //while (left < m_Last)

        //{

        //      //오른쪽 자식이 있다면, 좌우 자식을 비교해 작은 자식을 고름

        //      if (right < m_Last)

        //             child = m_Heap[left] < m_Heap[right] ? left : right;

        //      else //오른쪽 자식이 없다면, 왼쪽 자식을 선택

        //             child = left;

        //      //자식들 중 작은 수와 비교해, 밀어내릴 대상이 더 작다면 반복 종료

        //      if (m_Heap[index] <= m_Heap[child])

        //             break;

        //      //자식과 대상을 교환

        //      SWAP(int, m_Heap[index], m_Heap[child]);

        //      //자식의 위치를 현재 위치로

        //      index = child;

        //      left = LEFT(index);             //왼쪽 자식 위치

        //      right = RIGHT(index);   //오른쪽 자식 위치

        //}

}

void Heap::Print(void)

{

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

               printf("%d ", m_Heap[i]);

        printf("\n");

}

// 배열 크기 다시설정

void Heap::Resize(int size)

{

        Clear();

        SetSize(size);

        Reset();

}

//데이터 삭제

void Heap::Clear()

{

        delete[] m_Heap;

        m_Heap = NULL;

}

//다시 사용가능한 상태로

void Heap::Reset()

{

        m_Last = 0;

}

//배열 크기 지정

void Heap::SetSize(int size)

{

        m_Size = size;

        m_Heap = new int[m_Size];

}

//병합 정렬

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

}