I’m going to discuss some sorting methods used in computing in this post. By the way, sorting is a way of arranging objects in a list or an array or a sequence of numbers. This is a typical computer science knowledge so don’t get confused if you don’t know what l’m talking about. For a simple illustration, Lets say I have these numbers in an array and I want to arrange them in order: {3,5,2,1,8,4}. To arrange these numbers, lets say in ascending order( from smallest to highest), computer scientist employ different types of techniques to solve the problem. Now, some of the techniques are so traditional that almost all of us do it everyday but only that on average, we barely know we are acting as geniuses lol. So let’s discuss some methods we can sort the above array.
First , let’s talk about selection sort. The idea behind selection sort is that, you try to find the smallest element in the array and put it in the first place, then you move to the second place and find the smallest element in the remaining array and put it there. You continue in this manner until all the array is sorted. This is a linear deterministic algorithm because you traverse the array linearly, from beginning to end. Lets do a simple Pseudo-code to illustrate that idea. By the way, a pseudocode is a way of expressing the logic or the steps necessary to complete a programming task in the form of English expression.
Let’s say the array is identified by the letter “A” , and we use A.length to indicate the length of the array A.
SelectionSort(A)
{
For i = 0 to A.length // Start from the beginning of Array to the end
{
smallest <- A[i]; // Assume the element at i is the smallest to put in that location
for j = i+1 to A.length // another loop starting from next array index away from i
{
if A[j]< smallest // if the value next to i is smaller than the one we chose to be smallest?
smallest <- A[j] // Put that value in smallest rather
}
A[i] <- smallest // put the smallest in the location i
}
}//end
Another technique use to sort is Insertion Sort. The idea behind insertion sort is used in playing Cards. Assuming you want to arrange cards so you can easily know what to drop next in other of superiority, the traditional way is to put your cards down and pick one at a time and put into your left hand, making sure that, those in the left hand are arranged all the time. So let’s say, you place your cards face down on a table, you pick a card and put it in your left hand, pick another one and find the location in your left hand that will make all cards in the left arranged. continue this till all the card on the table is finished. Then all the cards in your left hand is sorted or arranged in order. Practice this at home to get the idea better.
With that idea in mind, let’s try to come out with an algorithm to do exactly that;
Insertion Sort (A)
{
for j = 2 to A.length // starting from second element in the array, that means I’m assuming the first element is now in my left hand
{
Key <- A[j]; // the element at J is our element that we’ll find it’s proper location in the left card
i = j-1;
while(i > 0 and A[i] > key)
{
A[i+1] = A[i];
i = i-1;
A[i+1] = key;
}
}
}//end
Our next algorithm to discuss is Merge Sort. This is a divide and conquer method of sorting.
The idea is that, we divide our array into 2 and perform sorting on it, using merge sort. It is built on the knowledge that when you have a big problem and you break it down into smaller units, you can solve it more easily than trying to solve the big junk at once. So what you do is divide the array into two, continue dividing those sub units into two until there is no more any division available for those units. With those little sub units, you are going to combine them to form the bigger array back and in doing so, you are going to make sure that the combination is done in such a way that each combined unit is sorted; that is from smallest to highest in every combination. continue this until all units are combined to form a sorted array of the array.
Merge sort has a subroutine that merges or combine the broken down units to form bigger units. So let’s try to write the Algorithm
Merge Sort(A,p,r) // A is the array, p is the beginning of the array, r is the last index of the array
{
if (p < r)// if there is more than one element in the array
{
q = floor( (p+r)/2) // q is the middle of the array.
Merge Sort(A,p,q) // Merge sort the first half of the array, this is a recursive call.
Merge Sort(A,q+1,r) // Merge Sort the other half of the array
}
Merge(A,p,q,r) // this is the subroutine that will combine the smaller units, making sure they remain sorted when combined
}//end of the mergesort
now we have to define our subroutine to merge two smaller units until the bigger array is formed
Merge(A,p,q,r)
{
n1 = q – p +1 // n1 is the length of the sub-Array from 1 to p
n2 = r – q // n2 is the length of sub-array from middle to end
//we are going to form two arrays and call it left and right with length n1+1 and n2+1 respectively
//make array right[1–n+1], left[1–n2+1]
for i = 1 to n1
left[i] = A[i];
for j = 1 to n2;
right[j] = A[q+j];
left[n1+ 1]= infinity // to identify end of this subarray
right[n2+1] = infinity
i = 1;
j = 1 ;
for k = p to r
{
if (left[i] <= right[i])
{
A[k] = left[i];
i=i+1;
}
else
{
A[k]= right[j];
j = j+1;
}
}
}//end of merge subroutine
Other methods of sorting are quicksort, bubble sort, heapsort etc.
Let me just quickly explain what these methods do,
In quick sort, the idea is to find a pivot to divide the array and do some arrangement such that, all elements to the left of the pivot are either smaller or equal to the pivot and all those on the right are bigger than the pivot. You continue the process on each sub part of the division until there is no more any division possible. Because in the process, you are making sure that the elements are always arranged in order, when you are done through the division process, all the elements will be in sorted order. Quick sort is an in place divide and conquer sorting method. That means, you don’t have to create a new array to help you sort the elements. The operation is done on the same array until the process completes.
lets perform quicksort on our array step by step and see what happens
A = 3,5,2,1,8,4. first let’s randomly chose a pivot, say 4. then what we do next is to partition the array such that all elements smaller or equal to four are to the left and those greater than 4 are to the right of 4 in the array. To do this, you point one left finger to the first element in the array and and one right finger to the last element in the array. start to move the left finger to the right until it points to an element that is bigger or equal to the pivot chosen, in our case, we stop at element 5 because 5 is greater than 4. Then we move our right finger to the left until we find an element that is smaller or equal to the pivot. In our case, our right finger will stop on element 4 because 4 is equal to the pivot we have chosen( that is 4). when we reach these two conditions, we swap those two elements on which the left and right fingers are pointing. So this is what happens
A = 3,4,1,2,8,5,
we have swapped 4 and 5. we continue in this manner again. Now, because our left hand is pointing to 4 which is greater or equal to the pivot, we can’t move yet because the only condition that allows it to move to the right is when it points to an element that is not greater or equal to the pivot. so the left finger will remain on 4 and the right finger will move till it reaches 2, it stops because 2 is less or equal to the pivot. we do the swap again. here is what happens
A = 3,2,1,4,8,5.
Now our right finger is pointing to 4, it can not move because it only moves if the value it points to is not less or equal to the pivot. the right finger will move till it reaches 4 because at that point, it’s condition to cause it to stop has arrived. The process stops when the to fingers points to the same element.
A = 3,2,1,4,8,5
The next step is to repeat the procedure on the partition of the array that is to the left of the pivot and to the right of the pivot. you will select pivots for each partition and perform this same process. so let’s write the our current array in the form of a partitition.
A = 3, 2, 1 4 8,5
let’s take the left partition and perform the procedure on it. we randomly chose a pivot for this partition say 1. then we put out fingers where they are supposed to be and perform the above mentioned steps.
A = 1,2,3 4 8, 5 ,
we swap the value 1 and 3 because right finger points to 1 which is less or equal to pivot(1) and the left finger points to 3 which is greater or equal to pivot (1). After this , the left finger remains on 1, the right finger will move till it reaches one and both hands meet so that will be the end of that operation. we move to the other partion and chose 5 as our pivot. right hand can not move because it points to an element that is equal or less than the pivot, left hand points to 8 which is greater than pivot so we have to perform a swap of the values point by our right and left hands.
A = 1, 2, 3 4 5 ,8
the right hand will move but the left hand can not because the left hand is point to 5 which is not less than our pivot but the right hand is pointing to 8 which is greater than the pivot so it will move to 5 where both hands meet and the operation stops.
Now we have our array as
A = 1, 2, 3, 4, 5, 8
The procedure continues to partition each sub partition into smaller parts until there is no more partitioning available.
so this is our new partitions
A = 1,2 3 4 5 8
The partition made of 3 is single element so it’s done, so is the partition for 5 and the partition for 8. That means, as soon as you put your right and left hands on the element, they meet so the operation ends.
The only partition to operate on is 1,2. We randomly choose our pivot to be 2, then placing the right and at the end and left finger at the beginning of this partition we repeat the procedure. it will be realized that we can’t swap anything before the hands meet. We then partition smaller partitions again.
A = 1 2 3 4 5 8
At this time all our partitions are made up of single elements so we can not do further surgery on them. they have surferred enough lol.
The array is now sorted and the program ends.
Now let’s see if we can write a simple algorithm to do what we were doing in the quick sort definition above. This is going to be dangerous, I know lol.
QuickSort(A, size)
{
if (size < 2)// if the array has less than 2 elements, it’s already sorted
return
pivot = A[rand() % size]; // you can choose to select any element for the pivot say A[last]
leftpointer = 0; // point left hand to first element
rightpointer = size – 1;// point right hand to end of array
while leftpointer < rightpointer
{
while A[leftpointer] < pivot // as far as the element pointed to by leftpointer is less than the pivot
leftpointer = leftpointer + 1; // move the leftpointer to the right one step
while A[rightpointer] > pivot // as far as the element pointed to by rightpointer is greater than the pivot
rightpointer = rightpointer – 1; // move the rightpointer to the left one step
swap( A[leftpointer],A[rightpointer);// swap the values pointed to by the left and right pointers
}
quicksort(A,leftpointer);
quicksort(A[leftpointer+1], size-leftpointer-1]
}//end of quick sort
Another sorting method is bubble sort, let me think of a traditional way of defining bubble sort. Ok, let’s say we have different sizes of people available and we want to arrange them by their height. so we put all the people in a long line. Then we start from the beginning of the line and compare each pair of people in a manner that, the tallest person will be moved forward to be compared with the next element. You continue this till you reach the end of the line, then the person at the end of the line now is the tallest person so leave him untouched in subsequent operations. go back to the beginning of the line and perform the operation again till you reach the end of the line – number of people already found to be tallest (without comparing to the ones you have already declared to be the tallest in previous steps).
Do this till there are no more elements to compare with each other. Then the people are arranged from the shortest to the tallest.
lets use numbers to go through this process. Assuming we are sorting our array. I’m going to use [ ] to indicate the part of the array that is already sorted.
A = 3,5,2,1,8,4. Start by comparing and switching, first 3 and 5, then 5 and 2,
A= 3,2,5,1,8,4. we swap 5 and 2 because 5 is greater than 2.
A = 3,2,1,5,8,4. we swap 5 and 1 because 5 is greater than 1
A = 3,2,1,5,8,4. we don’t swap because 8 is already greater than 5
A = 3,2,1,5,4,[8]. we swap 8 and 4 because 8 is greater than 4
We have reached the end so we go back and do the process again but we don’t have to compare anything with 8.
A = 2,3,1,5,4,[8]. we swap 2 and 3 because 3 is greater than 2
A = 2,1,3,5,4,[8]. we swap 3 and 1 because 3 is greater than 1
A = 2,1,3,5,4,[8]. we don’t swap 5 and 3 because they are in the right other
A = 2,1,3,4,[5,8]. we swap 5 and 4 because 5 is greater than 4
We are done with this step so we go back and start again.
A= 1,2,3,4,[5,8]. we swap 2 and 1 because 2 is greater than 1
A = 1, 2, 3, 4,[ 5, 8]. Do nothing, they are in the correct order
A = 1, 2, 3, [4, 5, 8]. Do nothing, they are in the correct order
we have reached the end of this step, so we go back to the beginning.
A = 1,2,3,[4,5,8]
A= 1,2,3,[4,5,8]. do nothing
A = 1,2,[3,4,5,8]. do nothing, end of this step
We go to the beginning again
A =1,[2,3,4,5,8]. do nothing, end of this step
go back to the beginning and start
A = [1,2, 3, 4, 5, 8]. we have only one element so that’s the end of the procedure.
Our array is now sorted in ascending order.
Here is the algorithm for bubble sort
bubble sort(A,size)
{
for i = size-1 downto 1
{
for j = 0 to i-1
{
if A[j] > A[j+1]
swap(A[j],A[j+1])
}
}
}end of bubble sort
bubble sort is not a good choice when it comes to speed. You can see you keep comparing things over and over even thought the array is already sorted from some point on.
I can’t write on the other sorting methods now but if someone have a question about anything, please post it for discussion.
