How to manually sort an array in Scala?

How to manually sort an array in Scala?

You can find in the Scala By Example book, in chapter 2, an example for a sort, without using a .sort kind of function:

def sort(xs: Array[Int]): Array[Int] = {
  if (xs.length <= 1) xs
  else {
    val pivot = xs(xs.length / 2)
    Array.concat(
      sort(xs filter (pivot >)),
      xs filter (pivot ==),
      sort(xs filter (pivot <)))
  }
}

If you want to read more about this algorithm, you can do it at Scala Quicksort algorithms: FP/recursive, imperative (and performance). This article also analyses the memory complexity.

Welcome to Scala. In Software Engineering there are multiple ways to sort outside of the standard library. One way to understand the different ones is to watch some of the Hungarian dancers entertain you with:

  1. Quicksort https://www.youtube.com/watch?v=ywWBy6J5gz8
  2. Bubblesort https://www.youtube.com/watch?v=lyZQPjUT5B4

But in answer to your question. It is kind of tough since a doesnt necessarily refer to anything and we dont know what arr originally looks like.

I redid a bit, the other thing is, this looks like a bubble sort, so you would have to ensure that you do a pass with no swaps. Here you will get a response at least, but it is still incorrect, post an update, and read about bubble sort. By the way, your check at the last element was reaching out of bounds .:)

val arr = Array(10, 3, 4, 9, 2, 5, 1)

for(i<-0 to (arr.length -1 )){
  
  if(i < (arr.length -1) && arr(i) > arr(i+1)){
    var tempVal: Int = arr(i)
    arr(i)= arr(i+1)
    arr(i+1) = tempVal
  }
}

println(arr.mkString(,))

How to manually sort an array in Scala?

Lets go through your code one step at a time. First of all, as an example Ill say that

val a = Array(5, 3, 4, 7, 1)

Ill let the formatter tidy up my code, fix the reference to arr (it should be a, judging from the rest of the code) and get rid of the debug print.

We get to this point (playground):

val a = Array(5, 3, 4, 7, 1)

for (i <- 0 to a.length) {
  if (a(i) > a(i + 1)) {
    var tempVal: Int = a(i)
    a(i) = a(i + 1)
    a(i + 1) = tempVal
  }
}

Now at least the code compiles. As suggested in a comment, one error is using to to produce a range: as you are correctly assuming that array indexes are 0 based. However, this means that an array of length 5 (as in my case) will have valid indexes in the range 0 to 4. The to method produces a range which includes the specified ends, so 0 to a.length will create the range 0 to 5, where 5 will cause the IndexOutOfRangeException. Again, as suggested in the comment, we should replace to with until, which yields the same result as 0 to (n - 1).

Furthermore, you are indexing the next element inside the loop, which means that you want to loop the array until the second to last element, which means we need to iterate from 0 until (a.length - 1).

After this change the code also runs, so Ill add a println at the end to see the result (playground):


for (i <- 0 until (a.length - 1)) {
  if (a(i) > a(i + 1)) {
    var tempVal: Int = a(i)
    a(i) = a(i + 1)
    a(i + 1) = tempVal
  }
}

println(a.iterator.mkString(, ))

Unfortunately this prints 3, 4, 5, 1, 7, which is definitely not sorted.

It looks like you are implementing bubble sort, but in order to do that we cannot simply go through the array once, we need to iterate over and over again until the array is sorted. Well introduce a boolean variable to keep track of whether we reached the desired conclusion (playground):

val a = Array(5, 3, 4, 7, 1)
var needsSorting = true

while (needsSorting) {
  needsSorting = false
  for (i <- 0 until (a.length - 1)) {
    if (a(i) > a(i + 1)) {
      var tempVal: Int = a(i)
      a(i) = a(i + 1)
      a(i + 1) = tempVal
      needsSorting = true
    }
  }
}

println(a.iterator.mkString(, ))

Now the output is 1, 3, 4, 5, 7, which is sorted! This successfully implements a bubble sort, which is however a very inefficient algorithm, requiring to go through the entire array once for every item in the array, which means that it has quadratic complexity.

The next step for you is learning more on more efficient sorting algorithms.

In the meantime, we can probably have a look at the code and improve where possible. A first step could be to remove the unnecessary mutable variable when swapping and factor out the swap method (playground):

def swap(a: Array[Int], i: Int, j: Int): Unit = {
  val tmp = a(j)
  a(j) = a(i)
  a(i) = tmp
}

val a = Array(5, 3, 4, 7, 1)
var needsSorting = true

while (needsSorting) {
  needsSorting = false
  for (i <- 0 until (a.length - 1)) {
    if (a(i) > a(i + 1)) {
      swap(a, i, i + 1)
      needsSorting = true
    }
  }
}

println(a.iterator.mkString(, ))

Another thing I would do is factor out sorting in its own function (playground):

def swap(a: Array[Int], i: Int, j: Int): Unit = {
  val tmp = a(j)
  a(j) = a(i)
  a(i) = tmp
}

def sort(a: Array[Int]): Unit = {
  var needsSorting = true
  while (needsSorting) {
    needsSorting = false
    for (i <- 0 until (a.length - 1)) {
      if (a(i) > a(i + 1)) {
        swap(a, i, i + 1)
        needsSorting = true
      }
    }
  }
}

val a = Array(5, 3, 4, 7, 1)

sort(a)

println(a.iterator.mkString(, ))

Another thing I would do is probably to factor out a single pass as its own method and declare both helpers in the sort function itself to limit the scope in which they can be used and take advantage of a being in scope so that we dont have to pass it in (playground):

def sort(a: Array[Int]): Unit = {
  
  val secondToLastItem = a.length - 1

  def swap(i: Int, j: Int): Unit = {
    val tmp = a(j)
    a(j) = a(i)
    a(i) = tmp
  }
  
  def onePassIsSorted(): Boolean = {
    var swapped = false
    for (i <- 0 until secondToLastItem) {
      val j = i + 1
      if (a(i) > a(j)) {
        swap(i, j)
        swapped = true
      }
    }
    swapped
  }

  while (onePassIsSorted()) {}
}

val a = Array(5, 3, 4, 7, 1)

sort(a)

println(a.iterator.mkString(, ))

Leave a Reply

Your email address will not be published.