iT邦幫忙

2022 iThome 鐵人賽
DAY 29
0
自我挑戰組

C++30日挑戰之旅系列 第 29 篇

DAY29 三種sorting實作-程式介紹(下)

14th鐵人賽
471 瀏覽

  • 分享至 

  • xImage
    •  

題目:

請撰寫程式，依照使用者打的數量自動生成對應個介於1~50000的隨機數字，並在程式中用三種mode對應三種排序方式(insertionSort, mergeSort, 和quickSort)依據使用者輸入的模式去印出初始陣列與依照對應模式的排序法所印出的排序後數列與其運算時間。

解法

#include<iostream>
#include<cstdlib>//srand()
#include<ctime>//time函式
#include<iomanip>//setw()，空格函式
#include<windows.h>//cpu頻率
// #include<algorithm>//swap()函式
using namespace std;

class Sorting
// sorting類別包含三個sort
{
     public:
          void InsertSort(int *initList,const int n);
          void MergeSort(int *initList, const int n);
          void QuickSort(const int left, const int right);

          Sorting(){ }//default函式，當呼叫一次sort型別就會construct一次

          void print(int n);//此print是從1~n，是針對tree的情況下使用
          // tree不會用到arr[0]方便對照
          void printAll(int n);//printAll是從0~n+1

          ~Sorting(); //destructor，解構

          void eqPtr(int *a)//把main裡面的pointer給class裡，讓所有sorting都可以使用
          {
               ptr = a;
          }

     private:
          int *ptr;
          void swap(int &a,int &b);
          void merge(int *initList, int *result, const int L, const int m, const int n);
          void MergePass(int *initList, int *result, const int n, const int subSize);
};

int main()
{
     int size;// array size
     int mode;//sorting 的模式
     srand(time(0));//宣告亂數

     Sorting answer;
     LARGE_INTEGER startTime, endTime, fre;
     QueryPerformanceFrequency(&fre);//取得CPU頻率
     double times;

     cout << "please enter your size of array." << endl;
     cin >> size;
     int *temp = new int[size + 1];
     int *adTemp = new int[size + 1];
     adTemp[0] = 5;

     for (int i = 0; i < size;i++)
     {
          temp[i]=(long long)((double)(rand()*49999)/RAND_MAX)+1;
          // (long long)用來好取後20位數
          // 不能用rand%50000,因為只有到32767
          //temp[i] = randint(1, 50000);
     }

     temp[size] = INT_MAX; //in order not to out of range
    // 將暫存器的最後一個位置=int裡的最大值=2^31-1
    //避免i++超過array size

     for (int j = 0; j < size;j++)
     {
          adTemp[j + 1] = temp[j];
     }

      cout << "Please enter mode of sort(1:Insert 2:Quick 3:Merge)" << endl;
      cin >> mode;
      cout << "The initial data: ";
      QueryPerformanceCounter(&startTime);//開始啟用位置
      
      if(mode == 1)//insert
      {
          answer.eqPtr(temp);
          answer.printAll(size);
          answer.InsertSort(0,size);
          cout << "The sorting data: ";
          answer.printAll(size);
      }

      if(mode == 2)//quick
      {
          answer.eqPtr(temp);
          answer.printAll(size);
          answer.QuickSort(0, size);
          cout << "The sorting data: ";
          answer.printAll(size);
      }

      if(mode == 3)//merge
      {
          answer.eqPtr(adTemp);
          answer.print(size);
          answer.MergeSort(adTemp,size);
          cout << "The sorting data: ";
          answer.print(size);
      }

     QueryPerformanceCounter(&endTime);// 時間結束的地方
     times=(double)(endTime.QuadPart-startTime.QuadPart)/fre.QuadPart;
     cout << fixed << setprecision(20) << times << "s" << endl;
    // fixed 是小數點後，setprecision(20)是20位
}

void Sorting::print(int n)
{
     for (int i=0; i <= n;i++)
     {
          cout << setw(5) << ptr[i] << " ";
     }
     cout << endl;
}

//自己定義swap函式
void Sorting::swap(int &a,int &b)
{
     int temp = a;
     a = b;
     b=temp;
}

//解構式
Sorting::~Sorting()
{
     delete[]ptr;
}

//Insert Sort:
void Sorting::InsertSort(int *initList,const int size)
{
     for (int i = 1; i < size;i++)
     {
          int key = ptr[i];
          int j = i - 1;
          while(key < ptr[j] && j >= 0)
          // 這裡的j記得是>=0
          {
               ptr[j + 1] = ptr[j];
               j--;
          }

          ptr[j + 1] = key;
     }
}

//Quick Sort:
void Sorting::QuickSort(const int left,const int right)
{
     if(left<right)
     {
          int i=left,
            // j不會小於array size因為碰到樞紐就會break(樞紐從arr[0]開始)
			j=right+1,
            // j設為最大值(自己定義的int_max)，避免i超過array size
			pivot=ptr[left];
            // 樞紐設為第一位
          do{
               do i++; while (ptr[i] < pivot);
               //選左邊比樞紐大的
               do j--; while (ptr[j] > pivot);
               //選右邊比樞紐小的
               if(i<j) {swap(ptr[i], ptr[j]);}
          } while (i < j);
          swap(ptr[left], ptr[j]);

          QuickSort(left, j - 1);//樞紐左邊的QuickSort
          QuickSort(j + 1, right);//樞紐右邊的QuickSort
     }
}

//Merge Sort:
// merge:實作2個list合併
void Sorting::merge (int *initList,int *result,const int L,const int m,const int n )
//m=中間
{
     int i1, i2, iResult;//兩個數列分為前半後半，iresult是位置
     for (i1 = L, iResult = L, i2 = m + 1; i1 <= m && i2 <= n;iResult++)
     {
          if(initList[i1]<=initList[i2])//較大的放進result且將位置往後移
          {
               result[iResult] = initList[i1];
               i1++;
          }
          else
          {
               result[iResult] = initList[i2];
               i2++;
          }
     }//上述迴圈結束會有(左或右)一端數列剩下

     if(i1<=m)//copy data避免資料消失，m=中間
     {
          for (; i1 <= m;i1++)
          {
               result[iResult] = initList[i1];
               ++iResult;
          }
     }
     else if(i2<=n)//copy data避免資料消失，n=最右邊
     {
          for (; i2 <= n;i2++)
          {
               result[iResult] = initList[i2];
               ++iResult;
          }
     }
     //上述兩個if中只會有一個成立

}

// mergepass:幫merge計算中間和尾巴
void Sorting::MergePass (int *initList,int *result,const int n, const int subSize)
{
     int i;
     for (i = 1; i <= n - 2 * subSize + 1;i+=2*subSize)
     {
          merge(initList, result, i, i + subSize - 1, i + 2 * subSize - 1);
          // 一倍mergesize跟兩倍mergesize，sub-1是因為剛剛arr[+1]
     }

     if((i+subSize-1)<n)
     {
          merge(initList, result, i, i+subSize - 1, n);
     }
     else
     {
          for (int j = i; j <= n;j++)
          {
               result[j] = initList[j];
          }
     }
}

// mergesort是呼叫函式
// mergesort -> mergepath->merge
void Sorting::MergeSort(int *initList,const int n)
{
     int *temp = new int[n + 1];
     for (int L = 1; L < n; L *= 2)
     {
          MergePass(initList, temp, n, L);//選mergePass的範圍
          L *= 2;//範圍conquer*2
          MergePass(temp, initList, n, L);
     }
     ptr = initList;
     delete[] temp;
}
//Merge Sort End


void Sorting::printAll(int n)
{
     for (int i = 0; i < n;i++)
          cout << setw(5) << ptr[i] << " ";
     cout<<endl;
}

解釋與詳細介紹

第一部分:mergeSort

void Sorting::merge (int *initList,int *result,const int L,const int m,const int n )
//m=中間
{
     int i1, i2, iResult;//兩個數列分為前半後半，iresult是位置
     for (i1 = L, iResult = L, i2 = m + 1; i1 <= m && i2 <= n;iResult++)
     {
          if(initList[i1]<=initList[i2])//較大的放進result且將位置往後移
          {
               result[iResult] = initList[i1];
               i1++;
          }
          else
          {
               result[iResult] = initList[i2];
               i2++;
          }
     }//上述迴圈結束會有(左或右)一端數列剩下

     if(i1<=m)//copy data避免資料消失，m=中間
     {
          for (; i1 <= m;i1++)
          {
               result[iResult] = initList[i1];
               ++iResult;
          }
     }
     else if(i2<=n)//copy data避免資料消失，n=最右邊
     {
          for (; i2 <= n;i2++)
          {
               result[iResult] = initList[i2];
               ++iResult;
          }
     }
     //上述兩個if中只會有一個成立

}

// mergepass:幫merge計算中間和尾巴
void Sorting::MergePass (int *initList,int *result,const int n, const int subSize)
{
     int i;
     for (i = 1; i <= n - 2 * subSize + 1;i+=2*subSize)
     {
          merge(initList, result, i, i + subSize - 1, i + 2 * subSize - 1);
          // 一倍mergesize跟兩倍mergesize，sub-1是因為剛剛arr[+1]
     }

     if((i+subSize-1)<n)
     {
          merge(initList, result, i, i+subSize - 1, n);
     }
     else
     {
          for (int j = i; j <= n;j++)
          {
               result[j] = initList[j];
          }
     }
}

// mergesort是呼叫函式
// mergesort -> mergepath->merge
void Sorting::MergeSort(int *initList,const int n)
{
     int *temp = new int[n + 1];
     for (int L = 1; L < n; L *= 2)
     {
          MergePass(initList, temp, n, L);//選mergePass的範圍
          L *= 2;//範圍conquer*2
          MergePass(temp, initList, n, L);
     }
     ptr = initList;
     delete[] temp;
}
//Merge Sort End

其中merge()函式的部分如下

void Sorting::merge (int *initList,int *result,const int L,const int m,const int n )
//m=中間
{
     int i1, i2, iResult;//兩個數列分為前半後半，iresult是位置
     for (i1 = L, iResult = L, i2 = m + 1; i1 <= m && i2 <= n;iResult++)
     {
          if(initList[i1]<=initList[i2])//較大的放進result且將位置往後移
          {
               result[iResult] = initList[i1];
               i1++;
          }
          else
          {
               result[iResult] = initList[i2];
               i2++;
          }
     }//上述迴圈結束會有(左或右)一端數列剩下

     if(i1<=m)//copy data避免資料消失，m=中間
     {
          for (; i1 <= m;i1++)
          {
               result[iResult] = initList[i1];
               ++iResult;
          }
     }
     else if(i2<=n)//copy data避免資料消失，n=最右邊
     {
          for (; i2 <= n;i2++)
          {
               result[iResult] = initList[i2];
               ++iResult;
          }
     }
     //上述兩個if中只會有一個成立

}

程式中我們先將陣列分為前後段，並在for迴圈內寫出兩個條件段，進行兩段數列自前項到後項index得值一一比較並排序放入result[]陣列中。而下一個if判斷條件copy data的部分(因為陣列可能不剛好為偶數)。

// mergepass:幫merge計算中間和尾巴
void Sorting::MergePass (int *initList,int *result,const int n, const int subSize)
{
     int i;
     for (i = 1; i <= n - 2 * subSize + 1;i+=2*subSize)
     {
          merge(initList, result, i, i + subSize - 1, i + 2 * subSize - 1);
          // 一倍mergesize跟兩倍mergesize，sub-1是因為剛剛arr[+1]
     }

     if((i+subSize-1)<n)
     {
          merge(initList, result, i, i+subSize - 1, n);
     }
     else
     {
          for (int j = i; j <= n;j++)
          {
               result[j] = initList[j];
          }
     }
}

在mergePass()的部分是為了要為陣列分出段落而定的函式。

void Sorting::MergeSort(int *initList,const int n)
{
     int *temp = new int[n + 1];
     for (int L = 1; L < n; L *= 2)
     {
          MergePass(initList, temp, n, L);//選mergePass的範圍
          L *= 2;//範圍conquer*2
          MergePass(temp, initList, n, L);
     }
     ptr = initList;
     delete[] temp;
}

mergeSort()就是結合兩者而定的函式。

第二部分:成果展示

https://ithelp.ithome.com.tw/upload/images/20220930/20151593OkP2JQcQzR.jpg

那我們明天見囉(｡•ㅅ•｡)♡


上一篇
DAY28 三種sorting實作-程式介紹(中)
下一篇
DAY30 三種sorting實作-效能比對
系列文
C++30日挑戰之旅 共 43 篇
  1. 39
    【WIDE LAB紀錄 Day9】 先讓我們看那神奇的工具：Clockify!
  2. 40
    【WIDE LAB紀錄 Day10】Flutter Widgets積木疊疊樂!
  3. 41
    【開學挑戰系列】DAY1
  4. 42
    【開學挑戰系列】DAY2
  5. 43
    番外篇: Chat GPT應用---通訊系統研究
完整目錄
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言
iThome鐵人賽
參賽組數
1064 組
團體組數
40 組
累計文章數
22200 篇
完賽人數
602 人
iT+看影片追技術 看影片追技術 看更多
熱門tag 看更多
15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react vue.js
熱門問題
熱門回答
熱門文章
IT邦幫忙