-
-
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 | |
} | |
} |
See Mittal
You quoted
I tried to test this, and unfortunately if the array isn't sorted from the start, the algorithm is running in O(n^2)
https://en.wikipedia.org/wiki/Selection_sort
Our objective here to see if array is sorted, If it is sorted we will exit with O(n) else let the complexity go for O(n^2).
You quoted
"Also, I noticed 2 typos: first one is in line 1 - parameter should be "input" rather than "inout"; second one is in line 6 - closed range operator in the for loop."
parameter is still input, inout
is keyword learn more about it : https://www.hackingwithswift.com/sixty/5/10/inout-parameters
Close range operator is ok to me.
parameter is still input,
inout
is keyword
Oh, okay... I'm not familiar with swift, so sorry about that. Thanks for the material.
As for the issue I was talking about, what I meant was that we're not exiting the loop when the array gets sorted. (Sorry that I was not able to specify it clearly.)
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 ?
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.
I tried to test this, and unfortunately if the array isn't sorted from the start, the algorithm is running in O(n^2).
The root cause being even after the array is sorted, for the next iteration the value of
currentRunningMaximumNumber
implies that a larger number is present before thefrontIndex
in the array (even though the array is sorted and thecurrentRunningMaximumNumber
and correspondingly the largest value are present at the end of the array) ; hence it sorts further.To tackle this, we can simply remove line 4, and declare the
currentRunningMaximumNumber
variable inside the outer loop and initialise withrearIndex
rather than index 0.Also, I noticed 2 typos: first one is in line 1 - parameter should be "input" rather than "inout"; second one is in line 6 - closed range operator in the for loop.