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

ソートアルゴリズム

More than 1 year has passed since last update.

整列(ソート)とは

  • データのリストを線形順序で並べ替える
    • 昇順、降順
  • 並べ替えの対象は「キーを含むレコード」
    • レコード:データの構成単位
    • キー:レコードの中で順序比較の対象となる欄
    • 例:アドレス帳
      • レコード:一人分の住所録情報(氏名、住所、電話番号)
      • キー:氏名(フリガナ)

内部ソートと外部ソート

  • 内部整列:整列の対象が主記憶に収まる
  • 外部整列:二次記憶(ディスク等)を使う

安定ソート

  • 同じキーをもつレコードの順序を保存するソートアルゴリズム

ソートのための三大要素

  • 交換
  • 選択
  • 挿入

ほとんどのソートアルゴリズムは、これらの考え方を応用したもの

「交換」のサンプルコード(c言語)

swap.c
#include<stdio.h>

/* 値を交換する関数 */
void swap (int *x, int *y) {
  int temp;   // 値を一時的に保存する変数

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

int main (void) {
  int a = 1;
  int b = 5;

  printf("a = %d, b = %d\n", a, b);
  swap(&a, &b);
  printf("a = %d, b = %d\n", a, b);

  return 0;
}

実行結果

a = 1, b = 5
a = 5, b = 1

代表的なソートアルゴリズム

選択ソート
挿入ソート
バブルソート
シェルソート
クイックソート
ヒープソート
基数ソート
マージソート
分布数え上げソート

参考

ソートアルゴリズムを極める! 〜 なぜソートを学ぶのか 〜
ソートアルゴリズム20種をCで作ってみた
【Unity】ソートアルゴリズム12種を可視化してみた

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
ユーザーは見つかりませんでした