ソートアルゴリズム(バブルソート)

雑談

整列アルゴリズムとは

データをある規則に従って並びを変えることを整列(ソート)という。
整列(ソート)アルゴリズムもいくつかあるが、大きく分けると7つになります。

  • バブルソート
  • 選択ソート
  • 挿入ソート
  • クイックソート
  • ヒープソート
  • シェルソート
  • マージソート

様々なソートがありますが、計算量やメモリ量また、データの状態によって適切なソートがあります。

バブルソートとは

上で述べたソートの一つであるが、隣り合う要素の大小を比較しながら整列するソートになります。最悪の計算量がO(n^2)、最良計算量がO(n)となります。

全ての要素で、隣接する要素と比較し順序が逆であった際に、変更をおこなう。これを要素数−1回繰り返してソートを行うようになります。

C言語での実装

#include <stdio.h>
void output(int *,int);
void bubbleSort(int *,int);
int main(){
  int data[]={10,5,8,3,2,1,15,13,52,35,24,42,23,12,42,56};
  int length= sizeof data/sizeof(int);
  output(data,length);
  bubbleSort(data,length);
  output(data,length);
}

void bubbleSort(int *data,int length){
int i,j,temp;

  for(i=0;i<length-1;i++){
    for(j=length-1;j>i;j--){
      if(data[j-1]>data[j]){
        temp = data[j];
        data[j] = data[j-1];
        data[j-1] = temp;
      }
    }
  }
}

void output(int *data ,int length){
  int i;
  for(i=0;i<length;i++){
    printf("%d ",data[i]);
  }
      printf("\n");
}

まとめ

ソートの種類やロジックと計算量等に関しては、一度学習しましたが、少し忘れている部分があるので、もう一度調べてみることにしました。他のソートに関しても時間がある時に調べて、実装をしてみようと思います。