Mon Apr 19 2021
Bubble Sort
Bubble sort is a simple sorting algorithm that works by repeatedly stepping through the list to be sorted, sometimes referred to as sinking sort. Among various other sorting algorithm, bubble sort algorithm is one of the popular and frequently used algorithm to sort elements either in ascending or descending order.
Bubble sort algorithm starts by comparing the first two elements of an array and swapping if necessary, if we want to sort the elements of array in ascending order and if the first element is greater than second then, we need to swap the elements but, if the first element is smaller than second, we mustn't swap the element. Then, again second and third elements are compared and swapped if it is necessary and this process go on until last and second last element is compared and swapped. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.
Bubble sort has worst-case and average complexity both O(n2), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other O(n2) sorting algorithms, such as insertion sort, tend to have better performance than bubble sort. Therefore, bubble sort is not a practical sorting algorithm when n is large.
File Name: bubble-sort-algorithm.c
/* Bubble Sort */
void bubsort(E A[], int n) {
for (int i=0; i<n-1; i++)
/* Bubble up i'th record */
for (int j=n-1; j>i; j--)
if (Comp::prior(A[j], A[j-1]))
swap(A, j, j-1);
}