Category Archives: scala

Scala by example – Sorting

Here’s an attempt at learning Scala using some basic algorithms. I do realize that these examples look and “feel” like Java and do not use the full power of Scala’s more expressive syntax or its functional approach. This is just my humble attempt at learning a new language.

I use the scala plugin for Netbeans 6.7.

Bubble Sort

package sorts

class Sort {


    def bubblesort(lst : Array[Int]) : Array[Int] =
    {
        val list : Array[Int] = new Array[Int](lst.length)
        Array.copy(lst, 0, list, 0, lst.length)
        var swapped : boolean = false
        do
        {
            swapped = false
            for (i <- 0 to (list.length - 2))
            {
                if (list(i) > list(i+1))
                {
                    swapWithNext(i, list)
                    swapped = true
                }
            }
        } while (swapped)

        return list
    }

    def swapWithNext(i : Int, list:Array[Int]) : Unit =
    {
        val temp = list(i)
        list(i) = list(i+1)
        list(i+1) = temp
    }

Selection Sort


    def selectionsort(lst : Array[Int]) : Array[Int] =
    {
        val list : Array[Int] = new Array[Int](lst.length)
        Array.copy(lst, 0, list, 0, lst.length)

        for (i <- 0 until (list.length -1))
        {
            var min = i
            //find min
            for(j <- (i+1) until list.length)
            {
                if (list(j) < list(min))
                  min = j
            }

            //swap ith number with that at min position
            if (i != min)
            {
                val swap = list(i);
                list(i) = list(min);
                list(min) = swap;
            }
        }
        return list
    }


&#91;/sourcecode&#93;

<strong>Insertion Sort</strong>



    def insertionsort(lst : Array[Int]) : Array[Int] =
    {
        val list : Array[Int] = new Array[Int](lst.length)
        Array.copy(lst, 0, list, 0, lst.length)

        list.foreach(a => print(a + ","))
        println()
        for (i <- 1 to list.length - 1)
        {
            //pick arbit minimum value
            val value = list(i)

            //iterate through the rest of the "sorted" array
            var j = i-1
            while (j >= 0 && list(j) > value)
            {
                list(j+1) = list(j)
                j = j-1
            }
            //replace
            list(j+1) = value
            list.foreach(a => print(a + ","))
            println()
        }
        return list
    }


Quick Sort


    def quicksort(lst : Array[Int]) : Array[Int] =
    {
        var list = lst.elements.toList
        
        list = quicksortBasic(list);
        return list.toArray

    }

    private def quicksortBasic(list: List[Int]): List[Int] =
    {
        var less:List[Int] = List()
        var greater:List[Int] = List()
        if (list.length <= 1)
            return list

        val index = list.length / 2;
        val pivot = list(index)

        for (i <- 0 to (list.length -1))
        {
            if (list(i) < pivot)
              less += list(i)
            else if (list(i) > pivot)
              greater += list(i)
        }

        return (quicksortBasic(less) + pivot ++ quicksortBasic(greater))
    }


}

Here’s the Main object that calls the sort methods

object Main {

    /**
     * @param args the command line arguments
     */
    def main(args: Array[String]) :Unit = {
        val list = new Array[Int](5)
        list(0) = 10
        list(1) = 5
        list(2) = 25
        list(3) = 0
        list(4) = 22

        println("bubble")
        new Sort().bubblesort(list).foreach(println);

        println("selection")
        new Sort().selectionsort(list).foreach(println);

        println("insertion")
        new Sort().insertionsort(list).foreach(println);


        println("quicksort")
        new Sort().quicksort(list).foreach(println);


        println("end")

    }

}

I’ll revisit these examples and make them more “scala” like in some time.

Advertisements