We'll it's certainly possible, but it can be expensive. Consider random numbers with maximum value say 100, let's say we have the sequence
92 51 11 69 24 35 17 36 26 98The program to sort this sequence in O(n) is time is given at code for O(n) sorting
The output of the program is
11 17 24 26 35 36 51 69 92 98
Question 1: What are the disadvantages of such sorting methods - give at-least two
Question 2: Can you write code, given a sequence of numbers as input, it can verify if the array is in sorted order
PS: The curious and smart will notice that O(n) is not the correct analysis of the algorithm, so whats the correct complexity then?
1 comment:
Are you saying your original algo is not O(n)? I mean, if you take 'n' to mean swaps or 'n' to mean compares, then, you are actually O(0)! 'coz you don't do any...right?
For q2: It should be O(n).
unsorted = false;
for ( int i = 0; i < n; i++ )
if (a[i] > a[i + 1] )
{
unsorted = true; break;
}
check unsorted... :)
Post a Comment