煎餅排序
煎餅排序是一種基於反轉的排序演算法。它是基於現實生活中的問題,即藉助鏟子在盤子上類似於攤煎餅。它的名字來源於演算法中使用的翻轉操作,類似於翻轉煎餅。與大多數排序演算法試圖最小化執行排序所需的比較次數不同,它試圖以最小的反轉次數對陣列進行排序。就像選擇排序一樣,它也將最大元素放在最後。
煎餅排序演算法
假設我們有一個包含 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