煎餅排序

Harshit Jindal 2023年1月30日 2021年2月7日
  1. 煎餅排序演算法
  2. 煎餅排序示例
  3. 煎餅排序演算法實現
  4. 煎餅排序演算法的複雜度
煎餅排序

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

煎餅排序演算法

假設我們有一個包含 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 avatar Harshit Jindal avatar

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

相關文章 - Sort Algorithm