0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

JavaScriptとソートアルゴリズムで学ぶ再帰処理

Posted at

ソートアルゴリズムもよくわからんし、再帰処理もよくわからん人間が
なんと勉強しました。

main.js

   {

        // 再帰の基本
        // まずはあの有名な高田健志を発見する再帰処理

        const haveKenshi = list => {
            
            if(list.length <= 0)
                return
            
            if(list.pop() == "高田健志")
                console.log("高田健志ってすごいよなぁ!?")

            haveKenshi(list)
            
        }

        const talent = ["もこう","横山緑","高田健志","こくにい"]
        haveKenshi(talent)

    }

    /**
     * ["もこう","横山緑","高田健志","こくにい"]
     * こくにい
     * 
     * ["もこう","横山緑","高田健志"]
     * 高田健志
     * 
     * 高田健志ってすごいよなぁ!?
     * 
     * */


引数で受け取った配列の要素を一つ取り出して検査する。
もしも高田健志がいなかったら、一つ取り出して一つなくなった状態の配列でもう一度検査する。ということをやっております。

バブルソート

ちょっと改善すべき点がいくつかあるらしいのですが
わかりやすいコードで書きます。

main.js
     {

        // バブルソート
        // 一番でっけえ値を後ろに持ってくるを繰り返すやつ
        const bsort = (list,n) => {

            if(n < 2)
                return

            list.forEach( (c,i) => {   
                if( c > list[i + 1])
                    [ list[i] , list[i+1] ] = [ list[i+1] , list[i] ]          
            })

            bsort(list,n-1)

        }

        let target = [3,42,6,1,7,13,9,8]
        bsort(target,target.length)
        console.log(target)

    }


// [1, 3, 6, 7, 8, 9, 13, 42]

        /**
         *
         *  一番大きい値を一番後ろに持っていく。
         * というのを繰り返す。
         * 
         * [3, 6, 1, 7, 13, 9, 8, 42]
         * [3, 1, 6, 7, 9, 8, 13, 42]
         * [1, 3, 6, 7, 8, 9, 13, 42]
         * [1, 3, 6, 7, 8, 9, 13, 42]
         * ...
         * 
         * */

ループの中で一番大きい値を一番後ろに持っていく。
というループを再帰で表現しています。
これも、一番大きい値が、一番後ろにもっていかれた配列で
bsortを呼び出すということで、実現しております。

クイックソート

今度はちょっと難しいけどわかるとスッキリするパターンです。

main.js
    const getsmall = (x,y) => x < y
    const getlarge = (x,y) => x >= y

    // quickソート
    // 一番かっけえやつ
    const qsort = list => {

        if(list.length < 2)
            return list 
        
        // 要素を一つとる
        let pivot = list.pop()
        // 要素より小さい配列
        let min = list.filter( x => getsmall(x,pivot))
        // 要素より大きい配列
        let max = list.filter( x => getlarge(x,pivot))

        return qsort(min) + pivot + qsort(max)

    }

    const val1 = [6,5,1,2,9,7,3,4]
    console.log(qsort(val1))


    /**
     *  pivot:4
     *  [1,2,3] [4] [6,5,9,7]
     * 
     *  pivot:3
     *  [1,2] [3] []
     * 
     *  pivot:2
     * [1] [2] []
     * 
     * 最初のpivot以下がソート完了
     * [1][2][3][4]
     * 
     * 
     * 最初のpivot以上のソート開始([6,5,9,7])
     *  pivot:7
     * [5,6] [7] [9]
     * 
     * pivot:6
     * [5] [6] []
     * 
     * [5][6][7][9]
     * 
     *  結果
     * [1][2][3][4][5][6][7][9]
     * >> 12345679
     * */


動きの詳細はコメントに書いてある通りです。
これは再帰呼び出しを駆使しております

[小] 基準値 [大]

という三つの値を使います。
そして小の中で、再帰処理を行い。
大の中でも再帰処理を行います。

結果的にはコメントのような動きになっていると思います。

0
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?