Question

You are given a collection of n bottles of different widths and n lids of different widths and you need to find which lid goes with which bottle. You can compare a lid to a bottle, from which you can determine if the lid is larger than the bottle, smaller than the bottle, or the correct size. However, there is no way to compare the bottles or the lids directly to each other, i.e. you can’t compare lids to lids or bottles to bottles. Design an algorithm for this problem with an average-case efficiency of Θ(nlgn)

Answer 1

void bubble_sort( int A[ ], int n ) {

int temp;

for(int k = 0; k< n-1; k++) {

// (n-k-1) to ignore comparisons of already compared iterations

for(int i = 0; i < n-k-1; i++) {

if(A[ i ] > A[ i+1] ) {

// swapping occurs here

temp = A[ i ];

A[ i ] = A[ i+1 ];

A[ i + 1] = temp ;

}

}

}

}