Page 375, Exercise 8

1. Bubble Sort

bubble(list,n);

void bubble(element list[], int n) /* for i = 0, ..., n-2, compare Ri and Ri+1, if they are out of order exchange the two elements */ { int i,j; element temp; for (i = 0; i < n-1; i++) { for (j = 0; j < n-i-1; j++) if (list[j].key > list[j+1].key) SWAP(list[j],list[j+1],temp); } }



2. O(n²)
3. O(n²) - Comparisons don't change.
4. O(n²)