update.概要プログラミングを始めた当初、アルゴリズムというものが全くわかりませんでした。クイックソート?アルゴリズムにまつわるどんなコードと向き合ってもちっとも楽しくないし、ちっともわかりませんでした。アルゴリズムって言葉を聞いたらなんだか怖い印象がありました。難しくて、本当に頭のいいプログラマーしか使えないような印象が強かったです。アルゴリズムってなに?本当にその通りで、僕も同じように感じていましたしかし、ようやく最近、アルゴリズムと向き合えるようになりました。どんなアルゴリズムも、何かしらの問題を解決するために作られています。[ˈælgəˌrɪðəm])とは、数学、コンピューティング、言語学、あるいは関連する分野において、問題を解くための手順を定式化した形で表現したものを言う。『素早く、なるべく正確に円の面積を求めたい!』という問題にぶつかったときに、この問題を解くために、大昔ギリシャで生まれたのが、このアルゴリズムです。円の半径さえ、入れれば、簡単に円の面積をこのアルゴリズムは求めることができますその他のアルゴリズムも同じように考えることができます。問題があって、それを解決するために、アルゴリズムは存在しています。ソートアルゴリズムもちろん、他にもたくさんのアルゴリズムが存在しますしかし、大学の授業の試験や、情報技術者試験の問題に出てくるようなアルゴリズムというと、この2つが代表的と言えるでしょう。アルゴリズムと検索すると、真っ先にソートアルゴリズムがヒットしますが、ソートアルゴリズムについて理解するには、まず、探索アルゴリズムについて理解しないと、何のためにソートアルゴリズムが存在するのかわからなくて、全く理解できません。探索アルゴリズムを学び、そのあと、ソートアルゴリズムについて学びます探索アルゴリズムまず、覚えて欲しいアルゴリズムに探索アルゴリズムがあります。難しく聞こえますが、とっても簡単です。膨大なデータ群の中から目的のデータを探しだすアルゴリズムのことを探索アルゴリズムと言います。線形探索アルゴリズムまず、トランプでイメージしてみましょうハートのトランプが1~Kまで13枚ランダムに並べられています。このとき、「どこにハートの7のトランプがあるか答えなさい」と聞かれたら、どうしますか?おそらく多くの人は、カードを一枚ずつめくって、ハードの7のトランプを探すことかと思いますこれをアルゴリズムの世界では、線形探索アルゴリズム(もしくは逐次探索アルゴリズム)と言います。途中で一枚飛ばしたり、途中からめくり始めたりせず、最初から最後まで目的のデータが見つかるまで探索を続けることから線形探索と呼ばれています。linear_search(heart_cards,heart_king)ただし、この線形探索アルゴリズム、とっても簡単でわかりやすいですが、実際の場面においては非効率であることが多いです今回のように、データ数が少ない場合は、問題ありませんが、データが1万、10万、100万と増えていったらどうでしょうか?一つずつデータを確認していく時間が膨大になりませんか?線形探索リストの最大探索回数はN(Nはデータの個数分)平均探索回数はN/2となります。線形探索アルゴリズムだと、100万個のデータを探索するとなると、最大で100万回、平均でも50万回トランプをめくらないといけません。2分探索アルゴリズム次に、トランプのお題を変えてみます今度は、ハートのトランプ1~Kまでの内、10枚だけが昇順(必ず小さいものから並べられている)で並べられています。このとき、「どこにハートの8のトランプがあるか答えなさい」と聞かれたら、どうしますか?また線形探索しますか?いえ、実は、データが昇順で並べられているという条件がある時のみ、僕たちはより効率的なアルゴリズムを使うことができますそれを2分探索(バイナリサーチ)アルゴリズムと言いますまずトランプの中から真ん中のトランプをめくりますすると、6が出てきました僕たちが探し出したいトランプは8です昇順でトランプは並べられているので、この真ん中のトランプよりも右側に目的のトランプは存在していることがわかります。今度は右側の真ん中のトランプをめくりますすると10が出てきますね今度はこれよりも小さいので左側に存在していることがわかりますもう一度真ん中のトランプをめくると、無事に見つかりました。heart_eight)線形探索リストの最大探索回数はN(Nはデータの個数分)で、平均探索回数はN/2でしたね。二分探索アルゴリズムの最大探索回数はlog2N+1平均探索回数はlog2Nになりますつまり、2分探索アルゴリズムで、100万個のデータを探索するとなると、最大で21回、平均でも20回トランプをめくるだけですみます。探索アルゴリズムの時、最大で100万回トランプをめくっていた時を振り返って見てください線形探索の時よりも、よっぽど効率的ですね【生活や実務に役立つ計算サイト】対数関数しかし、冒頭でも説明しましたが、この2分探索アルゴリズム、必ずデータが整列されていないと使えません!ここまで理解できていたら、当然ですよねデータが必ず、左側が一番小さく、右側にいけば大きくなるという条件があるから、この2分探索アルゴリズムは成立します。実際世の中のデータは、生まれながらに整列されていることはまずありません。したら良いでしょうか?そんな時の出番になるのが、ソートアルゴリズムになりますランダムで、規則性もないバラバラに並べられたデータ群を、昇順なり、降順なり、整列するアルゴリズムがソートアルゴリズムです。探索アルゴリズムまとめ以上で探索アルゴリズムの説明はおしまいです。『データ群の中から、ある目的のデータを入手したい!』という問題があった時に私たちは、線形探索アルゴリズムを使うことができますこれは、簡単でわかりやすく、初心者でも、この問題を解くことができるアルゴリズムになります。この線形探索アルゴリズムはまた別の問題を孕みますそれは、非効率的であるということ100万個あるデータなら100万回探索する可能性があるのがこのアルゴリズムですそして、この問題を解決するのが、2分探索アルゴリズムです『効率的に、データ群の中から、ある目的のデータを入手したい!』という問題に、この2分探索アルゴリズムを使うことができます。この2分探索アルゴリズムは、また問題を抱えていますそれは、データが整列されていないと使用することができないということデータが昇順、降順に整列されているという前提があるから、この2分探索アルゴリズムは使用することができますそして、この問題を解決するのがこの後紹介するソートアルゴリズムになります。このソートアルゴリズムには実はたくさん種類があります。それぞれによって、効率性が違ったり、組み合わせて使う場合もあります。どのソートアルゴリズムも目的は一つです。バラバラに並べられたデータ群を整列すること次から見ていきましょうまた、他の探索アルゴリズムにハッシュ探索アルゴリズムと呼ばれるものがあります。upLoginユーザーは見つかりませんでした。