Bubble sort code in scala

Bubble sort is simplest of all sorting algorithms. We start from the leftmost element of an array and compare two consecutive elements if a[i] > a[i+1] then we swap these two elements, so at the end of whole array scanning we'll have the largest element at the rightmost of the array. Now we repeat the same procedure for all the elements from (0 to n-1), (0 to n-2) ... and so on. The worst case running time of this algorithm will be (n + n-1 + n-2 ... 1) = O(n^2)

package com.thescalatutorial.examples

object BubbleSort {

  def bubbleSort(array: Array[Int]) = {
    def bubbleSortRecursive(array: Array[Int], current: Int, to: Int): Array[Int] = {
        println(array.mkString(",") + "    current -> " + current + ", to -> " + to)
        to match {
          case 0 => array
          case _ if(to == current) => bubbleSortRecursive(array, 0, to - 1)
          case _ =>
            if (array(current) > array(current + 1)) {
            var temp = array(current + 1)
            array(current + 1) = array(current)
            array(current) = temp
          }
          bubbleSortRecursive(array, current + 1, to)
        }
    }
    bubbleSortRecursive(array, 0, array.size - 1)
  }

  def main(args: Array[String]) {
    val sortedArray = bubbleSort(Array(10,9,11,5,2))
    println("Sorted Array -> " + sortedArray.mkString(","))
  }
}

Running above program will produce following output:
10,9,11,5,2    current -> 0, to -> 4
9,10,11,5,2    current -> 1, to -> 4
9,10,11,5,2    current -> 2, to -> 4
9,10,5,11,2    current -> 3, to -> 4
9,10,5,2,11    current -> 4, to -> 4
9,10,5,2,11    current -> 0, to -> 3
9,10,5,2,11    current -> 1, to -> 3
9,5,10,2,11    current -> 2, to -> 3
9,5,2,10,11    current -> 3, to -> 3
9,5,2,10,11    current -> 0, to -> 2
5,9,2,10,11    current -> 1, to -> 2
5,2,9,10,11    current -> 2, to -> 2
5,2,9,10,11    current -> 0, to -> 1
2,5,9,10,11    current -> 1, to -> 1
2,5,9,10,11    current -> 0, to -> 0
Sorted Array -> 2,5,9,10,11

Read more ...

Binary search in an ordered array

Array is most commonly used data structure. You can access an element stored in an array by its index in constant time but searching an element or deleting an element takes O(n) time. We can use binary search to find an element if the array is sorted. Below is the Scala code for binary search in an ordered array. Binary search is very simple, we divide the array in two parts and then decide on which part to search. Search continues recursively until either the element is found or it can't be found.

package com.thescalatutorial.examples

object OrderedArrayLookup {

  def binarySearch(array: Array[Int], value: Int) = {
    def printArray(array : Array[Int], start : Int, end : Int) {
      println(array.slice(start, end)mkString(","))
    }
    
    def binarySearchRecursive(array: Array[Int], start: Int, end: Int, value: Int): Int = {
      println("start -> " + start + ", end -> " + end)
      printArray(array, start, end+1)
      var i = (start + end) / 2
      if(start > end) {
        println("Not Found")
        return -99999999
      }
      
      array(i) match {
        case x if (x == value) => x
        case x if (x > value) => binarySearchRecursive(array, start, i - 1, value)
        case x if (x < value) => binarySearchRecursive(array, i + 1, end, value)
      }
    }
    binarySearchRecursive(array, 0, array.size - 1, value)
  }
  
  def main(args: Array[String]) {
   println("Found -> " + binarySearch(1 until 30 toArray, 11))
  }
}

Running above program will produce following output:
start -> 0, end -> 28
1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29
start -> 0, end -> 13
1,2,3,4,5,6,7,8,9,10,11,12,13,14
start -> 7, end -> 13
8,9,10,11,12,13,14
Found -> 11

Read more ...