データをきれいに並べ替えたいときって、ありますよね。テストの点数が高い順に友だちを並べてみたり、好きなゲームの成績をスコア順で見たり。この「並べ替え」の処理のことを「ソート」って呼ぶんです。スマートフォンのアプリでもWebサイトでも、毎日どこかでソートが活躍しているんですよ。この記事では、ソートがどういう仕組みで動いているのか、そして現実でどんなふうに役立っているのかを、くわしく説明していきます。読み終わったら「あ、あのときあれはソートだったんだ」って思うこと、きっとたくさんありますよ。
- ソートはデータを順番に並べ替える処理で、日常生活の中で無意識に使われている
- LINEやInstagram、Amazonなど多くのアプリやWebサイトで活躍している
- ソートアルゴリズムと呼ばれるいろいろな方法があり、効率性が異なる
もうちょっと詳しく
ソートって聞くと難しく思うかもしれませんが、実は毎日のように自分たちも使っているんです。物を整理するときの基本的な作業ですから。トランプを大きい数字順に並べるのもソートですし、クラスの身長順の並び替えもソートなんですよ。コンピュータの世界では、このような「きれいに並べる」という作業を、ルール化して自動的にやらせるわけです。だから、たくさんのデータを素早く正しく並べ替えられるんですね。
ソート=「データを比較して入れ替える」の繰り返し
⚠️ よくある勘違い
→ 実は毎日使っています。SNSで「新しい順」に見たり、オンラインショップで「安い順」に探したりするのはすべてソート。自分たちが使いやすいように、プログラマーたちがバックグラウンドでソートを使ってるんです。
→ アプリやWebサイトが快適に使えるのは、ソートがあるからこそ。プログラミングを勉強する人には重要なテーマですが、ユーザーとしても「ああ、これはソートなんだ」と気づくことで、テクノロジーの仕組みが見えてくるんです。
[toc]
ソートって何だろう？基本から始めよう
ソートの意味をかんたんに
ソートというのは、英語で「sort」と書きます。意味は「並べる」「整理する」という意味なんですよ。コンピュータの世界では、このソートという言葉を使ってデータの並べ替えを表します。つまり、バラバラな状態のデータを、何らかのルールに基づいて整列させることですね。
身近な例でいうと、あなたが教室の前に立って「身長が小さい人から大きい人へ並んでください」と言ったとします。すると、みんなが自分たちの身長を比べて、小さい人から順に並び直しますよね。あれが「ソート」なんです。コンピュータも、これと同じような処理を数百万のデータに対してやってるんですよ。すごいでしょ。
日常生活の中のソート
あなたが毎日使っているアプリやWebサイトで、実はソートが活躍しているんです。例えば、LINEでチャット一覧を見ると「最新のメッセージから順に」表示されていますよね。あれはソートです。古いチャットから順に表示するようにもできるし、未読メッセージを優先的に上に出すこともできます。すべて「ソート」のおかげで、好きな順番に並べ替えられるんですよ。
Instagramで「いいね」が多い順に写真を並べるのもソート。Amazonで「値段が安い順」「評価が高い順」に商品を表示するのもソート。YouTubeで「アップロード日が新しい順」に動画を並べるのもソート。こんなふうに、毎日いろいろなアプリやWebサイトで、ソートが使われているんです。
もう一つの例として、Twitterを見てください。タイムラインに表示されるツイートって、あなたが見やすいように、アルゴリズムで「おすすめ順」に並べ替えられてるんです。これも、ある意味ではソートなんですよ。つまり、ソートって言葉は「大小順に並べる」という狭い意味だけじゃなくて、「何らかのルールに基づいて整列させる」という広い意味で使われることもあるんです。
ソートの種類と特徴を知ろう
簡単だけど遅い「バブルソート」
ソートにはいろいろな方法があります。その中で、一番わかりやすいのが「バブルソート」という方法です。バブルというのは「泡」という意味なんですが、水に入れた泡が上へ浮かぶイメージでデータが入れ替わっていくから、こういう名前がついてるんですよ。
バブルソートのやり方はこんな感じです。まず、最初の数字と次の数字を比べます。大きい方が後ろに来るべきなら、入れ替えます。そして、その次の数字と比べて、また入れ替えるか判断する。この作業を、すべての数字がきちんと並ぶまで繰り返すんです。例えば「5、3、8、1、9」を小さい順に並べるなら：
最初は「3、5、1、8、9」、次は「1、3、5、8、9」という具合に、少しずつきちんとした順序に近づいていくんですよ。泡が一つずつ浮かぶように、大きい数字が後ろへ動いていく。だからバブルソートって呼ぶわけですね。
でも、バブルソートには欠点があります。データ数が多いと、ものすごく時間がかかるんです。100個のデータなら大丈夫ですが、100万個のデータだと何分もかかっちゃう。だから、実際のアプリやWebサイトではあんまり使われていないんです。ただし、プログラミングの勉強では「ソートの基本を理解するのに最適」だから、よく取り上げられるんですよ。
バランスの良い「クイックソート」
バブルソートは遅いので、プログラマーたちは「もっと速いソート方法がないか」と考えました。その中で、よく使われているのが「クイックソート」という方法です。クイックというのは「素早い」という意味なので、名前の通り速いんですよ。
クイックソートのやり方は、バブルソートとは全然違います。まず、データの中から一つの値を選びます。これを「基準値」（きじゅんち）と言います。つまり、このデータを中心に、左と右に分けるんですよ。そして、基準値より小さいデータは左に、大きいデータは右に分けます。その後、左側と右側でも同じ作業を繰り返すんです。
例えば「5、3、8、1、9」を小さい順に並べるなら、5を基準値にして「左に3、1」「右に8、9」に分けます。そして、左側の「3、1」に対しても同じ作業をして、右側の「8、9」に対しても同じ作業をする。こんなふうに「大きな問題を小さな問題に分ける」ことで、速く並べ替えられるんですよ。
クイックソートが速い理由は、大量のデータでも効率的に分割できるからです。100万個のデータでも、数秒で並べ替えられます。だから、現在のアプリやWebサイトでは、このクイックソートが使われることが多いんですよ。ただし、最悪の場合にはバブルソートと同じくらい遅くなることもあるので、完璧ではないんです。
その他の「マージソート」や「ヒープソート」
クイックソート以外にも、有名なソート方法があります。その一つが「マージソート」です。マージというのは「合わせる」という意味なんですよ。このソートのやり方は、データを二つに分けて、それぞれを並べ替えてから、二つを合わせるという方法なんです。
例えば「5、3、8、1、9」なら、「5、3」と「8、1、9」に分けます。「5、3」を並べ替えて「3、5」にして、「8、1、9」を並べ替えて「1、8、9」にして、最後に二つを合わせて「1、3、5、8、9」にするわけです。
マージソートの特徴は「どんなデータでも速い」ということです。最悪の場合でも速度が変わらないので、安定性が高いんですよ。ただし、データを一時的に保存するための余分なメモリが必要になるので、メモリが限られている場合には向きません。
また、「ヒープソート」というものもあります。ヒープというのは「山積み」という意味なんですが、ツリー状に組み合わせたデータ構造を使ってソートするんです。これも、最悪の場合でも速い方法として知られています。
実際のアプリやWebサイトでは、どんなソートが使われてるの？
検索サイトとソート
Googleで何か検索するときを想像してみてください。「ラーメン 近い順」と検索すると、あなたの場所から近い順にラーメン屋さんが表示されますよね。あれはソートです。システムが何千ものラーメン屋さんのデータから、あなたの場所からの距離を計算して、近い順に並べ替えているんですよ。
また、「ラーメン 評価が高い順」と検索すると、星の数が多い順に表示されます。「ラーメン 最新のお店から」と検索すると、最近オープンしたお店から順に表示される。すべて、ソートのおかげで、あなたが知りたい情報が上に来るんですよ。
SNSとソート
Instagramで「いいね」が多い順に写真を見たいなら、そう設定することができます。または「最新の投稿から」という順番もあります。TikTokは「おすすめ順」に動画を表示してますよね。この「おすすめ順」というのは、ソート＋人工知能（AI）を使って、あなたが好きそうな動画を上に来るようにしているんです。
オンラインショッピングとソート
Amazonで「値段が安い順」に商品を並べるのもソート。「レビューの評価が高い順」に並べるのもソート。「新しい商品から」に並べるのもソート。同じ商品でも、並べ替えの方法を変えると、買い物客の見え方が変わるんですよ。だから、オンラインショップとしては「この並べ替え方なら、お客さんが買いやすいな」という順番を工夫しているんです。
なぜソートって大事なの？
データが多い時代だからこそ
今は「ビッグデータの時代」と言われています。つまり、毎日、膨大な量のデータが生まれているんですよ。スマートフォンで検索するたびに、SNSに投稿するたびに、オンラインショップで買い物するたびに、データが増えていきます。
こんなにたくさんのデータの中から、あなたが欲しい情報を見つけるには、どうすればいいと思いますか？その答えが「ソート」なんです。ソートで「新しい順」「人気順」「値段が安い順」などに並べ替えることで、あなたが探している情報が上に来るようにしてるんですよ。
効率の問題
また、プログラマーにとっては「効率」が大事です。バブルソートで100万個のデータを並べ替えるのに10分かかるなら、クイックソートなら1秒で終わるかもしれません。その差は、ユーザーの快適性に大きく影響するんですよ。だから、プログラマーたちは「どのソート方法を使えば、一番速く正確にできるか」を常に考えているわけです。
社会への影響
実は、ソートって社会にも影響を与えているんです。例えば、Googleの検索結果の順番を変えるだけで、あるWebサイトへのアクセス数が大きく変わります。Instagramで「おすすめ順」の基準を変えるだけで、どの投稿が人気になるか変わってしまう。Amazonの「売上ランキング」の並べ替え方が変わると、どの商品が売れるか変わるんですよ。つまり、ソートという技術は、目に見えないけれど、社会全体に大きな影響を与えているんです。