0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@SciencePlayer(SciencePlayer)

ソートアルゴリズム (バブル・シェーカー・コム)

Last updated at Posted at 2020-02-18

概要

3つのソートアルゴリズム(バブルソート、シェーカーソート、コムソート)の計算時間を検証・比較

検証

  • 検証条件
    • 配列の要素数を1000~10000まで1000ずつ増やしたときの各手法における計算時間を求める
    • 配列に格納する数は0~199999までの範囲でランダムに定める。同じ要素数で3つの手法それぞれの計算時間を求めるときは、全要素が同じ配列をソートする
    • 同じ要素数の配列のソートでは、どの手法でも配列の並び方は同じにする
  • ソースコード(main関数)
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#include <time.h>

double executeBubbleSort(int *, int);
double executeShakerSort(int *, int);
double executeCombSort(int *, int );
void checkSort(int *, int, bool);
void swap(int *, int, int);
void printArray(int *, int, bool);
void printStats(int, int, bool);

// 配列の最大の要素数
#define MAX_NUM 10000
// 配列に格納する最大の値
#define MAX_VALUE 200000
// いくつの配列の要素数のパターンで検証するか
#define PATTERN 10

int main(void){

	int i, j;
	int *a;
	int *b;
	int *c;
	int n;
	// それぞれのソートの手法にかかった時間
	double bubbleTime[PATTERN] = {}, shakerTime[PATTERN] = {}, combTime[PATTERN] = {};

	srand((unsigned int)time(NULL));
	for(i = 0; i < PATTERN; i++){
		// 要素数
		n = (i+1)*MAX_NUM/PATTERN;
		// a: an array for bubble sort, b: shaker sort, c: comb sort
		a = (int *)malloc(sizeof(int)*n);
		b = (int *)malloc(sizeof(int)*n);
		c = (int *)malloc(sizeof(int)*n);
		// insert numbers into an array at random
		for(j = 0; j < n; j++){
			a[j] = rand()%MAX_VALUE;
			b[j] = a[j];
			c[j] = a[j];
		}

		// 要素数ごとの実行時間を手法ごとに記録する
		printf("== No.%3d The number of elements : %5d ==\n", i+1, n);
		printf("BUBBLE SORT\n");
		bubbleTime[i] = executeBubbleSort(a, n);
		printf("SHAKER SORT\n");
		shakerTime[i] = executeShakerSort(b, n);
		printf("COMB SORT\n");
		combTime[i] = executeCombSort(c, n);

		free(a);
		free(b);
		free(c);
	}
  • Bubble Sort
// 配列とその要素数を引数とし、実行時間を戻り値とする
double executeBubbleSort(int *a, int n){

	int i, j;
	clock_t start, end;
	bool isSwapped = false;
	int step = 0;	// 要素同士を比較した回数
	int howManyTimesSwapped = 0;	// 実際に交換をした回数
	double calcTime;
	bool isDisplayed = false;
	bool ascendingOrDescending = true;

	// ソート前の配列の一部を表示
	printArray(a, n, isDisplayed);

	// Start measuring the time of bubble sort
	start = clock();

	// 昇順に並べ替える
	for(i = n-1; i >= 0; i--){
		isSwapped = false;
		for(j = 0; j < i; j++){
			step++;
			if(a[j] > a[j+1]){
				isSwapped = true;
				howManyTimesSwapped++;
				swap(a, j, j+1);
			}
		}
		// 一度も入れ替えがなければ終了
		if(!isSwapped) break;
	}

	end = clock();

	// 計算時間を算出
	calcTime = (double)(end - start)/(double)CLOCKS_PER_SEC;

	// 正確にソートができたかを確認する
	checkSort(a, n, ascendingOrDescending);

	// ソートした配列の一部を表示
	printArray(a, n, isDisplayed);
	// 実際に入れ替えた数を表示する
	isDisplayed = true;
	printStats(step, howManyTimesSwapped, isDisplayed);

	return(calcTime);

}
  • Shaker Sort
// 配列とその要素数を引数とし、実行時間を戻り値とする
double executeShakerSort(int *a, int n){

	int i, j;
	clock_t start, end;
	bool isSwapped = false;
	int step = 0;	// 要素同士を比較した回数
	int howManyTimesSwapped = 0;	// 実際に交換をした回数
	double calcTime;
	bool isDisplayed = false;
	bool ascendingOrDescending = true;

	// ソート前の配列の一部を表示
	printArray(a, n, isDisplayed);

	// Start measuring the time of shaker sort
	start = clock();

	// 昇順に並べ替える
	for(i = n-1; i >= 0; i--){
		isSwapped = false;
		for(j = (n-1)-i; j < i; j++){
     		step++;
			if(a[j] > a[j+1]){
				isSwapped = true;
				howManyTimesSwapped++;
				swap(a, j, j+1);
			}
		}
		// 一度も入れ替えがなければ終了
		if(!isSwapped) break;

		isSwapped = false;
		for(j = i-1; j > (n-1)-i; j--){
			step++;
			if(a[j-1] > a[j]){
				isSwapped = true;
				howManyTimesSwapped++;
				swap(a, j-1, j);
			}
		}
		// 一度も入れ替えがなければ終了
		if(!isSwapped) break;
	}

	end = clock();

	// 計算時間を算出
	calcTime = (double)(end - start)/(double)CLOCKS_PER_SEC;

	// 正確にソートができたかを確認する
	checkSort(a, n, ascendingOrDescending);

	// ソートした配列の一部を表示
	printArray(a, n, isDisplayed);
	// 実際に入れ替えた数を表示する
	isDisplayed = true;
	printStats(step, howManyTimesSwapped, isDisplayed);

	return(calcTime);

}
  • Comb Sort
// 配列とその要素数を引数とし、実行時間を戻り値とする
double executeCombSort(int *a, int n){

	int i, j;
	int h;
	clock_t start, end;
	bool isSwapped = true;
	int step = 0;	// 要素同士を比較した回数
	int howManyTimesSwapped = 0;	// 実際に交換をした回数
	double calcTime;
	bool isDisplayed = false;
	bool ascendingOrDescending = true;

	// ソート前の配列の一部を表示
	printArray(a, n, isDisplayed);

	// Measuring the time of comb sort
	start = clock();

	h = n*10/13;
	while(h >= 1 && isSwapped){
		isSwapped = false;
		for(i = n-h-1; i >= 0; i--){
 			step++;
			if(a[i] > a[i+h]){
				isSwapped = true;
				howManyTimesSwapped++;
				swap(a, i, i+h);
			}
		}
		if(h >= 2) h = h*10/13;

	}

	end = clock();

	// 計算時間を算出
	calcTime = (double)(end - start)/(double)CLOCKS_PER_SEC;

	// 正確にソートができたかを確認する
	checkSort(a, n, ascendingOrDescending);

	// ソートした配列の一部を表示
	printArray(a, n, isDisplayed);
	// 実際に入れ替えた数を表示する
	isDisplayed = true;
	printStats(step, howManyTimesSwapped, isDisplayed);

	return(calcTime);

}
  • 要素数が数千～一万もある配列の要素を見ることはできないため、本当にソートできたかどうかを確認する関数を作成した
    • ascendingOrDescendingの値(true/false)の値を変えることで昇順降順どちらでも確認できるようにしてある
// 正確にソートができたかを確認する
// ascendingOrDescending: false=降順(descending order), true=昇順(ascending order)
void checkSort(int *a, int n, bool ascendingOrDescending){

	int i;
	
	for(i = 0; i < n-1; i++){
		
		if(ascendingOrDescending){

			if(a[i] > a[i+1]){
				printf("sort failure\n");
				printf("(No.%d(%d) & No.%d(%d))\n", i+1, a[i], i+2, a[i+1]);
				exit(1);
			}

		}else{

			if(a[i] < a[i+1]){
				printf("sort failure\n");
				exit(1);
			}

		}

	}

}

検証結果

  • 隣同士を比較回数と入れ替えた回数
    • step
      隣同士を比較した回数
      何回forループを周ったかのカウント
    • howManyTimesSwapped
      隣同士を入れ替えた回数
      配列の要素次第で大きく変わる
    • stepもswapした回数はコムソートが一番少ない
== No.  1 The number of elements :  1000 ==
BUBBLE SORT
step :     498465, howManyTimesSwapped :     240936
SHAKER SORT
step :     376740, howManyTimesSwapped :     240936
COMB SORT
step :      24707, howManyTimesSwapped :       4523
== No.  2 The number of elements :  2000 ==
BUBBLE SORT
step :    1995172, howManyTimesSwapped :     998185
SHAKER SORT
step :    1500499, howManyTimesSwapped :     998185
COMB SORT
step :      53378, howManyTimesSwapped :      10102
== No.  3 The number of elements :  3000 ==
BUBBLE SORT
step :    4497870, howManyTimesSwapped :    2311872
SHAKER SORT
step :    3495264, howManyTimesSwapped :    2311872
COMB SORT
step :      80055, howManyTimesSwapped :      15875
== No.  4 The number of elements :  4000 ==
BUBBLE SORT
step :    7995984, howManyTimesSwapped :    4080067
SHAKER SORT
step :    6115230, howManyTimesSwapped :    4080067
COMB SORT
step :     110722, howManyTimesSwapped :      22532
== No.  5 The number of elements :  5000 ==
BUBBLE SORT
step :   12491505, howManyTimesSwapped :    6280652
SHAKER SORT
step :    9388729, howManyTimesSwapped :    6280652
COMB SORT
step :     143382, howManyTimesSwapped :      28847
== No.  6 The number of elements :  6000 ==
BUBBLE SORT
step :   17996955, howManyTimesSwapped :    9058307
SHAKER SORT
step :   13679609, howManyTimesSwapped :    9058307
COMB SORT
step :     178052, howManyTimesSwapped :      35616
== No.  7 The number of elements :  7000 ==
BUBBLE SORT
step :   24488625, howManyTimesSwapped :   12079281
SHAKER SORT
step :   18179265, howManyTimesSwapped :   12079281
COMB SORT
step :     207722, howManyTimesSwapped :      41502
== No.  8 The number of elements :  8000 ==
BUBBLE SORT
step :   31995405, howManyTimesSwapped :   15824307
SHAKER SORT
step :   23699299, howManyTimesSwapped :   15824307
COMB SORT
step :     269383, howManyTimesSwapped :      50683
== No.  9 The number of elements :  9000 ==
BUBBLE SORT
step :   40480449, howManyTimesSwapped :   20190559
SHAKER SORT
step :   30480450, howManyTimesSwapped :   20190559
COMB SORT
step :     276056, howManyTimesSwapped :      55248
== No. 10 The number of elements : 10000 ==
BUBBLE SORT
step :   49988097, howManyTimesSwapped :   24946058
SHAKER SORT
step :   37602269, howManyTimesSwapped :   24946058
COMB SORT
step :     346732, howManyTimesSwapped :      63200
  • 計算時間
    • おおまかには バブル＞=シェーカー＞>コム となる。しかし、複数回プログラムを実行するとシェーカーソートの時間が少しだけバブルソートを上回るときがたまにある。
== No.  1 The number of elements :  1000 ==
bubble sort : 0.0013260000
shaker sort : 0.0011170000
comb   sort : 0.0000750000
== No.  2 The number of elements :  2000 ==
bubble sort : 0.0050730000
shaker sort : 0.0044660000
comb   sort : 0.0001980000
== No.  3 The number of elements :  3000 ==
bubble sort : 0.0112750000
shaker sort : 0.0097370000
comb   sort : 0.0002630000
== No.  4 The number of elements :  4000 ==
bubble sort : 0.0187430000
shaker sort : 0.0164390000
comb   sort : 0.0003590000
== No.  5 The number of elements :  5000 ==
bubble sort : 0.0296430000
shaker sort : 0.0273010000
comb   sort : 0.0004610000
== No.  6 The number of elements :  6000 ==
bubble sort : 0.0418130000
shaker sort : 0.0375110000
comb   sort : 0.0006180000
== No.  7 The number of elements :  7000 ==
bubble sort : 0.0594490000
shaker sort : 0.0519960000
comb   sort : 0.0007030000
== No.  8 The number of elements :  8000 ==
bubble sort : 0.0775220000
shaker sort : 0.0675540000
comb   sort : 0.0008440000
== No.  9 The number of elements :  9000 ==
bubble sort : 0.1005070000
shaker sort : 0.0861640000
comb   sort : 0.0011230000
== No. 10 The number of elements : 10000 ==
bubble sort : 0.1276620000
shaker sort : 0.1111880000
comb   sort : 0.0011620000
0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?