整列

整列アルゴリズムの実装

以下は，選択ソート，挿入ソート，ヒープソート，クイックソートの整列アルゴリズムを含むC言語プログラムであり，教科書リスト5.2, 5.5, 5.7 ~ 5.10 (pp.95 ~ 111) をベースに実装されている． ソースコードは，sort_collection.h，sort_collection.c，main_sort_collection.c に分割されている．

サンプルコードはこちらからダウンロード可能．

ヘッダーファイル sort_collection.h

#ifndef INCLUDE_GUARD_SORT_COLLECTION_H
#define INCLUDE_GUARD_SORT_COLLECTION_H

extern unsigned long compare_count;

void cmp_cnt_reset(void);
void display(int a[], int n);
void selection_sort(int a[], int n);
void insertion_sort(int a[], int n);
void heap_sort(int a[], int n);
void q_sort(int a[], int n);

#endif  // INCLUDE_GUARD_SORT_COLLECTION_H

ソースファイル sort_collection.c

#include <stdio.h>
#include <stdlib.h>
#include "sort_collection.h"

unsigned long compare_count = 0;

void cmp_cnt_reset(void) {
  compare_count = 0;
}

int compare(int ldata, int rdata) {
  compare_count++;
  if      (ldata  < rdata) return -1;
  else if (ldata == rdata) return  0;
  else                     return  1;
}

void swap(int a[], int lidx, int ridx) {
  int temp = a[lidx];
  a[lidx] = a[ridx];
  a[ridx] = temp;
}

void display(int a[], int n) {
  int i;
  for (i = 0; i < n; i++) {
    printf("%d ", a[i]);
  }
  printf("\n");
}

void selection_sort(int a[], int n) {
  int i, j;
  for (i = 0; i < n - 1; i++) {
    int min = i;
    for (j = i + 1; j < n; j++) {
      if (compare(a[j], a[min]) == -1) {
        min = j;
      }
    }
    swap(a, i, min);
  }
}

// Insertion sort
/**************************************/
void insertion_sort(int a[], int n) { ... }

// Functions for Heap sort
/**************************************/
void sift_down(int a[], int i, int n) { ... }

void build_heap (int a[], int n) { ... }

void heap_sort (int a[], int n) { ... }

// Functions for Quick sort
/**************************************/
int partition(int a[], int pivot, int left, int right) { ... }

void quick_sort(int a[], int left, int right) { ... }

void q_sort(int a[], int n) {
  quick_sort(a, 0, n-1);
}

ソースファイル main_sort_collection.c

#include <stdio.h>
#include <stdlib.h>
#include "sort_collection.h"

int GetRandom(int min, int max) {
  return min + (int)(rand()*(max-min+1.0)/(1.0+RAND_MAX));
}

int main(int argc, char *argv[]) {
  if (argc != 1) {
    int numdata = atoi(argv[1]);  // set numdata with cmd. argument
    int *array = (int*)malloc(sizeof(int) * numdata);
    int i;
    printf("Enter %d integers\n", numdata);
    for (i = 0; i < numdata; i++) {
      scanf("%d", &array[i]);  // enter integers
    }
    selection_sort(array, numdata);
    printf("sorting result\n");
    display(array, numdata);
    printf("# of comparisons: %lu\n", compare_count);
    free(array);
  } else {
    int numdata;
    for (numdata = 1000; numdata <= 10000; numdata += 1000) {  // numdata is 1000, 2000, ..., 10,000
      int *array = (int*)malloc(sizeof(int) * numdata);
      int i;
      for (i = 0; i < numdata; i++) {
        array[i] = GetRandom(0, (numdata * 10 - 1));  // random number from 0 to numdata * 10 - 1
      }
      selection_sort(array, numdata);
      printf("%d %lu\n", numdata, compare_count);
      cmp_cnt_reset();
      free(array);
    }
  }

  return EXIT_SUCCESS;
}

コンパイルと実行

以下の内容の Makefile を作成する．

ファイル Makefile

sort_collection: sort_collection.o main_sort_collection.o

コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される．

mac$ make
cc    -c -o sort_collection.o sort_collection.c
cc    -c -o main_sort_collection.o main_sort_collection.c
cc   sort_collection.o main_sort_collection.o   -o sort_collection

numdata をコマンドライン引数として与えると，numdata 個の整数の入力が要求され，整列結果及び比較回数が表示される．

mac$ ./sort_collection 5
Enter 5 integers
3
1
5
4
2
sorting result
1 2 3 4 5
# of comparisons: 10
mac$

コマンドライン引数を与えないと，main 関数の else 部分が実行される．

mac$ ./sort_collection
1000 499500
2000 1999000
3000 4498500
4000 7998000
5000 12497500
6000 17997000
7000 24496500
8000 31996000
9000 40495500
10000 49995000
mac$

基本課題

  1. 挿入ソート，ヒープソート，クイックソートを実装し，以下の要件を確認すること．なお，関数 swap, compare を改変し，動作の様子を確認できるようにした場合は加点する．
    • 関数 sift_down, build_heap, partition が正しく動作すること．
    • 各ソートについて， 6 ~ 8 個程度のデータを実際に整列する例を示し，動作について説明すること．
  2. ヒープソートおよびクイックソートの性能を分析せよ．
    1. ランダムな入力データを要素として持つ大きさ numdata (numdata = 1000, 2000, ..., 10,000)の配列を生成し，各整列法を実行し，整列に要するデータの比較回数を調べ，結果をグラフを用いて分析すること．
    2. ランダムな入力データを要素として持つ配列を生成し，各整列法を実行し，整列に要する実行時間を調べ，結果をグラフを用いて分析すること． 配列の大きさは，実行時間が0.1 ~ 数秒程度になるように選ぶこと (実行時間を調べる際には，課題3: ハッシュ法に記載した事項を念頭に置きましょう)．
    3. クイックソートの計算量が最悪 (すなわち，O(n2)の計算量) になるような配列を生成し，最悪の場合の性能を整列に要するデータの比較回数を調べ，結果をグラフを用いて分析すること．
    4. 1 ~ 3 の実験結果から，クイックソートとヒープソートの性能について，比較，考察せよ．

発展課題

sort_collection に，基数ソート void radix_sort(int a[], int n, int k) を追加せよ．実装には，教科書 115 ~ 121 ページを参考にすること． この基数ソートは，10進数の各桁にバケットソートを適用し，整数を整列するアルゴリズムであり，配列 a の各要素 a[i] は, 0 ≤ a[i] < 10k とする．

  • 以下の要件を全て満たすことを確認すること．
    • 整数143, 322, 246, 755, 123, 563, 514, 522を要素とする配列に対して動作を確認すること．
    • 各桁の処理の後のバケットの内容を表示し，確認すること．

提出締切

2022年12月12日（月）13:30