バブルソート

最近ソートについて勉強し直したのでメモしときます。

ばらばらな配列を、前から順番に見ていって隣同士入れ替えていくのを何回も繰り返す。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <iostream>

#define N 10

int x[N];
using namespace std;

void BabbleSort(void){
    int j, flag;

    do{
        flag = 0;
        for(int i=0;i<N-1;i++){
            if(x[i] > x[i+1]){
                flag = 1;
                j = x[i];
                x[i] = x[i+1];
                x[i+1] = j;
            }
        }
    }while(flag == 1);
}

void BabbleSort_2(void){
    int j, k, flag;

    k = 0;
    do{
        flag = 0;
        for(int i=0;i<N-1-k;i++){
            if(x[i] > x[i+1]){
                flag = 1;
                j = x[i];
                x[i] = x[i+1];
                x[i+1] = j;
            }
        }
        k++;
    }while(flag == 1);
}

int main(){
    srand((unsigned int)time(NULL));

    cout << "Ready for Sort" << endl;
    for(int i=0;i<N;i++){
        x[i] = rand();
        cout << x[i] << endl;
    }

    cout << "Start Sorting" << endl;
    BabbleSort_2();

    cout << "End" << endl;

    for(int i=0;i<N;i++){
        cout << x[i] << endl;
    }
}

BabbleSort()は上で書いた通りの処理をするだけ。

BabbleSort_2()は、一度後ろまで見ていった配列の後ろの方はすでソート済であるということを利用して繰り返しの回数を減らしたもの。