Algorithm: Sorting and Insertion Sort

Algorithm Binary Search Insertion sort Sorting Techniques

Algorithm: Sorting and Insertion Sort

Hey folks,
Hope you all are doing well.

Today, I attended an online lecture about sorting and insertion sort on MIT Open CourseWare.
So here are the things I've learnt from it.

First of all sorting. Why sorting is required ?
Well this question deserves a lot of discussion but due to time and space limit I'll be discussion some important aspects of the sorting with some real world applications.

First, you all know what sorting is, right ? If not sure, please visit this Wikipedia Article for the same.
Now, some of the applications of sorting are: arrangement of phonebook, or arrangement of media files or gallery files based on the specific criteria like based on name, size or date of creation etc.

Now some real world application: To find Median of given list. Median is a value in bunch of numbers where the quantity of the numbers less than the median are equal to the quantity of the numbers greater than the median. I guess this would be complex a little bit, but once you understand the above statement, it will be very easy for you to remember it.

Now the insertion sort.
Insertion Sort:

Here is the basic algorithm for the insertion sort. Its an abstract form of the algorithm,

For i=1,2,3...n
insert A[i] into sorted array A[0, i-1] by pairwise comparison and swaps down to the correct position.

This is the basic or the critical section of the algorithm. Lets understand the working using the below trace.

Step 1:
Given list is 5, 2, 4, 6, 1, 3
Total number of elements n=6

Note: Why didn't we take A[0] as a key.?
Answer: Its obvious not to compare the element with it self. So we will take the first element and compare it with the next one. Hope it is clear to you people.

Step 2:
Now that we have performed the swap, we need to update the base element and the key for the next comparison.

Now again, we will be comparing 5 and 4, and swap if required.

Step 3:
Now the key value and base element will be updated again.

Here the key is actually greater than the base element, so now swap will be performed, the base list will remain unchanged for the next iteration.

Step 4:
Now the key value will be again changed and the base element will be updated.

Note that, after the first swap, the key will remain unchanged until it compares with the remaining elements in the sorted list. Remember the definition here. Placing the A[i] in the sorted array A[0, i-1] in the correct position.

So Key element will be compared with 6, 5, 4, and 2 and swap all the way with all the elements to find the correct position for that element, until it finds out the correct position for itself.

Step 5:
Now again the key will be updated to 3 and base element will be updated to A[4] which is 6 in our case. And again the above method will be applied.

After following 6 steps of the above mentioned method, we will get out sorted list.

Conclusion:

Here you can see that,
Compares >> swaps
It means, the compare operations are way more than the swap operations which makes this algorithm A[n*n] (That is n square actually, but I don't know how to represent it here on the blogger]

One option to solve this is using binary search on the already sorted array A[0, i-1] and place the element at the correct position.

This variation of the algorithm is technically called binary insertion sort which follows given steps:
1. Binary search for the best suitable position for the A[i] element,
2. Swap, similar to the swaps being performed in the insertion sort.

Thats it. Thats all what I got from the lecture. Hope it helps you people in the process of understanding the algorithms.

...... Next Time.... :) :)

22:56

Algorithm: Counting Sort

Algorithm Counting Sort Radix Sort Sort Sorting Techniques

Algorithm: Counting Sort

Hey folks, whats up..?

I've reading about algorithms a lot lately. I have this awesome site GeeksforGeeks, they teach all things about computer, such as algorithms, data structures, c, c++ and some of the interview experiences from the people who got selected in the IT Giants like Google, Facebook, Amazon etc..

I was reading about radix sort when encounter a problem with some fraction of the program. So moderator of the site suggested me another algorithm to understand the radixsort. That is counting algorithm. Here are the details.

Counting sort  is a sorting technique based on keys between a specific range. It works by counting the number of objects having distinct key values (kind of hashing). Then doing some arithmetic to calculate the position of each object in the output sequence.

Let us understand it with the help of an example.

For simplicity, consider the data in the range 0 to 9. 
Input data: 1, 4, 1, 2, 7, 5, 2
  1) Take a count array to store the count of each unique object.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  2  0   1  1  0  1  0  0

  2) Modify the count array such that each element at each index 
  stores the sum of previous counts. 
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     0  2  4  4  5  6  6  7  7  7

The modified count array indicates the position of each object in 
the output sequence.
 
  3) Output each object from the input sequence followed by 
  decreasing its count by 1.
  Process the input data: 1, 4, 1, 2, 7, 5, 2. Position of 1 is 2.
  Put data 1 at index 2 in output. Decrease count by 1 to place 
  next data 1 at an index 1 smaller than this index.

Following is C implementation of counting sort.

// C Program for counting sort #include <stdio.h> #include <string.h> #define RANGE 255   // The main function that sort the given string str in alphabatical order void countSort(char *str) {     // The output character array that will have sorted str     char output[strlen(str)];       // Create a count array to store count of inidividul characters and     // initialize count array as 0     int count[RANGE + 1], i;     memset(count, 0, sizeof(count));       // Store count of each character     for(i = 0; str[i]; ++i)         ++count[str[i]];       // Change count[i] so that count[i] now contains actual position of     // this character in output array     for (i = 1; i <= RANGE; ++i)         count[i] += count[i-1];       // Build the output character array     for (i = 0; str[i]; ++i)     {         output[count[str[i]]-1] = str[i];         --count[str[i]];     }       // Copy the output array to str, so that str now     // contains sorted characters     for (i = 0; str[i]; ++i)         str[i] = output[i]; }   // Driver program to test above function int main() {     char str[] = "geeksforgeeks";//"applepp";       countSort(str);       printf("Sorted string is %s\n", str);     return 0; }

Output:

Sorted character array is eeeefggkkorss

Time Complexity: O(n+k) where n is the number of elements in input array and k is the range of input.
(You might be thinking what is time complexity. Here is the WikiPedia Article on that.)

Auxiliary Space: O(n+k)

Points to be noted:
1. Counting sort is efficient if the range of input data is not significantly greater than the number of objects to be sorted. Consider the situation where the input sequence is between range 1 to 10K and the data is 10, 5, 10K, 5K.
2. It is not a comparison based sorting. It running time complexity is O(n) with space proportional to the range of data.
3. It is often used as a sub-routine to another sorting algorithm like radix sort.
4. Counting sort uses a partial hashing to count the occurrence of the data object in O(1).
5. Counting sort can be extended to work for negative inputs also.

Exercise:
1. Modify above code to sort the input data in the range from M to N.
2. Modify above code to sort negative input data.
3. Is counting sort stable and online?
4. Thoughts on parallelizing the counting sort algorithm.

00:36