Start learning free

LESSON 218 OF 414 · BRUTE FORCE

Selection Sort in Scala: In-Place Sorting in O(n^2)

Practice O(n2) Read the full explanation

In this video lesson we will learn what sorting is, when it should be used and we will code our first sorting algorithm - Selection Sort:

Problem - Selection Sort:

Given an array of integers nums, sort it in ascending order using Selection Sort

Example 1:

Input: nums = [3, 1, 3, 2, 5, 4]
Output: [1, 2, 3, 3, 4, 5]

Note:

Your algorithm should run in O(n^2) time and use O(1) extra space.

STEP 1 OF 7
    Ctrl + Enter to check

    SCALA · BRUTE FORCE

    Selection Sort in Scala, explained

    Problem overview

    The method sort receives an Array[Int] named nums and must sort it in ascending order. It returns Unit: the array is sorted in place, and the caller sees the result in the same array. For Array(3, 1, 3, 2, 5, 4) the array becomes 1, 2, 3, 3, 4, 5. Duplicates stay, as the two 3s show.

    The statement asks for O(n^2) time and O(1) extra space, and the lesson is built on Selection Sort.

    Approach: fill the array from the left

    Selection Sort works position by position. Position 0 should end up holding the smallest value, position 1 the second smallest, and so on. When the pass for position i is finished, everything before i is in its final place, so later passes only look at the part to the right.

    The pass for position i compares nums(i) with every later element nums(j). When a later element is smaller, it must come to position i, so the two are swapped. By the end of the inner loop, nums(i) holds the smallest value from index i onward.

    The version in this lesson swaps whenever it sees a smaller element, so one pass can swap several times. The classic textbook version first finds the position of the minimum and swaps once at the end of the pass. Both end with the same sorted array, and both are O(n^2).

    Why does it work? After the pass for position i, no element to the right of i is smaller than nums(i): any smaller value met during the pass was swapped into position i, and the value that ends up there is compared with every remaining element. So position i holds the smallest of the elements from i onward, and the sorted prefix grows by one each pass. After the last pass the whole array is sorted. Nothing is ever swapped into the prefix, because every swap involves positions i and j with j > i.

    The example, traced

    On Array(3, 1, 3, 2, 5, 4):

    • i = 0. 3 > 1 is true, so they swap: 1, 3, 3, 2, 5, 4. The 1 is now at position 0, and nothing later is smaller, so there are no more swaps in this pass.
    • i = 1. 3 > 3 is false. Then 3 > 2 is true, so they swap: 1, 2, 3, 3, 5, 4.
    • i = 2 and i = 3. No later element is smaller. Nothing changes.
    • i = 4. 5 > 4 is true, so they swap: 1, 2, 3, 3, 4, 5.

    Three swaps were enough here.

    Step by step

    1. Outer loop. Use i <- 0 until nums.length to visit every position. Each pass fills position i.
    2. Inner loop. Inside it use j <- (i + 1) until nums.length. Positions before i are final, so only the indices after i are compared.
    3. Compare. Test nums(i) > nums(j): a smaller value later in the array belongs at position i. Using > and not >= means equal values are never swapped, which saves useless work.
    4. Write swap. Add a helper above sort that takes nums, i and j and returns Unit. It saves nums(i) in a val temp, copies nums(j) into nums(i), then puts temp into nums(j). Without temp, the first assignment would destroy the old value of nums(i).
    5. Call it. Inside the if, call swap(nums, i, j).

    The solution in Scala

    class Solution {
    def swap(nums: Array[Int], i: Int, j: Int): Unit = {
        val temp = nums(i)
        nums(i) = nums(j)
        nums(j) = temp
    }

    def sort(nums: Array[Int]): Unit = {
        for (i <- 0 until nums.length) {
            for (j <- (i + 1) until nums.length) {
                if (nums(i) > nums(j)) {
                    swap(nums, i, j)
                }
            }
        }
    }
}

    Scala details:

    • Arrays are mutable and passed by reference. swap receives the same array object that sort holds, so its assignments are visible afterwards. Method parameters themselves can't be reassigned, but the contents of an array can.
    • Assignment with parentheses. nums(i) = nums(j) is shorthand for a call of the array's update method. It works because Array is mutable; an immutable List has no such assignment.
    • No return value. A Unit method that ends with a for loop returns (). The sorted data is in nums.
    • Index ranges. until excludes the upper bound. For the last i the range (i + 1) until nums.length is empty, and the inner loop is skipped.
    • Library sorting. nums.sorted returns a new sorted array, and scala.util.Sorting.quickSort(nums) sorts in place. The lesson writes the algorithm out so you can see how it works.

    Complexity

    Time: O(n^2). The inner loop makes n - 1 comparisons for i = 0, n - 2 for i = 1, and so on, which is n * (n - 1) / 2 comparisons whatever the order of the input. Swaps add more constant-time work. In this version a reversed array is the worst case for swaps: Array(5, 4, 3, 2, 1) makes 10 swaps, while the classic one-swap-per-pass version would make at most 4.

    Space: O(1). The array is rearranged in place, and the extra memory is the loop variables and temp.

    Edge cases and common mistakes

    • Empty and one-element arrays. There is nothing to compare, and the array is unchanged.
    • Already sorted input. No comparison succeeds, so there are no swaps, though the comparisons still happen.
    • Duplicates. Array(2, 2, 2) makes no swaps because > is false for equal values.
    • Comparing the wrong direction. Using < sorts in descending order.
    • Starting j at 0. That would compare elements to the left too, and it would swap values back and forth, undoing the sorted prefix.
    • Skipping temp. Writing nums(i) = nums(j) followed by nums(j) = nums(i) leaves two copies of the same value.
    • Expecting a result. sort returns Unit; read the array afterwards.

    Testing

    • Array(3, 1, 3, 2, 5, 4) becomes 1, 2, 3, 3, 4, 5.
    • Array(5, 4, 3, 2, 1) becomes 1, 2, 3, 4, 5.
    • Array(9) stays 9.
    • Array() stays empty.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free