Skip to Content
学習アルゴリズム
book

学習アルゴリズム

by George Heineman
March 2025
Intermediate to advanced
280 pages
4h 16m
Japanese
O'Reilly Media, Inc.
Content preview from 学習アルゴリズム

第5章. 帽子なしのソート

この作品はAIを使って翻訳されている。ご意見、ご感想をお待ちしている:translation-feedback@oreilly.com

この章では、配列のN個の値を昇順に並べ替えるアルゴリズムを紹介する。ソートされた順序で値の集合を整理することは、多くのプログラミングの効率を向上させるために不可欠な最初のステップである。ソートはまた、従業員の名前と電話番号が記載された会社のディレクトリを印刷したり、空港のディスプレイに飛行機の出発時刻を表示したりするような、多くの実世界のアプリケーションでも必要である。

並び順のない配列の場合、値の検索は最悪の場合O(N)である。配列がソートされている場合、バイナリ配列検索は、最悪の場合、O(log N)のパフォーマンスで目的の値を見つけることができる。

スワップによるソート

図5-1の一番上にある配列、A の値をソートしてみよう。鉛筆を使って、図5-1の値を紙にコピーしてみよう(あるいはペンを持ってきて、このページに書き込んでみよう!)。配列中の2つの値の位置を繰り返し入れ替えることで、これらの値を昇順にソートすることに挑戦する。最も少ないスワップ回数は何回だろうか?また、2つの値を比較した回数もカウントしてみよう。私はこれらの値を5回のスワップでソートした。もっと少なくすることは可能か?1

Sort these values
図5-1. サンプル配列、A 、ソートする。

スワップの回数をカウントすることも重要だが、2つの値の比較回数もカウントする必要がある。手始めに、A 、たった7回の比較で、2が最小の値であることがわかる。これは第1章で示したとおりである。最小値はA[3] で発見されたので、A[0] と入れ替える。これにより、最小の値は本来あるべき配列の先頭に移動する。図5-1では、スワップされた値をハイライトしている。太字の枠は、最終的な位置にあることが保証されている値をマークするために使っている。太字の枠の外側の値はすべてソートされる。

残りの値をスキャンして最大の値24を発見し(6つの比較を使用)、 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.

Read now

Unlock full access

More than 5,000 organizations count on O’Reilly

AirBnbBlueOriginElectronic ArtsHomeDepotNasdaqRakutenTata Consultancy Services

QuotationMarkO’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.
Julian F.
Head of Cybersecurity
QuotationMarkI wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.
Addison B.
Field Engineer
QuotationMarkI’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.
Amir M.
Data Platform Tech Lead
QuotationMarkI'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
Mark W.
Embedded Software Engineer

You might also like

データサイエンスのための実践線形代数

データサイエンスのための実践線形代数

Mike X Cohen
データ分析によるネットワークセキュリティ

データ分析によるネットワークセキュリティ

Michael Collins, 中田 秀基, 木下 哲也

Publisher Resources

ISBN: 9798341626317