-
-
Save Roshankumar350/18d2db80bcb3955a1b289f0c6114ed7d to your computer and use it in GitHub Desktop.
func selectionSort(forInput input: inout [Int]) { | |
let uptoIndex = input.count - 1 | |
var currentRunningMaximumNumber = input[0] | |
for rearIndex in 0..<uptoIndex { | |
// Assuming all are sorted | |
var isAllSorted = true | |
// Assuming rearIndex is minimum Index | |
var currentRunningMinimumIndex = rearIndex | |
for frontIndex in (rearIndex+1)...uptoIndex { | |
// Will have maximum number so far. | |
if input[frontIndex] > currentRunningMaximumNumber { | |
currentRunningMaximumNumber = input[frontIndex] | |
} | |
// We will try to find minimum number's index. | |
guard input[currentRunningMinimumIndex] > input[frontIndex] else { | |
// Check if maximum number so far is still maxumum else it's not sorted | |
if currentRunningMaximumNumber > input[frontIndex] { | |
isAllSorted = false | |
} | |
continue | |
} | |
currentRunningMinimumIndex = frontIndex | |
} | |
// if both index are equal, You don't want to swap it. | |
guard currentRunningMinimumIndex == rearIndex else { | |
input.swapAt(currentRunningMinimumIndex, rearIndex) | |
continue | |
} | |
// If our assumption of all elements are sorted is true. We will break | |
guard isAllSorted else { | |
continue | |
} | |
break | |
} | |
} |
var input = [1,2,3,4,5,6,7,8,9,10]
For this, parent loop will execute for 1 time, and child loop for 9 times.
this is the best case when the array is already sorted.
Case 2: var input = [10,2,3,4,5,6,7,8,9,1]
for the optimised algorithm, in this case the parent loop should execute 2 times, and the child loop for (9+8) times.
This is so because in the first parent loop iteration, the values '10' and '1' gets swapped, thereby making the array sorted; and in the next iteration it checks that no swapping is done (which implies sorted array) so it should exit.
But, in this code, all other iterations of parent loop are also being executed, i.e., the parent loop is executing 10 times, and the child loop is executing for (9+8+7+6+5+4+3+2+1+0 = 45) times.
But our objective was to check the array is sorted once only.
Currently we are least concerned about cases, rather we are more concerned about can we exist if entire array is sorted.
Ok lets assume we have an array of natural number say:
var input = [1,2,3,4,5,6,7,8,9,10]
As per your statement after reading code.
can you tell me how many times parent and child loop will execute ?