高校「情報Ⅰ」単語帳 - 開隆堂「実践 情報Ⅰ」 - アルゴリズムとプログラミング

コンピュータプログラム (computer program)

コンピュータが行うべき処理を順序立てて記述したもの。広義の「ソフトウェア」の一部であるが、実用上はプログラムとソフトウェアはほとんど同義のように扱われることが多い。

現代のコンピュータではプログラムは一定の形式に従ってデータとして表現され、記憶装置(メインメモリ)に格納される。実行時にはCPU(中央処理装置)がプログラムに記述された命令を順番に読み出して解釈・実行していく。

プログラムを作成する作業や工程を「プログラミング」(programming)、これを行う人や職種のことを「プログラマ」(programmer)という。人間がプログラムを記述する際には、人間が理解しやすい人工言語である「プログラミング言語」(programming language)を使うことが多い。プログラミング言語で記述されたプログラムを「ソースコード」(source code)という。

ソースコードはコンピュータが解釈・実行することができないため、コンパイラなどの変換ソフトによってコンピュータが解釈・実行できる機械語(マシン語)などで構成された「オブジェクトコード」(object code)に変換されてから実行される。スクリプト言語のように、この変換処理を開発時には行わず、実行時にインタプリタなどのソフトウェアによって動的に行う場合もある。

狭義には、プログラミング言語やそれに相当する仕組みや道具を用いて、人間が読み書きしやすい形式のプログラム(ソースコード)を記述していく「コーディング」(coding)作業を指す。広義には、その前後に行われる、設計や試験(テスト)、修正(デバッグ)、実行形式や配布形式への変換(コンパイルやビルドなど)といった一連の作業を含む。プログラミングを行う人や職種のことを「プログラマ」(programmer)という。

プログラムの作成

プログラミングを行うには、まず何をするプログラムを作るのかを明確に定義し、仕様や要件を自然言語で記述したり、大まかな処理の流れを箇条書きやフローチャートなどの図表を用いて設計する。集団でソフトウェア開発を行う場合はプログラムの記述者とは別の設計者が専門に作業を行い、仕様書や設計書などの形でまとめる場合もあるが、個人が小規模のプログラムを作成する場合はこの工程を頭の中で行い、作業や手順としては省略する場合もある。

どんなプログラムを作りたいか決まったら、これをコンピュータが解釈できるプログラミング言語を用いてソースコードとして記述していく。言語やプログラムの記述法には様々な種類があるが、手続き型の言語(手続き型プログラミング)の場合、実行すべき命令を先頭から順に書き下していく。必要に応じて、複数の命令をひとまとめにして名前をつけて呼び出せるようにしたり(関数やサブルーチンなど)、条件分岐や反復(繰り返し)などで命令の流れの制御を行う。

プログラムの実行

ソースコードそのものはコンピュータ(の処理装置)が解釈・実行できる形式ではないため、これを機械語(マシン語)のプログラムなど実行可能な形式に変換する必要がある。ソースコードを機械語などのコード(オブジェクトコード)に変換する工程をコンパイル(compile)と呼び、プログラムの起動処理やライブラリなど実行に必要なコードを連結する工程をリンク(link)という。これら一連の工程を行って実行可能ファイルやパッケージを作ることをビルド(build)という。

スクリプト言語(軽量言語)などの場合はこうした明示的な変換工程は不要で、ソースコードを機械語に変換しながら同時に実行するインタプリタなどの処理系で直に実行することができる。記述したコードをすぐ実行でき手軽だが、変換しながら実行するため実行可能ファイルを生成する場合より実行速度やメモリ効率では劣る。

プログラムの修正

作成したプログラムが一度で完全に思い描いたとおりに動作する場合もあるが、大抵は何らかの誤りや不具合を抱えているものである。このため、ビルドしたプログラムを実行してみてテスト(動作試験)を行い、仕様通りに動くか調べる。

誤り(バグ)が発見されると原因や解決策を考え、正しく動作するようにプログラムを書き換える(デバッグ)。バグには単純な記述ミスのようなものから、そもそも解くべき問題に対して選択した計算手順(アルゴリズム)が合っていないといった根本的なレベルのものまで様々な種類がある。

デバッグ作業が完了したら再びビルドとテストを行い、誤りが正されていることを確認する。このビルド→テスト→デバッグの繰り返しによって次第にプログラムの完成度や品質が上がっていき、実際に実用可能なプログラムに仕上げることができる。実際のプログラミングにおいては作業時間の多くがこの繰り返しの工程に費やされる。

ITの分野では、コンピュータプログラムの設計やアルゴリズム(計算手順)の理解などのために、内部で行われる処理や演算の詳細な流れをフローチャートに表すことが多い。プログラムに限らず、業務手順など様々な過程や手順の図示に応用できる。

一つのフローチャートには開始と終了があり、その間に一つ以上の工程が含まれる。流れは分岐や繰り返しによって複数に枝分かれしたり戻ったりすることがあるが、途中どのような経路を通っても必ず一つの開始から始まって一つの終了で終わる。

フローチャートで用いる部品の種類や図記号の形状はJIS X 0121で規格化されており、一般的にはこれを用いることが多い。主な部品として、開始や終了を表す「端子」(円・楕円・角丸長方形)、「処理」(長方形)、プログラムにおけるサブルーチンや関数などの「定義済み処理」(左右が二重線の長方形)、「入出力」(平行四辺形)、条件分岐などの「判断」(菱形)、繰り返しの範囲を示す「ループ端」(開始は上側、終了は下側の角が欠けた長方形)、他の図との出入り口を示す「結合子」(小さな丸)、処理の流れを示す「線」(右や下へは線分・左や上には矢印)などがある。

プログラミング言語でプログラムを開発することを「プログラミング」(programming)、プログラミング言語で記述したプログラムを「ソースコード」(source code)という。語彙、文法、記法などが自然言語よりも厳密に定義されており、記述したソースコードはソフトウェアによって自動的に解析、処理、変換などすることができる。

コンパイラとインタプリタ

プログラミング言語は人間にとって理解、記述しやすい語彙や文法で構成された言語であり、そのままではコンピュータ(のCPU)が解釈、実行することができないため、ソフトウェアによってCPUが実行可能な言語(機械語、マシン語)によるプログラムに変換して実行される。

開発時や導入時などに一度にまとめて変換処理を行うことを「コンパイル」(compile)、そのような変換ソフトを「コンパイラ」(compiler)という。実行時に変換と実行を同時並行で行うソフトウェアを「インタプリタ」(interpreter)という。

高水準言語と低水準言語

プログラミング言語は人間にとっての理解のしやすさや機械語に対する抽象度の高さによって分類されることがあり、機械寄りの言語を「低水準言語」(low-level language)あるいは「低級言語」と呼び、人間寄りの言語を「高水準言語」(high-level language)あるいは「高級言語」という。

機械語の命令コードと一対一に対応する命令語を用いてプログラミング言語を行う低水準言語のことを特に「アセンブリ言語」(assembly language)と呼び、機械語への変換ソフトを「アセンブラ」(assembler)という。

プログラミングパラダイム

プログラムをどのようなものとして捉え、構築していくかについて一定の設計思想やルールがある場合が多く、これを「プログラミングパラダイム」(programming paradigm)という。複数の書き方が可能な言語は「マルチパラダイム」であるという。パラダイムに基いて言語を分類することもある。

手続きを順番に記述していく「手続き型言語」(procedural language)あるいは「命令型言語」(imperative language)や、関連するデータ群と手続き群を一つのまとまりとして捉える「オブジェクト指向言語」(object-oriented language)、プログラムを関数の組み合わせとして捉える「関数型言語」(functional language)、データ間の関係や論理を記述していく「論理型言語」(logic programming language)などの種類がある。

また、主な利用目的や主要な処理系の実装方式により分類することもあり、記述や実行の手間を軽減して迅速にプログラム開発ができる「スクリプト言語」(script language)あるいは「軽量言語」(LL：Lightweight Language)、特定の分野や処理に特化した「ドメイン固有言語」(DSL：Domain Specific Language)などの分類がある。

ITの分野では、ある特定の機能を持ったコンピュータプログラムを他のプログラムから呼び出して利用できるように部品化し、そのようなプログラム部品を複数集めて一つのファイルに収納したものをライブラリということが多い。

一般的に、ライブラリにはオブジェクトコード(機械語などで記述された実行可能形式のプログラム)が格納されているが、それ単体で起動して実行することはできず、他の実行可能ファイルに連結されて利用される。言語や処理系によってはソースコードの集合をライブラリという場合もある。

様々なプログラムが共通して利用する汎用性の高い機能などがライブラリとして開発・提供されることが多く、標準的なライブラリはオペレーティングシステム(OS)やプログラミング言語の開発環境、開発ツールなどの一部として付属することが多い。

特定のソフトウェアやハードウェアを利用したプログラムを開発するために必要な機能がライブラリの形でまとめられている場合もあり、当該システムのソフトウェア開発キット(SDK)などの一部として開発者に提供される。

また、部品化されたコンピュータプログラム以外にも、特定の分野や形式のデータなどを検索、取得、再利用しやすい形にまとめたファイルやデータベース、Webサイトなどのことを「フォトライブラリ」「音声ライブラリ」などといったように呼ぶことがある。

個々のソフトウェアの開発者が毎回すべての機能をゼロから開発するのは困難で無駄なため、多くのソフトウェアが共通して利用する機能は、OSやミドルウェアなどの形でまとめて提供されている。

そのような汎用的な機能を呼び出して利用するための手続きを定めたものがAPIで、個々の開発者はAPIに従って機能を呼び出す短いコードを記述するだけで、自分で一から処理内容を記述しなくてもその機能を利用したソフトウェアを作成することができる。

広義には、プログラミング言語の提供する機能や言語処理系に付属する標準ライブラリの持つ機能を呼び出すための規約などを含む場合もある(Java APIなど)。

また、APIを経由して機能を呼び出す形でプログラムを構成することにより、同じAPIが実装されていれば別のソフトウェア上でそのまま動作させることができるのも大きな利点である。実際、多くのOS製品などでは同じ製品の旧版で提供していたAPIを引き継いで新しいAPIを追加するという形で機能を拡張しており、旧バージョン向けに開発されたソフトウェアをそのまま動作させることができる。

APIの形式

APIは人間が記述・理解しやすい形式のプログラムであるソースコード上でどのような記述をすべきかを定めており、原則としてプログラミング言語ごとに定義される。

関数やプロシージャなどの引数や返り値のデータ型やとり得る値の意味や定義、関連する変数や定数、複合的なデータ構造の仕様、オブジェクト指向言語の場合はクラスやプロパティ、メソッドの仕様などを含む。

通信回線を通じて遠隔から呼び出すような構造のものでは、送受信するパケットやメッセージの形式、通信プロトコル(通信規約)などの形で定義される仕様をAPIと呼ぶこともある。

Web API

近年ではネットワークを通じて外部から呼び出すことができるAPIを定めたソフトウェアも増えており、遠隔地にあるコンピュータの提供する機能やデータを取り込んで利用するソフトウェアを開発することができる。

従来は通信を介して呼び出しを行うAPIはRPC(リモートプロシージャコール)の仕様を元に製品や環境ごとに個別に定義されることが多かったが、インターネット上でのAPI呼び出しの場合は通信にHTTPを、データ形式にXMLやJSONを利用するWeb APIが主流となってきている。

2000年代前半まではWeb APIの標準として仕様が巨大で機能が豊富なSOAPの普及が試みられたが、2000年代中頃以降は軽量でシンプルなRESTful APIが一般的となり、狭義のWebアプリケーションだけでなく様々な種類のソフトウェアやネットサービス間の連携・接続に幅広く用いられるようになっている。

APIと実装

API自体は外部からの呼び出し方を規定した決まりごとに過ぎず、呼び出される機能を実装したライブラリやモジュールなどが存在して初めてAPIに挙げられた機能を利用することができる。

あるソフトウェアのAPIが公開されていれば、同じAPIで呼び出すことができる互換ソフトウェアを開発することもできる。ただし、APIを利用する側のプログラムが(スクリプトなどではなく)バイナリコード(ネイティブコード)の場合にはこれをそのまま動作させることはできないのが一般的で、同じソースコードを元に互換環境向けにコンパイルやビルドをやり直す必要がある(ソースレベル互換)。

また、API自体は標準実装における動作の詳細までは定義していないため、APIが同一の互換ソフトウェアだからといって動作や振る舞いがまったく同じであるとは限らない。商用ソフトウェアの場合はAPIが非公開だったり、すべては公開されていなかったりすることが多く、公開情報だけではAPI互換の製品を作ることも難しい。

APIと知的財産権

従来は特許で保護されている場合を除いて、APIそのものには著作権その他の知的財産権は存在しないとする見方が一般的で、実際、元のソフトウェアのコードを複製せずすべて独自に実装するという方法でAPI互換ソフトウェアが数多く開発されてきた。

ところが、米オラクル(Oracle)社が権利を有するJava言語やその処理系に関して、米グーグル(Google)社が同社の許諾を得ずにAndroidスマートフォン向けにJava APIを実装した実行環境(Dalvik VM)を開発・提供しているのは著作権侵害であるとの裁判が起こされ、米裁判所は訴えを認める判決を出した。今後はAPIの権利について従来の状況が変化していく可能性がある。

変数につけた名前を「変数名」と呼び、記憶されているデータをその変数の値という。データの入れ物のような存在で、プログラム中で複数のデータを扱いたいときや、同じデータを何度も参照したり計算によって変化させたい場合に利用する。

変数をプログラム中で利用するには、これからどんな変数を利用するかを宣言(declaration)し、値を代入(assignment)する必要がある。コード中で明示的に宣言しなくても変数を利用できる言語もある。変数に格納された値を利用したいときは、変数名を記述することにより値を参照(reference)することができる。

変数の型

プログラム中で扱うデータは整数、浮動小数点数、文字列など様々なデータ型に分かれており、変数も特定のデータ型を持つ。多くの言語では宣言時に一つのデータ型を指定しなければならず、後から型は変えられないが、特定の型を指定しなくても処理系が適切な型を適用(型推論)してくれる言語や、代入などによって途中で型を切り替えることができる言語もある。

変数のスコープ

変数は宣言した位置などにより通用する範囲(スコープ)が決まっており、範囲の外から参照や代入を行うことはできない。プログラム全体を通用範囲とするものを「グローバル変数」(大域変数)、特定のサブルーチンや関数、メソッド、コードブロックなどの中でのみ通用するものを「ローカル変数」(局所変数)という。オブジェクト指向言語では「クラス変数」や「インスタンス変数」などに分かれる。

プログラミング言語では言語仕様などで様々な演算子が定義されており、これを組み合わせて式や命令文を構成することができる。対象となる被演算子の数によって、「a++」のように一つしか取らないものを「単項演算子」(unary operator)、「a+b」のように二つのものを「二項演算子」(binary operator)、「c?x:y」のように三つのものを「三項演算子」(ternary opeator)、任意個の被演算子を列挙できるものを「多項演算子」(n-ary operator)という。

演算子は演算の内容によっても分類でき、「a-b」「x/10」のように四則演算などの算術的な計算を記述する「算術演算子」(arithmetic operator)、「a>b」「x==y」のように二項の比較や関係を表す「比較演算子」(comparison operator)あるいは「関係演算子」(relational operator)、「a&&b」「x||y」のように論理演算を行う「論理演算子」(logic operator)などがある。

多くの言語では演算子は言語仕様で定義されており開発者が任意に追加、削除、変更することはできないが、言語によってはコード中で独自の演算子を定義して利用することができたり、既存の演算子に別の演算内容を割り当てる「多重定義」(オーバーロード)ができる場合もある。

コンピュータのCPUがプログラムを実行する際、特に指定がなければプログラムを先頭から読み込んで命令を並んでいる順に従って一つずつ実行していく。この最も基本的な命令実行の制御構造を、(他の構造と対比するため便宜的に)順次構造と呼ぶ。

一方、命令の中には命令実行の流れを変更するものもある。これを用いて、条件に従って別の実行位置に流れを分岐させる制御構造を「選択構造」あるいは「分岐構造」、条件が満たされる間だけ同じ個所を繰り返し実行する制御構造を「反復構造」あるいは「繰り返し構造」という。

コンピュータのCPUがプログラムを実行する際、特に指定がなければ命令を先頭から順に実行するが、分岐命令が存在する場合、特定の条件が満たされたらメモリの指定番地に実行位置を変更(ジャンプ)し、以降はそこから順に命令を実行していく。

このような実行制御を「条件分岐」と呼び、プログラムに複雑な処理をさせたい場合は必須の機能となる。一方、条件が満たされる間だけ同じ個所を繰り返し実行する制御構造もあり、「反復構造」あるいは「繰り返し構造」という。

コンピュータのCPUがプログラムを実行する際、特に指定がなければ命令を先頭から順に実行するが、反復構造になっている場合、指定の条件が満たされている間、指定範囲の末尾の命令を実行したら範囲の先頭に戻り、その範囲を繰り返し実行する。

同じ処理を様々な対象に次々に適用したい場合などに用いられ、プログラムに複雑な処理をさせたい場合には必須の機能となる。一方、特定の条件が満たされたらメモリの指定番地に実行位置を変更(ジャンプ)する制御構造もあり、「選択構造」あるいは「分岐構造」という。

曖昧さのない単純で明確な手順の組み合わせとして記述された一連の手続きで、必ず有限回の操作で終了し、解を求めるか、解が得られないことが示される。コンピュータで実行する場合は、基礎的な演算、値の比較、条件分岐、手順の繰り返しなどを指示する命令を組み合わせたプログラムとして実装される。

数値などの列を大きい順または小さい順に並べ替える「整列アルゴリズム」、たくさんのデータの中から目的のものを探し出す「探索アルゴリズム」、データが表す情報を損なわずにより短いデータに変換する「圧縮アルゴリズム」といった基本的なものから、画像の中に含まれる人間の顔を検出する、といった複雑なものまで様々な種類のアルゴリズムがある。

同じ問題を解くアルゴリズムが複数存在することもあり、必要な計算回数や記憶領域の大きさ、手順のシンプルさ、解の精度などがそれぞれに異なり、目的に応じて使い分けられる。例えば、ある同じ問題に対して、原理が単純で簡単にプログラムを記述できるが性能は低いアルゴリズム、計算手順が少なく高速に実行できるが膨大な記憶領域を必要とするアルゴリズム、厳密な解を求めるものより何桁も高速に近似解を求めることができるアルゴリズムなどがある。

データの探索

何らかのデータ形式やデータ構造として集められたデータの集合に対して、一定の手順に基づいて指定の条件を満たすデータを探し出し、一致したデータやその位置を明らかにする(あるいは対象の中には存在しないことを確定させる)操作のことを「探索」(search)という。

探索アルゴリズム

コンピュータなどで実行できるよう定式化された探索手順のことを「探索アルゴリズム」(search algorithm)という。例えば、最も単純な方法として、一列に並べたデータ列に対して端から順に指定の条件に一致するか照合する方法がある。これを「線形探索」(linear search)という。

また、順位や大小が比較できるデータ群であれば、大きい順または小さい順に整列(並べ替え)して、目的のデータと半分の位置にあるデータを比較すれば、含まれる方の半分に絞り込むことができる。残ったデータ群の半分の位置と比較すれば、もう半分に絞り込める。これを繰り返して残りが一つになれば探索完了となる。この方法は「二分探索」(binary search)と呼ばれる。

線形探索では一回の比較で一つしか候補が減らないため、平均してデータの個数に比例した回数の比較が必要となる(これを $O\left(n\right)$ と表記する)が、二分探索ならば一回の比較で候補を半分に減らせるため、平均してデータの個数の2を底とした対数で済む(これを $O\left(\log n\right)$ と表記する)。

このように、探索する対象の特性に適したアルゴリズムを選択することで効率的に探索を行うことができる。文字列内の特定のパターンを探索するためのアルゴリズムや、木構造やグラフなどのデータ構造に格納された要素を探索するためのアルゴリズムなどがよく知られている。

検索との違い

ITの分野では「検索エンジン」「全文検索」のようにデータ群から条件に一致するものを探し出す操作を「検索」と呼ぶこともある。いずれも英語では “search” であり、意味や用法に明確な違いはないが、慣例として情報科学などの学問分野では「探索」の語が、探索法を応用した具体的なシステムやサービスなどでは「検索」の語が好まれる。

最も単純なアルゴリズムで、配列などに格納されたデータ列の中から、まず先頭の要素を探しているデータと比較する。一致しなければ2番目の要素と比較する。これを末尾の要素まで繰り返し、途中でデータを発見したらそこで探索を終了する。

N個のデータ列の中から線形探索する場合、最良のケースは先頭の要素と一致する場合で比較回数は1回、最悪のケースは末尾まで探してもデータが見つからなかった場合で比較はN回、平均の比較回数はN/2回となる。比較回数の平均値は要素数に正比例して増大する。

仕組みが単純なため短いプログラムコードで記述でき、コードを読んだ人が処理を理解しやすく、探索対象のデータ列以外に余分な記憶領域を消費せず、事前にデータ列のソート(大きい/小さい順に並べ直す処理)などの前処理を行う必要がないという利点がある。より高度なアルゴリズムに比べると平均の比較回数は多く、性能の高いアルゴリズムとは言えない。

まず、データを降順(大きい順)あるいは昇順(小さい順)に並べ替え、探索したいデータが中央の要素より大きいか小さいかを調べる。これにより、データが全体の前半分にあるか後ろ半分にあるかを判定することができるため、存在しない側の半分は探索範囲から外すことができる。

半分になったデータ群の中央の要素と再び比較し、前半と後半のどちらにあるかを調べる。この操作を繰り返し行うことで、一回の操作ごとに探索範囲の大きさが半分になっていき、中央の要素が求めるデータに一致するか、探索範囲の要素数が一つになる(求めるデータは見つからなかったことが確定する)と探索は終了する。

値の大小は文字の索引順の前後関係などに適宜置き換えることにより、順序と比較手段を定義できればどのようなデータにも適用することができる。

n個のデータ群から平均でlog₂n回の比較で探索を終えることができ、例えば1000個のデータを10回の比較で探索できる。原理は単純ながら高速なアルゴリズムである。ただし、要素があらかじめ整列済みである必要があるため、未整列のデータに適用するにはソートの分の計算時間も必要となる。

複数の同じ種類の要素が一列に並んでいる場合に、すべての要素に一律に適用可能な順序の規則を用いて並べ替える操作を意味する。数値と日付のように異なる種類の要素が混在していたり、要素間にじゃんけんの出し手のような循環的な関係性がある場合には正しく整列することができない。

数を小さい方から大きい方へ並べる順序を「昇順」(ascending order)、その逆を「降順」(descending order)という。数以外の場合、アルファベットを「A」から「Z」へ、読み仮名を「あ」から「ん」へ、日付や時刻を古い方(過去)から新しい方(未来)へといったように、本来の並び順や自然な順序を昇順、逆を降順という。

ソートアルゴリズム

コンピュータによるデータ処理でもソートは頻繁に用いられる操作で、整列手順を定式化したものを「ソートアルゴリズム」(sorting algorithm)という。古くから活発に研究され様々な手法が考案されており、計算回数の少なさ(高速さ)や必要な記憶装置の容量、手順のシンプルさ(プログラムの短さ)などが異なる。

平均的に効率が良く、広く用いられるのは「クイックソート」(quick sort)と呼ばれる手法で、要素数がn倍になると平均の計算時間が n×log₂n 倍になる。プログラミング言語に標準で組み込まれた配列を整列する関数などによく採用されている。

データ列に同じ値が含まれる場合、その出現順がソート前後で変わらない手法を「安定ソート」(stable sorting)、保存されるとは限らない(順序が入れ替わることがある)手法を「不安定ソート」(unstable sorting)という。

また、元のデータ列の格納領域のみを用いて操作が完結する手法を「内部ソート」(in-place sorting)、外部に別の領域を確保する必要がある手法を「外部ソート」(external sorting)という。組み込みシステムなど利用できるメモリ領域が限られる場合には、高速性よりも内部ソートであることが重視されることもある。

データの並べ替え(ソート)における順序の指定などに用いられる概念で、小さい方から大きい方へ、あるいは本来の並び順における先頭側から末尾側へ「昇(のぼ)っていく」順序のことを意味する。

数字であれば1、2、3…と小さい値から大きい値へ、アルファベットであれば「A」から「Z」に向けて、カナであれば「ア」から「ン」に向けて、日付や時刻であれば過去側・古い側から未来側・新しい側に向けて並べる順序である。

一方、大きい方から小さい方へ、あるいは本来の並び順とは逆に並べる順序は「降順」(descending order)という。「9、8、7」「Z、Y、X」「ん、を、わ」といった本来とは逆の並び順のことである。

データの並べ替え(ソート)における順序の指定などに用いられる概念で、大きい方から小さい方へ、あるいは本来の並び順における末尾側から先頭側へ「降(お)りていく」順序のことを意味する。

数字であれば9、8、7…と大きい値から小さい値へ、アルファベットであれば「Z」から「A」に向けて、カナであれば「ン」から「ア」に向けて、日付や時刻であれば未来側・新しい側から過去側・古い側に向けて並べる順序である。

一方、小さい方から大きい方へ、あるいは本来の並び順の通りに並べる順序は「昇順」(ascending order)という。「1、2、3」「A、B、C」「あ、い、う」といった本来定められた並び順のことである。

すべての要素について隣接する要素と大きさを比較し、並べたい順番と逆転していたら両者を入れ替える。この手順を最高で要素数-1回繰り返すと並べ替えが完了する。要素の入れ替えが発生しなくなった時点で処理を打ち切ってもよい。

一般的な実装では、この処理を列の一方の端から反対の端まで順番に行うことが多く、繰り返しの度に未整列の要素の中で最も大きな(あるいは小さな)要素が列の端に移動していく様子を泡(バブル)が浮き上がっていく様に例えてこのような名称となった。

最良の場合の計算時間は O(n) と高速だが、最悪の場合の計算時間は O(n²) と整列法の中でも最も遅い部類に入り、平均して高速な手法とは言えない。ただし、要素の比較・交換は順序を問わず並列化しやすいという特徴があり、並列分散処理が可能な環境では高速化することができる。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート(内部ソート)で、同じ大きさの要素の順序が入れ替わらない安定ソートである。アルゴリズムの理解や実装が容易で、コードの記述量が少ない。実用上はあまり使われないが、整列法の学習ではほぼ必ず取り上げられ、効率化した派生アルゴリズムも多く考案されている。

数値の列を先頭から小さい順(昇順)に並べる場合を考える。まず、先頭から末尾までの間で最も小さい値を見つけ、先頭の値と交換する。次に2番目から末尾までの間で最も小さい値を見つけ、2番目の値と交換する。

以降も同様に、「n番目から末尾までで最も小さい値を見つけ、n番目と入れ替える」という操作を繰り返す。これを末尾の一つ前の値まで繰り返せば、先頭が最も小さく末尾が最も大きい数値の列が得られる。

列の元の状態によらず O(n²) の計算量がかかるため処理時間の予測はしやすいが、ソートアルゴリズムの中では最も遅いものの一つに分類される。木構造の一種である二分ヒープ木を用いて改良した手法を「ヒープソート」(heap sort)という。

整列したいデータ列以外の記憶領域を用意しなくてよいインプレースソート(内部ソート)で、同じ大きさの要素の順序の維持は保証されない不安定ソートである。挿入ソートなどと同じように、アルゴリズムの理解や実装が容易なため、対象データ列が短いことが分かっている場合などに利用されることがある。