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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: