Help us understand the problem. What is going on with this article?

C言語でマージソート

More than 1 year has passed since last update.

マージソートとは

分割統治法に基づくアルゴリズム

手順

  1. 与えられた配列(長さ$n$)を$n/2$の部分配列に分割
  2. 2つの部分配列をそれぞれマージソート
  3. 得られた二つのソート済み部分配列を統合

qiita-sort-5.png

基本的な考え方

  • 整列済みの2つの配列を併合する
  • 2つの配列の先頭を見て、小さいほうを取り出す
  • 配列の併合を再帰的に実行

qiita-sort-6.png

サンプルコード

int型の配列を、マージソートを用いて整列するプログラム

merge_sort.c
#include<stdio.h>

/* マージソート */
void merge_sort (int array[], int left, int right) {
  int i, j, k, mid;
  int work[10];  // 作業用配列
  if (left < right) {
    mid = (left + right)/2; // 真ん中
    merge_sort(array, left, mid);  // 左を整列
    merge_sort(array, mid+1, right);  // 右を整列
    for (i = mid; i >= left; i--) { work[i] = array[i]; } // 左半分
    for (j = mid+1; j <= right; j++) {
      work[right-(j-(mid+1))] = array[j]; // 右半分を逆順
    }
    i = left; j = right;
    for (k = left; k <= right; k++) {
      if (work[i] < work[j]) { array[k] = work[i++]; }
      else                   { array[k] = work[j--]; }
    }
  }
}

int main (void) {
  int array[10] = { 2, 1, 8, 5, 4, 7, 9, 0, 6, 3 };
  int i;

  printf("Before sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  merge_sort(array, 0, 9);

  printf("After sort: ");
  for (i = 0; i < 10; i++) { printf("%d ", array[i]); }
  printf("\n");

  return 0;
}

実行結果

Before sort: 2 1 8 5 4 7 9 0 6 3
After sort: 0 1 2 3 4 5 6 7 8 9

性能

  • 比較回数$O(n\log{n})$で実用的
  • 作業領域が必要
  • 安定ソート
  • 性能は、入力のデータの並び方に影響されない
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした