ソート

ボゴソート^^;

投稿日: 更新日:


男は黙ってボゴソート^^;
馬鹿らしいソートなんだけど、よくこんな無限の猿定理を利用したソートを考えたなと思った。
しかし、O(n*n!)って…^^;
下のサンプルはとりあえずWikipediaにかいてあったトランプの例をやってみた感じ。
実際は、1回ランダムに1つと1つを交換っていう方が効率はいい。

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

void bogosort(int d[],int n)
{
    int h=1,i,j,*k,*l;
    k = (int *)malloc(sizeof(int)*n);
    l = (int *)malloc(sizeof(int)*n);
    memcpy(k,d,sizeof(int)*n);
    while(h)
    {
        for(i=0;i<n;i++)
        {
            j=rand()%(i+1);
            l[i]=l[j];
            l[j]=i;
        }
        for(i=1,d[0]=j=k[l[0]];i<n;i++)
        {
            if(j>k[l[i]])break;
            d[i]=j=k[l[i]];
            if(i==(n-1)) h=0;
        }
    }
    free(k);
    free(l);
}

int main(void)
{
    int list[] = { 132,45123,3462,36,43,5,2352,536,234,574 };
    int i,size = sizeof(list) / sizeof(int);
    bogosort(list,size);
    for(i=0;i<size;i++) printf(“%d\n”,list[i]);

    return(0);
}