Skip to content

Instantly share code, notes, and snippets.

@komasaru
Last active December 24, 2017 01:52
Show Gist options
  • Save komasaru/5614cd0ba34937765ac3c71957b00f9b to your computer and use it in GitHub Desktop.
Save komasaru/5614cd0ba34937765ac3c71957b00f9b to your computer and use it in GitHub Desktop.
C++ source code to test sorting algorithms.
#include <cstdlib> // for srand()
#include "sort.h"
using namespace std;
/*
* コンストラクタ
*/
Sort::Sort()
{
// 元になる配列を生成
srand((unsigned int)time(NULL));
printf("#### Base Array\n");
for (i = 0; i < N; i++) {
base[i] = rand() % M;
printf("%5d ", base[i]);
if ((i + 1) % 10 == 0) printf("\n");
}
printf("\n");
}
/*
* 計算
*/
void Sort::exec()
{
// 基本交換法(バブル・ソート)
printf("%-22s", "1 : Bubble Sort");
sort_bubble(base);
// 基本選択法(直接選択法)
printf("%-22s", "2 : Selection Sort");
sort_selection(base);
// 基本挿入法
printf("%-22s", "3 : Insertion Sort");
sort_insertion(base);
// 改良交換法(クイック・ソート)
printf("%-22s", "4 : Quick Sort");
sort_quick(base);
// 改良選択法(ヒープ・ソート)(上方移動)
printf("%-22s", "5-1: Heap Sort(Up)");
sort_heap_up(base);
// 改良選択法(ヒープ・ソート)(下方移動)
printf("%-22s", "5-2: Heap Sort(Down)");
sort_heap_down(base);
// 改良挿入法(シェル・ソート)
printf("%-22s", "6 : Shell Sort");
sort_shell(base);
}
/*
* 基本交換法(バブル・ソート)
*/
void Sort::sort_bubble(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
for (i = 1; i < N - 1; i++) {
for (j = N - 1; j > i; j--) {
if (a[j] < a[j - 1]) {
t = a[j];
a[j] = a[j - 1];
a[j - 1] = t;
}
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 基本選択法(直接選択法)
*/
void Sort::sort_selection(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
for (i = 0; i < N - 1; i++) {
min = a[i];
s = i;
for (j = i + 1; j < N ; j++) {
if (a[j] < min) {
min = a[j];
s = j;
}
}
t = a[i];
a[i] = a[s];
a[s] = t;
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 基本挿入法
*/
void Sort::sort_insertion(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
for (i = 1; i < N; i++) {
for (j = i - 1; j >= 0; j--) {
if (a[j] > a[j + 1]) {
t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
} else {
break;
}
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 改良交換法 (クイック・ソート)
*/
void Sort::sort_quick(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
quick(a, 0, N - 1);
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* 改良選択法 (ヒープ・ソート)(上方移動)
*/
void Sort::sort_heap_up(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 初期ヒープ作成(上方移動)
generate_heap_up(h, base);
// ソート処理
n = N; // データ個数
m = N; // n の保存
while (n > 1) {
swap(&h[1], &h[n]);
n--; // 木の終端切り離し
p = 1;
s = 2 * p;
while (s <= n) {
if (s < n && h[s + 1] > h[s]) s++;
if (h[p] >= h[s]) break;
swap(&h[p], &h[s]);
p = s;
s = 2 * p;
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(h, tt, 1);
}
/*
* 改良選択法 (ヒープ・ソート)(下方移動)
*/
void Sort::sort_heap_down(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 元の配列を元の木としてコピー
for (i = 1; i <= N; i++)
h[i] = base[i - 1];
// 初期ヒープ作成(下方移動)
generate_heap_down(h);
// ソート処理
n = N; // データ個数
m = N; // n の保存
while (n > 1) {
swap(&h[1], &h[n]);
n--; // 木の終端切り離し
p = 1;
s = 2 * p;
while (s <= n) {
if (s < n && h[s + 1] > h[s]) s++;
if (h[p] >= h[s]) break;
swap(&h[p], &h[s]);
p = s;
s = 2 * p;
}
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(h, tt, 1);
}
/*
* 改良挿入法 (シェル・ソート)
*/
void Sort::sort_shell(int *base)
{
// 処理開始時刻
t1 = clock();
// 指定回数 LOOP
for (l = 0; l < L; l++) {
// 配列コピー
for (i = 0; i < N; i++) a[i] = base[i];
// ソート処理
gap = N / 2;
while (gap >0) {
for (k = 0; k < gap; k++) {
for (i = k + gap; i < N; i += gap) {
for (j = i - gap; j >= k; j -= gap) {
if (a[j] > a[j + gap]) {
t = a[j];
a[j] = a[j + gap];
a[j + gap] = t;
} else {
break;
}
}
}
}
gap /= 2;
}
}
// 処理時間計算・結果出力
t2 = clock();
tt = (double)(t2 - t1) / CLOCKS_PER_SEC;
display(a, tt, 0);
}
/*
* クイック・ソート用再帰関数
*/
void Sort::quick(int *a, int left, int right)
{
if (left < right) {
s = a[left]; // 最左項を軸にする
i = left; // 軸より小さいグループ
j = right + 1; // 軸より大きいグループ
while (1) {
while (a[++i] < s);
while (a[--j] > s);
if (i >= j) break;
t = a[i];
a[i] = a[j];
a[j] = t;
}
a[left] = a[j];
a[j] = s; // 軸を正しい位置に挿入
quick(a, left, j - 1); // 左部分列に対する再帰呼び出し
quick(a, j + 1, right); // 右部分列に対する再帰呼び出し
}
}
/*
* ヒープ・ソート用ヒープ生成(上方移動)関数
*/
void Sort::generate_heap_up(int *heap, int *base)
{
for (i = 1; i <= N; i++) {
// 元データ配列から1つヒープ要素として追加
heap[i] = base[i - 1];
s = i; // 追加要素の位置
p = s / 2; // 親要素の位置
while (s >= 2 && heap[p] < heap[s]) {
w = heap[p];
heap[p] = heap[s];
heap[s] = w;
s = p; // 追加要素の位置
p = s / 2; // 親要素の位置
}
}
}
/*
* ヒープ・ソート用ヒープ生成(下方移動)関数
*/
void Sort::generate_heap_down(int *heap)
{
n = N; // データ個数
for (i = n / 2; i >= 1; i--) {
p = i; // 親要素の位置
s = 2 * p; // 左の子要素の位置
while (s <= n) {
if (s < n && heap[s + 1] > heap[s]) s++; // 左右子要素の小さい方
if (heap[p] >= heap[s]) break;
swap(&heap[p], &heap[s]); // 交換
p = s; // 親要素の位置
s = 2 * p; // 左の子要素の位置
}
}
}
/*
* ヒープ・ソート用スワップ関数
*/
void Sort::swap(int *a, int *b)
{
t = *a;
*a = *b;
*b = t;
}
/*
* 結果出力
* k = 0 (ヒープ以外用)
* k = 1 (ヒープ用)
*/
void Sort::display(int *a, double tt, int k)
{
// ソート結果確認
// (ソート結果を確認したければ、以下のコメント解除)
//printf("\n");
//for (i = k; i < N + k; i++) {
// printf("%5d ", a[i]);
// if ((i + 1 - k) % 10 == 0) printf("\n");
//}
// 処理時間出力
printf("Time: %6.2lf sec.\n", tt);
}
#ifndef INCLUDED_SORT_H
#define INCLUDED_SORT_H
#include <stdio.h>
#include <time.h>
#define N 1000 // データ個数
#define M 10000 // 値 MAX ( M 未満 )
#define L 10000 // ソート試行回数
/*
* ソートクラス
*/
class Sort
{
// 各種変数
double tt; // 計算時間
clock_t t1, t2; // 計算開始CPU時刻、計算終了CPU時刻
int i, j, k, l; // Loop インデックス
int base[N]; // 元データ用配列
int a[N]; // 作業用配列
int h[N + 1]; // 作業用配列(ヒープ・ソート用)
int min, s, t, gap, m, n, p, w; // ソート処理用ワーク
public:
Sort(); // コンストラクタ
void exec(); // ソート処理実行
private:
void sort_bubble(int *); // 基本交換法(バブル・ソート)
void sort_selection(int *); // 基本選択法(直接選択法)
void sort_insertion(int *); // 基本挿入法
void sort_quick(int *); // 改良交換法(クイック・ソート)
void sort_heap_up(int *); // 改良選択法(ヒープ・ソート)(上方移動)
void sort_heap_down(int *); // 改良選択法(ヒープ・ソート)(下方移動)
void sort_shell(int *); // 改良挿入法(シェル・ソート)
void quick(int *, int, int); // クイック・ソート用再帰関数
void generate_heap_up(int *, int *); // ヒープ・ソート用ヒープ作成(上方移動)関数
void generate_heap_down(int *); // ヒープ・ソート用ヒープ作成(下方移動)関数
void swap(int *, int *); // ヒープ・ソート用スワップ関数
void copy_array(int *, int *); // 配列コピー
void display(int *, double, int); // 結果出力
};
#endif
/***********************************************************
* ソート処理各種のテスト
**********************************************************/
#include <iostream>
#include "sort.h"
using namespace std;
/*
* メイン処理
*/
int main()
{
try
{
// ==== インスタンス化
Sort objSort;
// ==== ソート処理実行
objSort.exec();
}
catch (...) {
// ==== 異常終了
cout << "例外発生!" << endl;
return -1;
}
// ==== 正常終了
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment