Skip to content

Instantly share code, notes, and snippets.

@Roshankumar350
Created April 13, 2021 07:32
Show Gist options
  • Save Roshankumar350/18d2db80bcb3955a1b289f0c6114ed7d to your computer and use it in GitHub Desktop.
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
}
}
@Mittal-Samarth
Copy link

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 the frontIndex in the array (even though the array is sorted and the currentRunningMaximumNumber 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 with rearIndex 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.

@Roshankumar350
Copy link
Author

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.

@Mittal-Samarth
Copy link

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.)

@Roshankumar350
Copy link
Author

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 ?

@Mittal-Samarth
Copy link

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.

@Roshankumar350
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment