ソートアルゴリズム（バブルソート）

2018年10月21日雑談

Contents

1. 整列アルゴリズムとは
2. バブルソートとは
3. まとめ
4. 共有:
5. いいね:
6. 関連

整列アルゴリズムとは

データをある規則に従って並びを変えることを整列（ソート）という。
整列（ソート）アルゴリズムもいくつかあるが、大きく分けると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");
}