Bubble Sort Algorithm
is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements if they are in wrong order. In computer graphics, it is popular for its capability to detect a very small error (like a swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x-axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines.
The average case time complexity is
and the auxiliary space complexity is
Refer the article
for more details and implementations.
Share your thoughts or ask any questions below.
This is a companion discussion topic for the original entry at http://iq.opengenus.org/bubble-sort/