Insertion sort code in scala

Insertion sort improves upon both Bubble sort and Selection sort as it uses copy instead of swap and latter being more expensive operation as compared to former. We start from the leftmost element of an array and while in the process of iteration left part of the array from current element is always sorted. In each iteration we find the right place for current element among all of its left elements. The worst case running time of this algorithm still remains same because finding right position for an element will take O(n) so actual running time will be (1 + 2 + ... + n -1 + n) = O(n^2)

package com.thescalatutorial.examples

object InsertionSort {

  def insertionSort(array: Array[Int]) = {
  
    def insertionSortRecursive(array: Array[Int], start: Int): Array[Int] = {
      start match {
        case _ if (start > array.size - 1) => array
        case _ =>
          var j = start;
          val valueToSwap = array(start)
          while(j > 0 && array(j - 1) > valueToSwap) {
            array(j) = array(j - 1)
            j -= 1
          }
          array(j) = valueToSwap
          println(array.mkString(",") + "   valueToSwap -> " + valueToSwap)
          insertionSortRecursive(array, start + 1)
      }
    }
    insertionSortRecursive(array, 0)
  }

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

Running above program will produce following output:
10,9,11,5,2   valueToSwap -> 10
9,10,11,5,2   valueToSwap -> 9
9,10,11,5,2   valueToSwap -> 11
5,9,10,11,2   valueToSwap -> 5
2,5,9,10,11   valueToSwap -> 2
Sorted Array -> 2,5,9,10,11

Read more ...

Selection sort code in scala

Selection sort improves upon bubble sort as it minimizes number of swaps to O(n) as compared to bubble sort where number of swaps are in the order of O(n^2). We start from the leftmost element of an array and compute minimum of all elements which are right from current element then swap the current element with then minimum element. So at any point of time rightmost part from current element of the array is sorted. The worst case running time of this algorithm still remains same because finding minimum element in an array is O(n) so actual running time will be (n + n-1 + n-2 ... 1) = O(n^2)

package com.thescalatutorial.examples

object SelectionSort {

  def selectionSort(array: Array[Int]) = {

    def findMin(array: Array[Int], start: Int): Int = {
      var minIndex = start
      for (i <- start until array.size) {
        if (array(i) < array(minIndex)) {
          minIndex = i
        }
      }
      minIndex
    }

    def bubbleSortRecursive(array: Array[Int], start: Int): Array[Int] = {
      val minIndex = findMin(array, start)
      println(array.mkString(",") + ",  start -> " + start + ",  min -> " + array(minIndex))
      start match {
        case _ if (start >= array.size - 1) => array
        case _ =>
          var temp = array(start)
          array(start) = array(minIndex)
          array(minIndex) = temp
          bubbleSortRecursive(array, start + 1)
      }
    }
    bubbleSortRecursive(array, 0)
  }

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

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

Read more ...

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 ...