This is probably the simplest way sort an array of objects. Unfortunately it is also the slowest way! The basic idea is to compare two neighboring objects, and to swap them if they are in the wrong order. Given an array a of numbers, with length n, here's a snippet of C code for bubble sort:
for (i=0; i
if (a[j+1] < a[j])
{
/* compare the two neighbors */
tmp = a[j];
/* swap a[j] and a[j+1] */
a[j] = a[j+1];
a[j+1] = tmp;
}
}
As we can see, the algorithm consists of two nested loops. The index j in the inner loop travels up the array, comparing adjacent entries in the array (at j and j+1), while the outer loop causes the inner loop to make repeated passes through the array. After the first pass, the largest element is guaranteed to be at the end of the array, after the second pass, the second largest element is in position, and so on. That is why the upper bound in the inner loop (n-1-i) decreases with each pass: we don't have to re-visit the end of the array.
No comments:
Post a Comment