Bubble Sort PHP

Bubble sort's one virtue is simplicity. The list is scanned repeatedly, once less than there are elements. Neighboring items are compared and swapped if out of order. Each time through the list you scan one less item because the lightest bubbles (to stick with the metaphor) have risen to the top.

The outermost for loop sets the limit for how far to allow bubbles to rise. The first time through, this is one, because the first element of the array is indexed by zero. After going through the inner loop once, we will be certain that the smallest number will be in the first position of the array. This is because the inner loop will compare the last element to the next to last element, swap them if they are out of order, and then move up a notch. Eventually the smallest element will be reached and swapped upward.

If n is the number of elements in the array, the bubble sort will always make (n - 1) comparisons, then (n - 2) and so on.This means 7 elements require 21 comparisons (6 + 5 + 4 + 3 + 2 + 1) in the first iteration, regardless of whether the array is in order or out of order. If the array is already in order, then no exchanges will be made. If it is in reverse order, an exchange will be made for every comparison.

Bubble Sort

Bubble Sort

Listing

It's easy to see that the bubble sort is very inefficient, but if you ran the example, you probably didn't get the impression it was slow. For tiny lists of fewer than a hundred elements, the bubble sort is fine. If you have to code your own sort, the bubble sort has the advantage of being easy to remember and simple enough to get right the first time.


All rights reserved © 2018 Wisdom IT Services India Pvt. Ltd DMCA.com Protection Status

PHP Topics