整列(ソート)

情報処理用語集

整列(ソート)

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



スポンサードリンク







情報処理用語集>整列(ソート)

sort

整列ソート)とは、複数の要素からなるデータの列を、昇順(小さい順)や

降順(大きい順)などの、ある特定の規則に従って並べ替えることである。

並べ替えということもある。

整列の対象とする項目を整列キーと呼ぶ。


整列キーが同じとき、整列前の順序が保たれる整列を「安定な整列」、

保たれない整列を「安定でない整列」という。

安定でない整列は、整列前に順序のこともあるが、そうでないこともある。


コンピュータで整列を行う方法には、

@内部整列:主記憶装置上のデータを対象とする

A外部整列:補助記憶装置上の大量のデータを対象とする

があり、いろいろなアルゴリズムが発表されている。

内部整列の中でもクイックソートは高速であり、マージソートは外部整列に

用いられることが多い。


計算量を表すのに(オーダ)という記号を用い、データ個数がn個のとき、

(n)は、計算量がnに比例することを意味する。

ただし、、1回の計算にかかる時間(定数項)が異なるため、同じオーダでも

計算時間はことなる。


分類 整列法 計算量 安定
交換法 バブルソート(基本交換法) (n
クイックソート 平均(nlogn)
最悪(n
×
選択法 基本選択法 (n
ヒープソート(改良選択法) (nlogn) ×
挿入法 基本選択法 (n
シェルソート(改良挿入法) (n1.2 ×
併合法 マージソート (nlogn)
基数法 ラディクスソート(基数整列法) (kn)
kは、桁数


場合によって、分類整列を区別することもあるが、一般的にはカタカナで

ソートと示し、分類整列も同義語である。




スポンサードリンク


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