Bubble sort
From Wikiversity
In this learning project we explore bubble sort, the conceptually simplest sorting algorithm. Its idea is to "bubble" the smallest number to the top, by swapping adjacient numbers when need; And then, working with a string with one fewer element, bubble the next smallest number to the top but one, and so on, until no more swaps are possible. Whilst it is a simple algorithm it is also very inefficient.
For more details, see w:sorting algorithm, w:comparison sort, w:bubble sort.
Contents |
[edit] Try your hands on bubble sort
Substitute the following wikitext into the sandbox:
{{subst:bubble sort|5|4|3|2|1}}
{{subst:bubble sort a 5/2|4{{subst:pipe}}5{{subst:pipe}}3{{subst:pipe}}2{{subst:pipe}}1}}
5,4,3,2,1
[edit] What is going on?
[edit] Questions
[edit] In terms of the permutation group
The permutation "initial unordered string ---> final ordered string" is an element of the w:permutation group. The sorting procedure can be thought of as expressing a permutation as a product of elementary transpositions.
[edit] Try your hands
How can we express the permutation (5,4,3,2,1)-->(1,2,3,4,5) as a product of elementary transpositions?
{{subst:bubble sort b|5|4|3|2|1}}
[edit] Further reading
- Other sorting algorithma
