題目:

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

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
#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

          ~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;
}

解釋與詳細介紹

第一部分:quicksort

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//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
     }
}

在quicksort()的部份我們直接定義left,right與pivot的判斷值(同day26所述)

第二部分:main()函式

main()的整體如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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位
}

在main()函式中，我們首先定義了size(arr大小)與mode(三種sort模式)的兩變數。並先運用srand與time()來設定亂數seed。

再來我們設置了一個Sorting型別的變數answer，來代表結果陣列。再來我們定義了

1
2
3
4
5
6
7
8
9
10
11
//第一part初始設定
     LARGE_INTEGER startTime, endTime, fre;
     QueryPerformanceFrequency(&fre);//取得CPU頻率
     //----------------分隔線---------------------
     //第二part:設置開始計算與結束計算程式時間的位置
     QueryPerformanceCounter(&startTime);//開始啟用位置
     QueryPerformanceCounter(&endTime);// 時間結束的地方
     //----------------分隔線---------------------
     //第三part:是輸出程式執行總時間
     times=(double)(endTime.QuadPart-startTime.QuadPart)/fre.QuadPart;
     cout << fixed << setprecision(20) << times << "s" << endl;

這部分顯示了是如何用來取CPU頻率的設置，他以程式的clock cycle來計算時間更為精準。而我們需要先在程式開頭設定第一part，在愈計算程式前後要分別設置(part2)，而最後的輸出便是part3。

1
2
3
4
5
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;//定義陣列初始值

再來程式會先輸出”please enter your size of array.” ，讓使用者輸入arr大小(size)，並將此值設定為一動態陣列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];
          }
     }

再來將亂數值(範圍1~50000)塞入temp陣列中，而註解的部分是一些說明事項。而將temp[size]，也就是最大index的下一位值設為INT_MAX是為了避免i++超越整數最大值而設置的。而adTemp的index值會設置為temp的index+1，因為在mergesort執行時，我們會需要多一位元的空間存放pivot，因而需要做此設定。

1
2
3
cout << "Please enter mode of sort(1:Insert 2:Quick 3:Merge)" << endl;
      cin >> mode;
      cout << "The initial data: ";

再來終端機會跳出”Please enter mode of sort(1:Insert 2:Quick 3:Merge)”，讓使用者來輸入愈執行的sort種類。我們用連續三個if來判斷之。

1
2
3
4
5
6
7
8
if(mode == 1)//insert
      {
          answer.eqPtr(temp);//存入陣列值
          answer.printAll(size);//輸出原數列
          answer.InsertSort(0,size);//insertionSort執行
          cout << "The sorting data: ";
          answer.printAll(size);//輸出執行後數列
      }

mode1的部分是insertionSort，我們會先將方才的temp的陣列值存入answer.eqPtr()中，並先輸出原數列，再對其執行InsertSort()，並輸出執行後結果。

1
2
3
4
5
6
7
8
if(mode == 2)//quick
      {
          answer.eqPtr(temp);
          answer.printAll(size);
          answer.QuickSort(0, size);
          cout << "The sorting data: ";
          answer.printAll(size);
      }

mode2的部分是quickSort，而他的執行順序同mode1，只是將InsertSort()換為QuickSort()。

1
2
3
4
5
6
7
8
if(mode == 3)//merge
      {
          answer.eqPtr(adTemp);
          answer.print(size);
          answer.MergeSort(adTemp,size);
          cout << "The sorting data: ";
          answer.print(size);
      }

mode3的部分是mergeSort，因為他的sorting需多出一位空間給pivot使用，所以我們為它特別設立adTemp代替Temp、print()代替printAll()，而兩前者皆多於後者一位置的記憶體空間。其他的執行順序同mode1,2，且將函式換為MergeSort()即可。

第三部分:print()與printAll()

1
2
3
4
5
6
7
8
void Sorting::print(int n)
{
     for (int i=0; i <= n;i++)//是
     {
          cout << setw(5) << ptr[i] << " ";
     }
     cout << endl;
}

接著我們接續講昨天在sorting中所令的print()和printAll()函式，兩者都是為了印出答案的函式，其中我們先介紹print()的部分。print()主要是用在印出index[0][n-1]，而print()則是index[0][n]，因為在mergesort執行時，我們會需要多一位元的空間存放pivot，因而需要做此設定。

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

可以看到兩者的差別僅在條件項的中<n與<=n，可視不同的sorting做印出的配合。理由如剛才所述(mergesort pivot)

第四部分:QuickSort()(mode 2)成果展示

https://ithelp.ithome.com.tw/upload/images/20220929/20151593XuLNSdHfcQ.png

今天提到auicksort與main()函式的部分，大家可以依據main函式的循序步驟對應整個程式的component(組件，即各個程式段予宣告函式)，也會更加了解這個程式的統合核心架構與順序。而merge與insert、quick在記憶體配置的不同也跟以前只要考慮程式執行的思維不太一樣，需就演算法的執行架構做專門的設定才會符合!那我們明天見囉~ଘ(੭ˊᵕˋ)੭* ੈ✩‧₊˚

參考資料:

https://www.796t.com/content/1546454534.html