C++로 쉽게 풀어쓴 자료구조 프로그래밍 프로젝트 13

/*

1)0에서 n 사이의 난수를 발생하여 배열에 저장하는 다음 함수를 구현하라

2)다양한 n 값에 대해 1번의 함수를 이용해 난수를 발생시키고 각 알고리즘으로 정렬하라.

  이 때 각 알고리즘의 실행시간을 측정하라.

*/

#include <iostream>

#include "MinHeap.h"

#include "CircularQueue.h"

#include <cstring>

#include <cstdlib>

#include <ctime>

#include <chrono> //시간 재기 위해

using namespace std;

 

#define MAX_SIZE 1024

 

static void PrintArray(int arr[], int n, char *str = "Array");

 

inline void swap(int &x, int &y)

{

        int temp = x;

        x = y;

        y = temp;

}

 

//선택정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void selectionSort(int A[], int n)

{

        for (int i = 0; i < n - 1; i++) //n-1번 반복

        {

               int least = i;

               for (int j = i + 1; j < n; j++) //최솟값 탐색

                       if (A[j] < A[least])

                              least = j;

               swap(A[i], A[least]);

        }

}

 

inline int ascend(int x, int y)

{

        return y - x; //오름차순

}

 

inline int descend(int x, int y)

{

        return x - y; //내림차순

}

 

void insertionSortFn(int A[], int n, int(*f)(int, int))

{

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

        {

               int key = A[i];

               int j;

               for (j = i - 1; j >= 0 && f(A[j], key) < 0; j--)

                       A[j + 1] = A[j];

               A[j + 1] = key;

        }

}

 

void bubbleSort(int A[], int n)

{

        for (int i = n - 1; i > 0; i--)

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

                       if (A[j] > A[j + 1])

                              swap(A[j], A[j + 1]);

}

 

//gap 만큼 떨어진 요소들을 삽입 정렬, 정렬의 범위는 first에서 last

static void sortGapInsertion(int A[], int first, int last, int gap)

{

        int i, j, key;

        for (i = first + gap;i <= last; i = i + gap)

        {

               key = A[i];

               for (j = i - gap; j >= first&&key < A[j]; j = j - gap)

                       A[j + gap] = A[j];

               A[j + gap] = key;

        }

}

 

//셸 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void shellSort(int A[], int n)

{

        for (int gap = n / 2; gap > 0; gap = gap / 2)

        {

               //PrintArray(A, n, "Shell....");

               if ((gap % 2) == 0)

                       gap++;

               for (int i = 0; i < gap; i++) //부분 리스트의 개수는 gap

                       sortGapInsertion(A, i, n - 1, gap);

        }

}

 

static void merge(int A[], int left, int mid, int right)

{

        int i, j, k = left, l; //k는 정렬된 리스트에 대한 인덱스

        static int sorted[MAX_SIZE];

        //분할 정렬된 A의 합병

        for (i = left, j = mid + 1; i <= mid&&j <= right; )

               sorted[k++] = (A[i] <= A[j]) ? A[i++] : A[j++];

        //한쪽에 남아있는 레코드의 일괄 복사

        if (i > mid)

               for (l = j;l <= right;l++, k++)

                       sorted[k] = A[l];

        else

               for (l = i; l <= mid; l++, k++)

                       sorted[k] = A[l];

        //배열 sorted[]의 리스트를 배열 A[]로 재복사

        for (l = left;l <= right;l++)

               A[l] = sorted[l];

}

 

//합병 정렬 알고리즘을 이용해 int 배열을 오름차순으로 정렬하는 함수

void mergeSort(int A[], int left, int right)

{

        if (left < right)

        {

               int mid = (left + right) / 2; //리스트의 균등 분할

               mergeSort(A, left, mid); //부분리스트 정렬

               mergeSort(A, mid + 1, right); //부분리스트 정렬

               merge(A, left, mid, right); //합병

        }

}

 

static int partition(int A[], int left, int right)

{

        int low = left;

        int high = right + 1;

        int pivot = A[left];

        do

        {

               do //왼쪽 리스트에서 피벗보다 큰 레코드 선택

               {

                       low++;

               } while (low <= right&&A[low] < pivot);

               do

               {

                       high--; // 오른쪽 리스트에서 피벗보다 작은 레코드 선택

               } while (high >= left &&A[high] > pivot);

               if (low < high) //선택된 두 레코드 교환

                       swap(A[low], A[high]);

        } while (low < high); //인덱스 i, j가 엇갈리지 않는 한 반복

 

        swap(A[left], A[high]); //인덱스 j가 가리키는 레코드와 피벗 교환

        return high;

}

 

 

void quickSort(int A[], int left, int right)

{

        if (left < right)

        {

               int q = partition(A, left, right); //좌우로 분할

               quickSort(A, left, q - 1);

               quickSort(A, q + 1, right);

        }

}

 

 

//랜덤함수를 이용하여 int 배열을 0~max-1의 값으로 무작위로 채우는 함수

static void initRandom(int list[], int n, int max = 100)

{

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

               list[i] = rand() % max;

}

 

//배열을 화면에 보기 좋게 출력하는 함수, 디폴트 매개변수 사용

static void PrintArray(int arr[], int n, char *str)

{

        cout << str << "= ";

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

               cout << arr[i] << " ";

        cout << endl;

}

 

int main(void)

{

        using namespace std::chrono;

 

        MinHeap minHeap;

        int length;

        high_resolution_clock::time_point t1, t2;

        duration<double> time_span; //시간 재기 위해

        int *list, *org;

        srand((unsigned)time(NULL));

        cout << "배열의 길이 >";

        cin >> length;

        list = new int[length];

        org = new int[length];

        initRandom(list, length, 9999);

        //PrintArray(list, length, "정렬 전 배열 ");

 

        memcpy(org, list, length * sizeof(int)); //정렬 전 배열복사

        t1 = high_resolution_clock::now();

        selectionSort(list, length);

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        //PrintArray(list, length, "Selection Sort ");

        cout << "SelectionSort 경과시간: " << time_span.count() << "초" << endl;

       

        memcpy(list, org, length * sizeof(int));

        t1 = high_resolution_clock::now();

        insertionSortFn(list, length, ascend);

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        //PrintArray(list, length, "Insertion Sort ");

        cout << "insertionSort 경과시간: " << time_span.count() << "초" << endl;

 

        memcpy(list, org, length * sizeof(int));

        t1 = high_resolution_clock::now();

        bubbleSort(list, length);

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        //PrintArray(list, length, "Bubble Sort ");

        cout << "bubbleSort 경과시간: " << time_span.count() << "초" << endl;

 

        memcpy(list, org, length * sizeof(int));

        t1 = high_resolution_clock::now();

        shellSort(list, length);

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        //PrintArray(list, length, "Shell Sort ");

        cout << "Shell Sort 경과시간: " << time_span.count() << "초" << endl;

 

        memcpy(list, org, length * sizeof(int));

        t1 = high_resolution_clock::now();

        mergeSort(list, 0, length - 1);

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        //PrintArray(list, length, "Merge Sort ");

        cout << "Merge Sort 경과시간: " << time_span.count() << "초" << endl;

 

        memcpy(list, org, length * sizeof(int));

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

               minHeap.insert(list[i]);

        t1 = high_resolution_clock::now();

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

               //cout << minHeap.remove().getKey() << " ";

               minHeap.remove().getKey();

        cout << endl;

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        cout << "HeapSort 경과시간: " << time_span.count() << "초" << endl;

 

        memcpy(list, org, length * sizeof(int));

        t1 = high_resolution_clock::now();

        quickSort(list, 0, length - 1);

        t2 = high_resolution_clock::now();

        time_span = duration_cast<duration<double>>(t2 - t1);

        //PrintArray(list, length, "Quick Sort ");

        cout << "QuickSort 경과시간: " << time_span.count() << "초" << endl;

        return 0;

}

[CircularQueue.h]

/*

원형 큐 프로그램

*/

#include <iostream>

#include <cstdlib>

using namespace std;

 

#define MAX_QUEUE_SIZE 100

 

inline void error(char *str)

{

        cout << str << endl;

        exit(1);

}

 

class CircularQueue

{

protected:

        int front; //첫 번째 요소 앞의 위치

        int rear; //마지막 요소 위치

        int data[MAX_QUEUE_SIZE]; //요소의 배열

public:

        CircularQueue()

        {

               front = rear = 0;

        }

        bool isEmpty()

        {

               return front == rear;

        }

        bool isFull()

        {

               return (rear + 1) % MAX_QUEUE_SIZE == front;

        }

        void enqueue(int val) //큐에 삽입

        {

               if (isFull())

                       error("error:큐가 포화상태입니다\n");

               else

               {

                       rear = (rear + 1) % MAX_QUEUE_SIZE;

                       data[rear] = val;

               }

        }

        int dequeue() //첫 항목을 큐에서 빼서 반환

        {

               if (isEmpty())

                       error("Error: 큐가 공백상태입니다\n");

               else

               {

                       front = (front + 1) % MAX_QUEUE_SIZE;

                       return data[front];

               }

        }

        int peek() //첫 항목을 큐에서 빼지 않고 반환

        {

               if (isEmpty())

                       error("Error: 큐가 공백상태입니다\n");

               else

                       return data[(front + 1) % MAX_QUEUE_SIZE];

        }

        void display() //큐의 모든 내용을 순서대로 출력

        {

               cout << "큐의 내용: ";

               int maxi = (front < rear) ? rear : rear + MAX_QUEUE_SIZE;

               for (int i = front + 1; i <= maxi; i++)

                       cout << data[i%MAX_QUEUE_SIZE] << " ";

               cout << endl;

        }

};

[HeapNode.h]

/*

힙을 위한 노드 클래스 구현

*/

#include <iostream>

#include <iomanip>

using namespace std;

 

class HeapNode

{

private:

        int key;

public:

        HeapNode(int k = 0) :key(k)

        {

        }

        void setKey(int k)

        {

               key = k;

        }

        int getKey()

        {

               return key;

        }

        void display()

        {

               cout << key << "\t";

        }

};

[MinHeap.h]

/*

허프만 코딩을 위한 최소 힙 클래스

*/

#include "HeapNode.h"

#define MAX_ELEMENT 200

 

class MinHeap

{

private:

        HeapNode node[MAX_ELEMENT]; //요소의 배열

        int size; //힙의 현재 요소의 개수

public:

        MinHeap() :size(0)

        {

        }

        bool isEmpty()

        {

               return size == 0;

        }

        bool isFull()

        {

               return size == MAX_ELEMENT - 1;

        }

        HeapNode &getParent(int i)

        {

               return node[i / 2];

        }

        HeapNode &getLeft(int i)

        {

               return node[i * 2];

        }

        HeapNode &getRight(int i)

        {

               return node[i * 2 + 1];

        }

        //삽입 함수

        void insert(int key)

        {

               if (isFull())

                       return;

               int i = ++size;

               while (i != 1 && key < getParent(i).getKey())

               {

                       node[i] = getParent(i);

                       i /= 2;

               }

               node[i].setKey(key);

        }

        //삭제 함수

        HeapNode remove()

        {

               if (isEmpty())

                       return NULL;

               HeapNode root = node[1];

               HeapNode last = node[size--];

               int parent = 1;

               int child = 2;

               while (child <= size)

               {

                       if (child<size && getLeft(parent).getKey()>getRight(parent).getKey())

                              child++;

                       if (last.getKey() <= node[child].getKey())

                              break;

                       node[parent] = node[child];

                       parent = child;

                       child *= 2;

               }

               node[parent] = last;

               return root;

        }

};

 

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] C++로 쉽게 풀어쓴 자료구조, http://www.cplusplus.com/reference/chrono/high_resolution_clock/now/

*정렬된 배열을 확인하고 싶으시다면 주석으로 처리된 PrintArray를 출력해보시면 됩니다.

*링크를 참고하여 수행시간을 확인했습니다