Microsoft Interview Question
Testing / Quality Assurancesvoid sort ( int A[] , int n )
{
if( n < 0 )return;
int idx=0,max=INT_MIN,max_idx=-1;
for( idx=0;idx<n;idx++ )
{
if( A[idx] < max )
{
max=A[idx];
max_idx=idx;
}
}
Flip( A , n ,max_idx);
Flip( A , n , n-1 ); /* gets the largest element at end of the array */
sort( A , n-1 );
}
This is bubble Sort
finding smallest element:
- Anonymous July 02, 2010- min = A[0]
- for i = 1 to (n-1)
if ( min > A[i] )
min = A[i]; Flip (A, n, i);
So, O(n) time to get smallest.
Once smallest is found, print it to output stream,and call Flip(A, n, n-1) which puts the last element in the array to first place, finally n-- as we removed smallest. Repeatedly we can do it to get O(n^2) sorting.
Plz correct if something seems wrong.