Selection Sort

excerpt: How does selectionsort work? What is the time complexity? When can we use selectionsort? tags: swap nested-for-loops reducing-the-domains-of-the-variables

The goal is to order a list of integers in ascending order. The selectionsort is quadratic in time complexity but simple. It can outperform faster but more complicated algorithms for very small arrays.

Selectionsort in Arrays

The basic idea is to search the input list for the largest item and then add it to the end of a growing sorted list. An alternative approach is to find the smallest item and move it to the beginning of the growing sorted list. The steps to implement the selectionsort:

1. Iterate through the array from index 0 to array size - 1.
2. Find the item that must be in position i.
   • Find the smallest item with index j >= i.
3. Swap values[i] and values[j]

Iterate through the array to find the smallest element that has not yet been added to the sorted part of the array. Then swap the smallest item with the item in position i.

The first image shows the unsorted array. The second image shows the first three items that has been sorted. The code is getting ready to swap th enext element into position. The code searches the unsorted elements to find the one with the smallest value (3). Then this item is swapped into the next unsorted position. The last image shows the array after the new element has been moved to the sorted part of the array. The for loop continues to the next step to add the next element (5) to the growing sorted portion of the array.

The items are sorted inplace so no additional space is used. If the array contains N elements, each of the N positions must be considered. For each position i, we must seach N - i elements that have not yet been sorted to find the element that must be in position i. The code then swaps the item into its final position in a small constant number of steps.

The total run time is calculated by adding up all the steps required to move all the elements.

(N-1) + (N-2) + ... + 2 + 1 = (N<sup>2</sup> + N)/2

Therefore, the run time is O(N2). This is fast enough for small arrays of size 5 to 10 elements or so. This algorithm is relatively simpler that complicated algorithms that are faster.

Alternative Implementation

Consider the list as if it was divided into two parts, one sorted and the other unsorted. (note: at the beginning the sorted part is empty).

1. Select the smallest element in the unsorted part of the list
2. Swap that element with the element in the initial position of the unsorted array
3. Change where you divide the array from the sorted part to the unsorted part.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def sort(a)
  n = a.size
  
  for i in (0..n-2)
    min = i
    
    for j in (i+1..n-1)
      if a[j] < a[min]
        min = j
      end      
    end
    
    # swap
    a[min], a[i] = a[i], a[min]
  end
end

a = [3,1,0,2,8,4]
sort(a)
p a

Building Blocks

The selection sort algorithm uses the following basic building blocks:

• Nested For Loop
• Reducing the Domains of the Variables

Recursive Implementation

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def sort(array, index)
  low = index

  if index == array.size-1
    return array
  else
    for i in (index..array.size-2) do
      if array[i+1] < array[i] 
        low = i+1
      end
    end

    if array[index] > array[low]
      array[index], array[low] = array[low], array[index]
    end

    return sort(array, index+1)
  end
end

p sort([4,2,7,1,3], 0)