読者です 読者をやめる 読者になる 読者になる

引くなっ!

声優 佐倉綾音さんとその出演作品を応援しています

pancake sorting algorithm

はじめに

間違いあったら教えて欲しい(´・ω・`) 理解まだ半分 加筆予定ちう


f:id:mikamiyuki:20151208173652j:plain
みなさんはパンケートソートというソーティングアルゴリズムをご存知でしょうか?
私は ソート - Wikiwand を見ている時に発見しました。 f:id:mikamiyuki:20151208140635p:plain

どういうソートか視覚的に見たい人は以下の動画がおすすめです

www.youtube.com

どういうアルゴリズムなの・。・?


ビルゲイツが発表したパンケーキソートアルゴリズムの論文は1979"
http://www.eecs.berkeley.edu/~christos/papers/GP79.pdf
こちらに詳しく記述されている。

簡単に説明すると prefix reversals のみでソートするソーティング.

プレフィクスリバースとは 例えば,(3,2,1,4)の場合 長さ3のプレフィックス反転をすれば3,2,1が1,2,3と反転することになる。

上の例を用いれば (5,8,2,4,1)をパンケーキソートすると
{5,8,2,4,1}
- 長さ2のプレフィクス反転
{8,5,2,4,1}
- 長さ5のプレフィクス反転
{1,4,2,5,8}
- 長さ3のプレフィクス反転
{2,1,4,5,8}
- 長さ 2のプレフィクス反転
{1,2,4,5,8}
🔚

よって反転のみでソートできた(∩´∀`)∩

実用性

誰か教えてくれ。そこまでまだ読めてない(´・ω・`)
DNAコンピュータとかに用いられてる?????
blogs.yahoo.co.jp

Code


(´・ω・`)

#include <stdio.h>
#include <algorithm>
#include <stdlib.h>

//表示
void print_array(int *list,int length){
        for(int i=0;i<length;i++)
                printf("%d ",list[i]);
        printf("\n");
}

//回転
void do_flip(int *list,int length,int num){
        for(int i=0;i<--num;i++)
                std::swap(list[i],list[num]);
}

//パンケーキ食べたい
int pancake_sort(int *list,unsigned int length){
        if(length<2)
                return 0;
        int i,j;
        int max_num_pos;
        int moves=0;//ソート回数
        for(i=length;i>1;i--){
                max_num_pos=0;
                for(j=0;j<i;j++){
                        if(list[j]>list[max_num_pos])
                                max_num_pos=j;
                }
                if(max_num_pos==i-1)
                        continue;
                if(max_num_pos){
                        moves++;
                        do_flip(list,length,max_num_pos+1);
                }
                moves++;
                do_flip(list,length,i);
        }
        return moves;
}

int main(int argc, char **argv){
        int list[9];
        int i;
        //初期値
        srand(time(NULL));
        for(i=0;i<9;i++)
                list[i]=rand()%1000;
        printf("Before\n");
        print_array(list,9);

        int moves=pancake_sort(list,9);
        printf("After\n");
        print_array(list,9);
}

実行結果

Before
96 82 7 49 89 92 33 47 8 
Sorted
8 82 7 49 89 92 33 47 96 
8 47 7 49 89 92 33 82 96 
8 47 33 49 89 92 7 82 96 
8 47 33 92 89 49 7 82 96 
92 47 33 8 89 49 7 82 96 
92 33 47 8 89 49 7 82 96 
82 33 47 8 89 49 7 92 96 
82 7 47 8 89 49 33 92 96 
82 7 49 8 89 47 33 92 96 
82 7 49 89 8 47 33 92 96 
89 7 49 82 8 47 33 92 96 
89 49 7 82 8 47 33 92 96 
33 49 7 82 8 47 89 92 96 
33 47 7 82 8 49 89 92 96 
33 47 8 82 7 49 89 92 96 
82 47 8 33 7 49 89 92 96 
82 8 47 33 7 49 89 92 96 
49 8 47 33 7 82 89 92 96 
49 7 47 33 8 82 89 92 96 
49 7 33 47 8 82 89 92 96 
8 7 33 47 49 82 89 92 96 
8 47 33 7 49 82 89 92 96 
47 8 33 7 49 82 89 92 96 
7 8 33 47 49 82 89 92 96 
7 33 8 47 49 82 89 92 96 
33 7 8 47 49 82 89 92 96 
8 7 33 47 49 82 89 92 96 
7 8 33 47 49 82 89 92 96 
After
7 8 33 47 49 82 89 92 96

参考/引用


パンケーキソート問題 - Distributed Systems Laboratory www.wikiwand.com www.theguardian.com

広告を非表示にする