[Home]
[Edit this page]
[Recent Changes]
[Special Pages]
[Help]
BubbleSort
The bubble sort has order n2, and therefore gets increasingly inefficient as you have more and more data to sort.
A bubble sort is execute by swapping pairs of adjecent elements to put them in order. Multiple swapping passes must be made through the array in order to complete the sort.
For an example, take the array
48, 12, 45, 2, 16, 22
The first step is to test the first and second elements, and swap them if they are not in order. In this case, 48 is larger than 12, so the elements must be swapped.
12, 48, 45, 2, 16, 22
Now we repeat the step for the second and third elements. Since 48 is also larger than 45, we swap again.
12, 45, 48, 2, 16, 22
We continue in this manner until we have completed a sweep of the array.
12, 45, 2, 16, 22, 48
Now we know that the largest element of the array is in the last position. Thus, in the next sweep of the array, we do not need to check again the last element. We only need to check the first 5 element of this 6-element array (and in any array, with each subsequent sweep, we check one element less until we arrive at the final sweep, in which there are only the first two elements to check).
Thus, after the second sweep, we would have
12, 2, 16, 22, 45, 48
From this progression arises the name ''bubble'' sort: with each sweep, the next largest element ultimately "bubbles" up to its rightful position within the array until we have a completely sorted array:
2, 12, 16, 22, 45, 48
This sorting algorithm is remarkably slow and inefficient because it requires multiple passes, checking the same elements many times, and only positions one element reliably with each sweep.
[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]
BubbleSort
(Computer science) Bubble Sort
Explantation #2
The Bubble Sort is a sorting algorithm. Given a list L, we iterate through the items, swapping them if they are out of order. Since each time we iterate, at least one item will be in the proper place, we can leave out that item the next iteration. To improve efficiency, we should check at the end of each iteration through the items if any swaps were made. If none were, the data is sorted and we can pull the plug on it.The bubble sort has order n2, and therefore gets increasingly inefficient as you have more and more data to sort.
Explanation #2
The '''bubble sort''' is a sorting algorithm for putting elements in an array in order. The bubble sort is famous for being one of the simplest, yet at the same time slowest and most inefficient, sorting algorithms.A bubble sort is execute by swapping pairs of adjecent elements to put them in order. Multiple swapping passes must be made through the array in order to complete the sort.
For an example, take the array
48, 12, 45, 2, 16, 22
The first step is to test the first and second elements, and swap them if they are not in order. In this case, 48 is larger than 12, so the elements must be swapped.
12, 48, 45, 2, 16, 22
Now we repeat the step for the second and third elements. Since 48 is also larger than 45, we swap again.
12, 45, 48, 2, 16, 22
We continue in this manner until we have completed a sweep of the array.
12, 45, 2, 16, 22, 48
Now we know that the largest element of the array is in the last position. Thus, in the next sweep of the array, we do not need to check again the last element. We only need to check the first 5 element of this 6-element array (and in any array, with each subsequent sweep, we check one element less until we arrive at the final sweep, in which there are only the first two elements to check).
Thus, after the second sweep, we would have
12, 2, 16, 22, 45, 48
From this progression arises the name ''bubble'' sort: with each sweep, the next largest element ultimately "bubbles" up to its rightful position within the array until we have a completely sorted array:
2, 12, 16, 22, 45, 48
This sorting algorithm is remarkably slow and inefficient because it requires multiple passes, checking the same elements many times, and only positions one element reliably with each sweep.
'Bubble sort' links
[Edit this page] [Page history] [What links here] [Discuss this topic] [Printer Friendly]
