Help us understand the problem. What is going on with this article?

【Goでアルゴリズムの勉強】バブルソート【1日目】

More than 1 year has passed since last update.

※事の始まりはこちらをご参照ください。

お題

今回はVisuAlgoからsorthingに挑戦しました。
ソートする値はランダムではなく固定値 [29, 10, 1, 37] とします。

自力で解く

Step1:比較して入れ替える

本来ならば昇順になるまでソートしますが、
Step1では1巡だけにしました。

main.go
package main

import (
    "fmt"
)

func main() {
    arr := []int{29, 10, 1, 37}

    for i := 0; i < len(arr)-1; i++ {
        //「左>右」の場合、左右入れ替える
        if arr[i] > arr[i+1] {
            v1 := arr[i]
            v2 := arr[i+1]
            arr[i] = v2
            arr[i+1] = v1
        }
    }

    fmt.Printf("Finish: %v\n", arr)
}

結果
Finish: [10 1 29 37]

コードの書き方はともかく、ソートはうまくいっています。

Step2:昇順になるまでソートする

それでは本題の「昇順になるまでソート」させてみました。

main.go
package main

import (
    "fmt"
)

func main() {
    // ソートする値
    arr := []int{29, 10, 1, 37}
    // ソート終了判定するための配列
    arrTF := []bool{false, false, false, true}

    for {
        for i := 0; i < len(arr)-1; i++ {
            // 「左>右」の場合、左右入れ替える
            if arr[i] > arr[i+1] {
                v1 := arr[i]
                v2 := arr[i+1]
                arr[i] = v2
                arr[i+1] = v1
            } else {
                // 「左<右」になっていることを示すため、FをTにする
                arrTF[i] = true
            }
        }
        // ソート終了か判定する
        if finishSort(arrTF) {
            break
        }
    }

    fmt.Printf("Finish: %v %v\n", arr, arrTF)
}

func finishSort(arr []bool) bool {
    for _, v := range arr {
        if !v {
            return false
        }
    }
    return true
}
結果
Finish: [1 10 29 37] [true true true true]

結果は正しく得られていますが、書き方がまどろっこしいなと思いました。
以下、所感です。

  • ソート判定するための配列って必要?配列じゃなきゃいけないの?ソート数によって配列を作り変えなくちゃいけないのは無駄な気がする。
  • ソート処理でfor文やif文が入れ子になって読みづらそう。
  • シンプルにできそう。
  • finishSort関数でまたfor文を使用するよりも、ソート処理内でまとめてソート終了判定できないのかな。

答え合わせ

引用元:VisuAlgoのsorthing
do

  swapped = false

  for i = 1 to indexOfLastUnsortedElement-1

    if leftElement > rightElement

      swap(leftElement, rightElement)

      swapped = true

while swapped

ロジックを見る分には問題ないため、C言語で答え合わせを行います。

解答を見ると、やはり自分の書き方はまどろっこしいなと思いました。

swappedという変数を作り、「左>右」の間はswapped = trueにすれば、
falseになるまでソートを繰り返してくれます。
この方法ならば、ソート終了判定のために配列を作ったりfor文を使ったりしなくて済みます。
変数にしてしまえば、ソートする値が何個あろうがメモリを気にする必要がありません。

また、C言語にはswap関数というものがあるのですね。
調べてみると、Go言語にもありました(引用元:golang.jp)。

Go言語では、複数の代入が許されます。この代入は、それぞれ個別に処理されます。
i, j = j, i // iとjのスワップ

この方法ならば、わざわざv1 := arr[i]のような変数を作って代入させる処理が不要になります。

学んだこと

  1. T/Fの配列で判定するのではなく、変数にする。
  2. swap関数。

最後に

次回も今回のように、解いて答え合わせをした記事をアップします。
7日後、再度同じ問題を解いた際、今回の学びが反映されているようにしていきます。

コメントに体験談や知識、アホなところをツッコんでいただけると幸いです。
それでは。

Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away