Embedded Files
Comparison-based sorting algorithm
Compares and swaps the adjacent elements if out of order
This animation shows a reverse bubble sort (where elements are sorted smallest to biggest in reverse order, different to the algorithm below, which has the sorted elements at the right end of the algorithm).
If ’n’ elements are to be sorted, the process will repeat itself n-1 times before completion.
Out of all the other sorts, it is the most tedious or counter-intuitive, due to its simplicity.
Pseudo-coding the procedure
Pseudo-coding the procedure
A flag variable swap is used which will help us see if any swap has happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it will exit, or come out of the loop.
After every iteration the highest values settles down at the end of the array. Hence, the next iteration need not include already sorted elements. For this purpose, the inner loop is restricted to avoid already sorted values.
Key points
Key points
Efficient for some...
Efficient for some...
Fastest sort available but on an extremely small and or nearly sorted set of data
But not for large data sets
But not for large data sets
This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2) where n is the number of items.
Further links (bibliography) ,
Interactivepython.org. (2018). 5.7. The Bubble Sort — Problem Solving with Algorithms and Data Structures. [online] Available at: http://interactivepython.org/runestone/static/pythonds/SortSearch/TheBubbleSort.html [Accessed 18 Oct. 2018].
HackerEarth. (2018). Bubble Sort Tutorials & Notes | Algorithms | HackerEarth. [online] Available at: https://www.hackerearth.com/practice/algorithms/sorting/bubble-sort/tutorial/ [Accessed 18 Oct. 2018].
YouTube. (2018). Bubble Sort | GeeksforGeeks. [online] Available at: https://www.youtube.com/watch?v=nmhjrI-aW5o [Accessed 21 Oct. 2018].
Qian, Y. (2014). Example 8: The use of a sentinel value in while loops « PD4CS - Python programming, common student misconceptions, student projects. [online] Pd4cs.org. Available at: https://www.pd4cs.org/example-8-the-use-of-a-sentinel-value-in-while-loops/ [Accessed 18 Oct. 2018].
Elearning.algonquincollege.com. (2018). Repetitions Until A Sentinel Value. [online] Available at: http://elearning.algonquincollege.com/coursemat/pincka/dat2219d/lectures/16-SentinelRepetitions.htm [Accessed 18 Oct. 2018].
Chortle.ccsu.edu. (2018). Sentinel Values. [online] Available at: https://chortle.ccsu.edu/QBasic/chapter09/bc09_12.html [Accessed 18 Oct. 2018].
Users.cs.fiu.edu. (2018). Types of loops. [online] Available at: https://users.cs.fiu.edu/~downeyt/cop2210/loops.html [Accessed 18 Oct. 2018].
YouTube. (2018). What is SENTINEL VALUE? What does SENTINEL VALUE mean? SENTINEL VALUE meaning & explanation. [online] Available at: https://www.youtube.com/watch?v=dwk_QZiXBrg [Accessed 18 Oct. 2018].
Webopedia.com. (2018). What is sentinel value? Webopedia Definition. [online] Available at: https://www.webopedia.com/TERM/S/sentinel_value.html [Accessed 18 Oct. 2018].
character?, W. (2018). What's the difference between a Sentinel value and an End-of-file character?. [online] Stack Overflow. Available at: https://stackoverflow.com/questions/43731611/whats-the-difference-between-a-sentinel-value-and-an-end-of-file-character [Accessed 18 Oct. 2018].
Page updated
Report abuse