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

C言語で挿入ソート

More than 1 year has passed since last update.

挿入ソートとは

先頭からi番目までが整列済みの時、i+1番目の要素を、正しい位置に挿入する。
整列済みのデータに新しいデータを追加し、再び整列するときなどに便利。

サンプルコード

ここでは、int型の配列を、挿入ソートを用いて小さい順に並べ替える。

insertion_sort.c
#include<stdio.h>

/* 値を入れ替える関数 */
void swap (int *x, int *y) {
  int temp;    // 値を一時保存する変数

  temp = *x;
  *x = *y;
  *y = temp;
}

/* 挿入ソート */
void insertion_sort (int array[], int array_size) {
  int i, j;

  for (i = 1; i < array_size; i++) {   // 先頭から順にソート
    j = i;
    while ((j > 0) && (array[j-1] > array[j])) {   //整列済みの場合は処理しない
      swap(&array[j-1], &array[j]);   // 整列されていない要素を交換
      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");

  insertion_sort(array, 10);

  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

性能

  • 最悪の場合:逆順にソート済み
    • while文の比較回数:約$n^2/2$
    • while文の実行回数:約$n^2/4$
    • 比較+実行=$O(n^2)$
  • 最善の場合:ほぼ整列済み
    • while文の比較回数:$n-1$
    • while文の実行回数:$0$
    • 計算量はほぼ線形時間$O(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
ユーザーは見つかりませんでした