Monday, September 5, 2011

PowerShell: Insertion Sort

Insertion Sort is in practice slightly more efficient then Selection Sort (And by extension of course Bubble Sort), even though they share the same O(n^2) time complexity.

Insertion Sort have a number of benefits. It'd Adaptive, meaning that it takes less time to run the more sorted the input already is. Stable, meaning that it doesn't change the order of same valued numbers. If we for example sort 1,3,2,2 with Insertion Sort, the 2's won't change place in relation to each other. That can be relevant if we are sorting value-key pairs. In-place meaning that the extra memory needed (in addition to the storage of the array) is constant. Online, meaning that you can start sorting a list even if you haven't received all the values yet.

The idea behind Insertion Sort is that you first divide the data to be sorted into two partitions. One consisting of the unsorted data, and one containing the partially sorted data. First, the first value in the array is considered part of the partially sorted data. The step of comparing this first value to the empty partition of partially sorted data is naturally omitted. Then, the next value of the unsorted values are compared to this partially sorted value, and put it into the partially sorted values before or after the value already there, depending of course on weather or not it's larger or smaller. I'm assuming an left to right ascending sort.
For example:
Imagine this representation [partially sorted values][unsorted values].
We start with this [][2,3,1].
The first value is immediately moved to the partially sorted values, [2][3,1].
The second unsorted value is then compared to the partially sorted value, and since it's bigger, it will be placed to the right of it [2,3][1].
Now the only unsorted item is compared to the last partially sorted value. Since 1 is smaller then 3, we compare it with the next value. Finally since, there is only one partially sorted value left to compare with (the number 2) and our unsorted value (number 1) is smaller, we put it to the left and get [1,2,3][].

Here's the code for Insertion Sort in PowerShell:
Function InsertionSort($arrArray) {
  for ($i=1;$i -lt $arrArray.length;$i++) {
    $j = $i - 1
    $intValue = $arrArray[$i]
    $boolDone = $false
    Do {
      If ($arrArray[$j] -gt $intValue) {
        $arrArray[$j+1] = $arrArray[$j]
        $j -= 1
	if ($j -lt 0) {
	  $boolDone = $true
	}
      }
      Else {
        $boolDone = $true
      }
    }
    Until ($boolDone)
    $arrArray[$j + 1] = $intValue
  }
  $arrArray
}

No comments: