I'm currently doing some shearSorting and cannot figure out when this operation is supposed to be done with an n x n matrix.
What I'm doing currently is I'm copying the matrix at the start of each iteration of the loop to a temp matrix and then at the end of each iteration of the loop I'm comparing both the original and the temp matrices and if they are the same then I break out of the loop and exit. I do not like this approach as we always end up going through one extra iteration after the matrix in sorted and done which is a waste of CPU time and cycles.
There has to be a better way to do this checking. I keep finding references to log(n) to signify how many iteration we need but I don't believe they mean actual log(n) as log(5) for a 5x5 matrix in 0.69 which is impossible for number of iterations.
Any suggestions?
SO I know shearSort takes log(n) run iterations to complete so for a case of 5x5 matrix we will have 3 runs for rows and 3 runs for columns. But what if the 5x5 matrix I was given is kinda almost sorted and only needs one or 2 more iterations to be completed, in that case I do not see the point in iterating 6 time through it as this would be considered a waste of CPU power and cycles.
Also we have the following solution: if we copy the matrix at start of each iteration of the shearSort function to a temporary matrix and at the end of each iteration we compare the 2 matrices together and they are the same then we know that we are done (Note here an iteration would mean both a row and a column sort as a matrix might not need a row sort at first but would need a column sort after ). In this case we would be preserving CPU cycles in case the matrix doesn't need N + 1 iterations, but this solution would provide an issue which is when N + 1 iterations are needed then we would be doing N + 3 iterations to finish ( the extra 2 iterations would be one to check if 2 matrices are same for row and one for column).
To solve this we would have to use a combination of both solutions:
we would still be copying the matrix at start and comparing it to temp matrix at the end and if they are equal before we get to the N + 1 iterations then we are done and do not need to go on any further, and if they are not then we go to the N + 1 iteration and stop after since we know at this point the matrix should be sorted after N + 1 iterations.