Scala プログラミング練習（バブルソート）

色んな便利なライブラリのお陰で、アルゴリズムの勉強をせずとも複雑な処理が実現できています。
ただ、やはりアルゴリズムってプログラミングをする上では知っておきたいところです。
正直なところ、アルゴリズムの勉強ってきちんとやったことがないので
プログラミングを通じて学んでみようかなと思ってます。

バブルソートって？
まずはバブルソートですが、手書きでどんな流れになるか手元で書いてみたところ。

ひどい図になりましたが、赤が数字の大小を比較しているところ、青がその数字の居場所が確定したところになります。
文字で流れを書くと以下のような感じです。
1. リストの最初の要素と次の要素を比較。
2. 左の要素の方が大きかったら、右の要素と交換。
3. 一番左の要素以外を新たなリストとし、1 -> 2 -> 3 を繰り返す。
4. 一番右の要素までチェックしたら、一番右の要素以外を新たなリストとし、1 -> 2 -> 3 -> 4 を繰り返す。
5. 4 で作り新たなリストのサイズが 1 になったら終了。

単純なことなはずなのに、言葉で表現するのって難しい。

最初に書いてみたコード

def bubbleSort1(list: List[Int]): List[Int] = {
  def switchElement(list2: List[Int]): List[Int] = {
    val headValue = list2.head
    val tailList = list2.tail
    var switchedList = headValue :: tailList
      
    if (headValue > tailList.head) {
      switchedList = tailList.head :: headValue :: tailList.tail
    }
      
    if (switchedList.tail.length > 1) {
      switchedList = switchedList.head :: switchElement(switchedList.tail)
    }
    switchedList
  }
    
  if (list.length > 1) {
    var latestSwitchedList = switchElement(list)
    if (latestSwitchedList.init.length > 1) {
      latestSwitchedList = bubbleSort1(latestSwitchedList.init) :+ latestSwitchedList.last
    }
    latestSwitchedList
  } else {
    list  
  }
}

動くには動きますが、var を使ってしまっているのが気持ち悪かったので、そこだけ書き直しました。

def bubbleSort2(list: List[Int]): List[Int] = {
  def switchElement(list2: List[Int]): List[Int] = {
    val headValue = list2.head
    val tailList = list2.tail
     
    val switchedList = 
      if (headValue > tailList.head) tailList.head :: headValue :: tailList.tail
      else headValue :: tailList
      
    if (switchedList.tail.length > 1) switchedList.head :: switchElement(switchedList.tail)
    else switchedList
  }
    
  if (list.length > 1) {
    val latestSwitchedList = switchElement(list)
    if (latestSwitchedList.init.length > 1) bubbleSort2(latestSwitchedList.init) :+ latestSwitchedList.last
    else latestSwitchedList
  } else {
    list  
  }
}

感想
久しぶりに scala で書いたので楽しかったし、再帰処理で書けたのが良かった。
case match とか使えばもっとシンプルに書けるのかも。
思っていたよりも難しいが、他のアルゴリズムにもチャレンジしてみたい。

ソースコード