The selection sort, similar to insertion sort, is one of the simple sorting algorithm that has O(N^2) time complexity. The selection sorting algorithm is quadratic, thus not efficient when the items to sort is large.
The selection sort works by choosing a minimal element in the unsorted list and append the element to the sorted list – which is done by swapping the element beyond the end of the sorted part.
For example, given the array: [3, 5, 2, 6, 1, 3, 4, 6, 9], we can simulate the Selection Sort algorithm in the following process:
1 2 3 4 5 6 7 8 9 10 | Sorted: [] Unsorted: [3, 5, 2, 6, 1, 3, 4, 6, 9] // min = 1 in the Unsorted Sorted: [1, ] Unsorted: [3, 5, 2, 6, 3, 4, 6, 9] // min = 2 in the Unsorted Sorted: [1, 2] Unsorted: [3, 5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted Sorted: [1, 2, 3] Unsorted: [5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted Sorted: [1, 2, 3, 3] Unsorted: [5, 6, 4, 6, 9] // min = 4 in the Unsorted Sorted: [1, 2, 3, 3, 4] Unsorted: [5, 6, 6, 9] // min = 5 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5] Unsorted: [6, 6, 9] // min = 6 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5, 6] Unsorted: [6, 9] // min = 6 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5, 6, 6] Unsorted: [9] // min = 9 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5, 6, 6, 9] Unsorted: [] // Done. |
Sorted: [] Unsorted: [3, 5, 2, 6, 1, 3, 4, 6, 9] // min = 1 in the Unsorted Sorted: [1, ] Unsorted: [3, 5, 2, 6, 3, 4, 6, 9] // min = 2 in the Unsorted Sorted: [1, 2] Unsorted: [3, 5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted Sorted: [1, 2, 3] Unsorted: [5, 6, 3, 4, 6, 9] // min = 3 in the Unsorted Sorted: [1, 2, 3, 3] Unsorted: [5, 6, 4, 6, 9] // min = 4 in the Unsorted Sorted: [1, 2, 3, 3, 4] Unsorted: [5, 6, 6, 9] // min = 5 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5] Unsorted: [6, 6, 9] // min = 6 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5, 6] Unsorted: [6, 9] // min = 6 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5, 6, 6] Unsorted: [9] // min = 9 in the Unsorted Sorted: [1, 2, 3, 3, 4, 5, 6, 6, 9] Unsorted: [] // Done.
Translating to VBScript, we have the following Selection Sorting Algorithm:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | Dim Nums: Nums = Array(3, 5, 2, 6, 1, 3, 4, 6, 9) Sub SelectionSort(ByRef Nums) For i = LBound(Nums) To UBound(Nums) - 1 Dim min: min = i For j = i + 1 To UBound(Nums) If Nums(j) < Nums(min) Then min = j End If Next If min <> i Then Dim t: t = Nums(min) Nums(min) = Nums(i) Nums(i) = t End If Next End Sub SelectionSort Nums For i = LBound(Nums) To UBound(Nums) WScript.Echo Nums(i) Next |
Dim Nums: Nums = Array(3, 5, 2, 6, 1, 3, 4, 6, 9) Sub SelectionSort(ByRef Nums) For i = LBound(Nums) To UBound(Nums) - 1 Dim min: min = i For j = i + 1 To UBound(Nums) If Nums(j) < Nums(min) Then min = j End If Next If min <> i Then Dim t: t = Nums(min) Nums(min) = Nums(i) Nums(i) = t End If Next End Sub SelectionSort Nums For i = LBound(Nums) To UBound(Nums) WScript.Echo Nums(i) Next
One advantage of Selection Sorting Algorithm is that it has at most (n-1) swaps when sorting n elements.
--EOF (The Ultimate Computing & Technology Blog) --
loading...
Last Post: Find the Queens That Can Attack the King
Next Post: Walking Robot Simulation Algorithm with Obstacles Detection
Thank you for article