マージソート(併合ソート)

情報処理用語集

マージソート(併合ソート)

情報処理関連の用語について、基本的知識を紹介しているサイトです。近年、情報処理はインターネットなどの普及により、毎日生活していく中で熟知され、さまざまなシーンで利用されており日常生活の一部になりつつあります。コンピュータ社会において、技術の急激な進歩や発展に伴い情報処理用語も大幅に増えてきております。膨大な量の用語を全てご紹介するのは難儀ではありますが、多様化する現状に対応して、基本的な用語から、コンピュータ全般、ソフトウェア、アルゴリズムとデータ構造、システム開発の基礎、ファイルとデータベース、通信ネットワーク、情報処理システム、産業社会と情報化、情報化の課題など、いろいろな観点から用語を努めて簡潔で、できる限り解りやすく、丁寧に説明させていただいております。情報処理関連用語の理解やスキルアップで多くの情報と知識を習得していただけたら幸いです。「初級上級システムアドミニストレータ」や「上級システムアドミニストレータ」、「基本情報技術者」、「特種情報処理技術者」、「ソフトウェア開発技術者」などIT技術関連の試験対策にも是非、お役立てください。情報処理用語集は情報処理技術者試験資格取得を目指すあなたを応援させていただきます。

マージソート(併合ソート)


スポンサードリンク






情報処理用語集
TOP


A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 数字


ア イ ウ エ オ
カ キ ク ケ コ
サ シ ス セ ソ
タ チ ツ テ ト
ナ ニ ヌ ネ ノ
ハ ヒ フ ヘ ホ
マ ミ ム メ モ
ヤ ユ ヨ
ラ リ ル レ ロ
ワ

スポンサードリンク







情報処理用語集>マ>マージソート(併合ソート)

merge sort

マージソート(併合ソート)とは、2つの整列済みデータ列を昇順(小さい順)、

あるいは、降順(大きい順)に併合することで、1つの整列済みデータ列を

作り出す整列方法である。

n個のデータの計算量はO(nlog2n)


�@整列前のデータ

A(1) A(2) A(3) A(4) A(5) A(6) A(7) A(8)
20 51 18 80 06 77 24 63



�A2分割

グループのデータ数が2つになるまで、2分割する。

20 51 18 80

06 77 24 63

20 51

18 80

06 77

24 63



�B整列

2つのデータの大小関係で、それぞれを降順に整列する。

20 51

06 77

24 63

18 80



�C併合

2つのグループを昇順に併合する。

グループが1つになるまで併合を繰り返す。

06 20 51 77

18 24 63 80

06 18 20 24 51 63 77 80


このように内部整列もできるが、大量のデータを外部整列するときに

用いられることが多い。

分割したグループをファイルに書き出せば、ファイルの併合アルゴリズムに

よって、主記憶容量以上のデータでも昇順に整列することができる。




スポンサードリンク


Copyright (C) 情報処理用語集 All Rights Reserved