In this post, I’m going to briefly explain three very basic sorting algorithms: Bubble sort, Selection sort & Insertion sort.
Bubble Sort:
Assume that we have an array of integers that we want to sort: 4,5,1,2,7,8
What would be the most basic thought that would cross your mind? Well, simply to take each pair & see if they are in a wrong order & then re-arrange them.
Why “bubble”?
As we said we exchange each two numbers if they have an incorrect order, so whoever invented this algorithm saw this exchange as some water bubbles that float to change their position!
Let’s do it:
4,5,1,2,7,8–> correct order no change
4,5,1,2,7,8 –> 4,1,5,2,7,8
4,1,5,2,7,8 –>4,1,2,5,7,8
4,1,5,2,7,8–> correct order no change
4,1,5,2,7,8 –> correct order no change
It’s clear that we’re not done though we’ve iterated on the whole set. So we need to loop again & not just once but till n-1 .. which is the count of the number -1.
Again:
4,1,5,2,7,8 –> 1,4,5,2,7,8
1,4,5,2,7,8 –> correct order no change
1,4,5,2,7,8 –> 1,4,2,5,7,8
1,4,2,5,7,8–> correct order no change
1,4,2,5,7,8 –> correct order no change
Third iteration:
1,4,2,5,7,8 –> correct order no change
1,4,2,5,7,8 –> 1,2,4,5,7,8
and we’re done! .. yet there’s one problem .. Bubble sort never knows when it’s done .. so it will just continue iterating until n-1 with each time comparing adjacent numbers. This lead to the introduction of the Modified Bubble Sort algorithm which checks every time if the position of any number has changed, if not it quits.
The complexity of this algorithm is O(n^2). For those who don’t know this means that it needs 2 for loops each of a stopping condition (< length of numbers) to finish sorting at the worst case. Try sorting the numbers when they’re totally reversed 8,7,5,4,2,1 & count the number of steps.
Code (unmodified):
Selection Sort:
This algorithm simply selects the smallest number in the unsorted array & place it in the first place (index =0), then selects the second smallest number & place it in the second place (index =1) .. etc. I guess you concluded why it’s called selection!
Example:
Let’s stick with the same set of numbers:
We have two cursors, the first one is set to the index of the first element (index = 0, we initially assume that it’s the min value) & the second one selects the min value & swaps them
4,1,5,2,7,8 –> 1,4,5,2,7,8
then the first cursor moves to index =1 and assumes that its the min then does the same with the remaining numbers from (4,5,2,7,8)..
<1,4,5,2,7,8 –> 1,2,5,4,7,8
1,2,5,4,7,8 –> 1,2,4,5,7,8 .. Done!
but it will just continue as the bubble sort ..
Code:
Insertion Sort:
This is the most realistic search you would ever meet. It just analogues the way you might sort some cards. Assume that we have 4 cards that are randomly sorted: 7,3,5,9 & that we have a table that we would like to put them sorted on (left to right).
Trace:
You hold the first card: 7 .. well it’s the smallest so far .. so we’ll put it on the left side. The second card is 3 .. OK smaller than 7 .. move 7 to the right and put 3 in the left most place.
Numbers so far: 3,7,5,9
Next, 5 .. smaller than 7, move 7 to the right & put 5 in it’s place .. continue, 5 is not smaller than 3 .. so we’re not exchanging them [3,5,7,9]. Same will happen with 9 but no change would happen .. although it will check anyway.
Implementation:
Now we need to loops .. one to that moves element by element in the array, and the other to compare the element chosen by the first loop to the element next to it. if the element selected by the first loop is smaller than the element selected by the second loop .. we shift the elements to the right to make room for the element selected from the second loop.
Code:
*This post is inspired by: Data Structure & Algorithms using C#, Michael McMillan
But on the other hand, It’s unlikely to happen that Arabic programming languages (in general) would go further; i.e., to be embraced by non-Arabic speaking developers. It’s simple: we know English, they don’t know Arabic. In addition to being convenient to what they have & the continual rapid upgrade of existing frameworks/IDEs.
