煎餅排序
煎餅排序是一種基於反轉的排序演算法。它是基於現實生活中的問題，即藉助鏟子在盤子上類似於攤煎餅。它的名字來源於演算法中使用的翻轉操作，類似於翻轉煎餅。與大多數排序演算法試圖最小化執行排序所需的比較次數不同，它試圖以最小的反轉次數對陣列進行排序。就像選擇排序一樣，它也將最大元素放在最後。
煎餅排序演算法
假設我們有一個包含 n 元素的未排序陣列 A[]。
PancakeSort()
-
初始化未排序子陣列的大小為
curr = n-1，並迭代減少其大小1。 -
查詢未排序子陣列中最大元素
mi的索引。 -
使用
flip(A,mi)翻轉A[0, ... , mi]，將最大元素A[i]移動到索引0處。 -
使用
flip(A,i)將最大元素A[i]移動到正確的位置，翻轉A[0, ... , i]。
Flip()
-
將第一個索引
f的元素與最後一個索引e的元素互換。 -
增加
f，減少e。 -
重複以上步驟，直到
f <= e。
煎餅排序示例
假設我們有一個陣列：(3, 5, 2, 1, 7, 6, 4)。我們將使用煎餅排序演算法對其進行排序。
- 第一次迭代
mi=4，curr=7
| 翻轉(mi) | [7, 1, 2, 5, 3, 6, 4] |
| 翻轉(6) | [ 4, 6, 3, 5, 2, 1, 7] |
- 第二次迭代
mi=1，curr=6
| 翻轉(mi) | [6, 4, 3, 5, 2, 1, 7] |
| 翻轉(5) | [1, 2, 5, 3, 4, 6, 7] |
- 第三次迭代
mi=2，curr=5
| 翻轉(mi) | [5, 2, 1, 3, 4, 6, 7] |
| 翻轉(4) | [4, 3, 1, 2, 5, 6, 7] |
- 第四次迭代
mi=0，curr=4
| 翻轉(mi) | [4, 3, 1, 2, 5, 6, 7] |
| 翻轉(3) | [2, 1, 3, 4, 5, 6, 7] |
- 第五次迭代
mi=2，curr=3
| 翻轉(mi) | [3, 1, 2, 4, 5, 6, 7] |
| 翻轉(2) | [2, 1, 3, 4, 5, 6, 7] |
- 第六次迭代
mi=0，curr=2
| 翻轉(mi) | [2, 1, 3, 4, 5, 6, 7] |
| 翻轉(1) | [1, 2, 3, 4, 5, 6, 7] |
我們得到最終的排序陣列為 1，2，3，4，5，6，7。
煎餅排序演算法實現
#include <bits/stdc++.h>
using namespace std;
void flip(int arr[], int i) {
int temp, start = 0;
while (start < i) {
temp = arr[start];
arr[start] = arr[i];
arr[i] = temp;
start++;
i--;
}
}
int findMax(int arr[], int n) {
int mi = 0;
for (int i = 0; i < n; ++i)
if (arr[i] > arr[mi]) mi = i;
return mi;
}
void pancakeSort(int arr[], int n) {
for (int i = n; i > 1; i--) {
int mi = findMax(arr, i);
if (mi != i - 1) {
flip(arr, mi);
flip(arr, i - 1);
}
}
}
int main() {
int n = 6;
int arr[6] = {5, 3, 4, 2, 1, 6};
cout << "Input arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
pancakeSort(arr, n); // Sort elements in ascending order
cout << "Output arr: ";
for (int i = 0; i < n; i++) {
cout << arr[i] << " ";
}
cout << "\n";
}
煎餅排序演算法的複雜度
時間複雜度
- 平均情況
平均來說，在煎餅排序的第 i 次傳遞中會進行 n-i 次比較。所以，如果有 n 次迭代，那麼平均時間複雜度可以用下式來表示。
(n-1) + (n-2) + (n-3) + ... + 1 = n*(n-1)/2
因此，時間複雜度為 [Big Theta]：O(n2)。也可以通過計算迴圈次數來計算。總共有兩個迴圈的 n 次迭代，使得複雜度：n*n = n2。
- 最壞情況
最壞的情況發生在小元素和大元素交替的時候。共需要 2n-3 次翻轉。所需的翻轉次數為 O(n)。最壞情況下的時間複雜度為 [Big O]：O(n2)。
- 最佳情況
最好的情況是陣列已經排序，不需要翻轉。最佳情況下的時間複雜度是 [Big Omega]：O(n)。
空間複雜度
這個演算法的空間複雜度是 O(n)，因為除了一個臨時變數外，不需要額外的記憶體。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn