C++/Fundamentals of Data Structures in C++(Horowitz)

C++ Fundamentals of Data Structures(C++ 자료구조론) 7.1 Sorting(정렬) 예제

꾸준함. 2017. 11. 7. 00:40

/*

Fast Verifications of two lists

리스트끼리의 비교(빠른 버젼)

*/

#include <iostream>

#include <ctime>

#include <cstdlib>

using namespace std;

 

//순차적 탐색

/*

template <class E, class K>

int SeqSearch(E *a, const int n, const K &k)

{

        int i;

        for (i = 1; i <= n && a[i] != k; i++);

        if (i > n)

               return 0;

        return i;

}

*/

 

//Verify2와 동일한 역할을 하는 함수

/*

void Verify1(Element *l1, Element *l2, const int n, const int m)

{

        bool *marked = new bool[m + 1];

        fill(marked + 1, marked + m + 1, false);

 

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

        {

               int j = SeqSearch(l2, m, l1[i]);

               if (j == 0)

                       cout << l1[i] << "not in l2" << endl;

               else

               {

                       if (!Compare(l1[i], l2[j]))

                              cout << "Discrepancy in " << l1[i] << endl;

                       marked[j] = true;

               }

        }

        for (ii = 1; i <= m; i++)

               if (!marked[i])

                       cout << l2[i] << "not in l1." << endl;

        delete[]marked;

}

*/

 

void Sort(int *arr, int length) //bubble sort

{

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

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

               {

                       if (arr[i] > arr[j])

                       {

                              int temp = arr[i];

                              arr[i] = arr[j];

                              arr[j] = temp;

                       }

               }

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

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

        cout << endl;

}

 

bool Compare(int n1, int n2)

{

        if (n1 == n2)

               return true;

        else

               return false;

}

 

void OutputRest(int *arr, int i, int n, int number)

{

        cout << number << "번째 리스트의 나머지 요소들: ";

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

               cout << arr[j] << " ";

        cout << endl;

}

 

//Element 클래스를 정의하고 Element 배열을 매개변수로 정의했어야했지만 간편하게 int 배열로 대체했다

void Verify2(int *l1, int *l2, const int n, const int m)

{

        cout << "정렬 후 리스트 출력" << endl;

        //오름차순 정렬

        cout << "1번째 리스트: ";

        Sort(l1, n);

        cout << "2번째 리스트: ";

        Sort(l2, m);

        int i = 0, j = 0;

        while ((i < n) && (j < m))

        {

               if (l1[i] < l2[j])

               {

                       cout << l1[i] << " 2번째 리스트에 없다" << endl;

                       i++;

               }

               else if (l1[i] > l2[j])

               {

                       cout << l2[j] << " 1번째 리스트에 없다" << endl;

                       j++;

               }

               else

               {

                       if (!Compare(l1[i], l2[j]))

                              cout << l1[i] << " " << l2[j] << "는 다른 요소이다" << endl;

                       else

                              cout << l1[i] << "는 두 리스트가 공통으로 갖고 있는 요소이다" << endl;

                       i++;

                       j++;

               }

        }

        //비교가 다 끝나고 남은 요소가 있다면 출력

        if (i < n)

               OutputRest(l1, i, n, 1); //i부터 n까지 출력

        else if (j < m)

               OutputRest(l2, j, m, 2); //j부터 m까지 출력

}

 

int main(void)

{

        int *arr1, *arr2;

        srand((unsigned)time(NULL));

        int length1 = rand() % 10 + 4, length2 = rand() % 8 + 3; //길이 랜덤

        arr1 = new int[length1];

        arr2 = new int[length2];

        cout << "정렬 전 리스트 출력" << endl;

        cout << "1번째 리스트: ";

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

        {

               arr1[i] = rand() % 50 + 1;

               cout << arr1[i] << " ";

        }

        cout << endl;

        cout << "2번째 리스트: ";

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

        {

               arr2[i] = rand() % 50 + 1;

               cout << arr2[i] << " ";

        }

        cout << endl;

        Verify2(arr1, arr2, length1, length2);

        return 0;

}



[참고] Fundamentals of Data Structures in C++(Horowitz, Sahni, Mehta) 원서


*영어로 적혀있는 문제를 제가 의역한 것이기 때문에 오역이 있을 수 있습니다. 양해 부탁드립니다.


반응형