insertion sort:-
One of the simplest sorting algorithms is the insertion sort. The code for the algorithm is as follows: for(i = 1; i <>
Inserted = false; //boolean variable
j = i;
while((j >= 1) && (Inserted == false){
if(List[j] <>
swap(List[j], List[j-1]);
else
Inserted=true;
j--;
}
}
This algorithm works by first considering the first element of the list (element 0) to be correctly placed. It proceeds to the next element (element 1) and compares its value with. If the magnitude is smaller, it swaps it with element 0. Now, elements 0 and 1 are sorted, but only with respect to each other. Element 2 is now considered, and is moved to its correct position with respect to elements 0 and 1, i.e., it may stay where it currently is, or it may be placed between what are now elements 0 and 1, or it may be placed before element 0. To do this, elements 2 and 1 may be swapped, resulting in the placement of element 2 between what is currently element 0 and element 1, and then another swap between what are now elements 0 and 1 may be done to place the element before what is now element 0. This continues over and over again, considering the elements from element 3 through the last element of the list. Each element is placed in its proper position in the part of the list already consider to be sorted. Each element under consideration is swapped with its immediately preceeding neighbour as it moves towards the front of the list. The moment the swapping stops, the element's immediately preceding neighbor has lesser magnitude, and so the current element may be considered to be properly placed.
Complexity:
In this method there are N-1 insert operations. The j-th insert operation inserts a new element into a sorted array of j elements and hence takes at most j comparisions. Thus the total number of comparisions are:
1 + 2 + 3 + ... + (N-1) = N*(N-1)/2 = O(N^2)
INSERTION SORT II
iNSERTION SORT (A)
for j <-- 2 to length[A]
do key<--A[j]
//Insert A[j] into the sorted sequence A[1 . . . .j-1]
i <-- j - 1 while i > 0 and A[i] > key
do A[i + 1] <-- A[i]
i <-- i -1 A[i + 1] <-- key
COUNTING SORT
Counting sort is a linear time sorting algorithm used to sort items when they belong to a fixed and finite set. Integers which lie in a fixed interval, say k1 to k2, are examples of such items.
The algorithm proceeds by defining an ordering relation between the items from which the set to be sorted is derived (for a set of integers, this relation is trivial).Let the set to be sorted be called A. Then, an auxiliary array with size equal to the number of items in the superset is defined, say B. For each element in A, say e, the algorithm stores the number of items in A smaller than or equal to e in B(e). If the sorted set is to be stored in an array C, then for each e in A, taken in reverse order, C[B[e]] = e. After each such step, the value of B(e) is decremented.
The algorithm makes two passes over A and one pass over B. If size of the range k is smaller than size of input n, then time complexity=O(n). Also, note that it is a stable algorithm, meaning that ties are resolved by reporting those elements first which occur first.
This visual demonstration takes 8 randomly generated single digit numbers as input and sorts them. The range of the inputs are from 0 to 9.
COUNTING SORT(A,B,k)
1 for i = 1 to k
2 do c[i] = 0
3 for j = 1 to length[A]
4 do C[A[j]] = C[A[j]] + 1
5 >C[i] now contains the number of elements equal to i
6 for i = 2 to k
7 do C[i] = C[i] + C[i-1]
8 >C[i] now contains the number of elements less than or equal to i
9 for j = length[A] downto 1
10 do B[C[A[j]]] = A[j]
11 C[A[j]] = C[A[J]] - 1
//////////////////////////////////////////////////////////////////////////////////////////////////
HEAP SORT
The heapsort algorithm uses the data structure called the heap. A heap is defined as a complete binary tree in which each node has a value greater than both its children (if any). Each node in the heap corresponds to an element of the array, with the root node corresponding to the element with index 0 in the array. Considering a node corresponding to index i, then its left child has index (2*i + 1) and its right child has index (2*i + 2). If any or both of these elements do not exist in the array, then the corresponding child node does not exist either. Note that in a heap the largest element is located at the root node. The code for the algorithm is:
Heapify(A, i){
l <- left(i)
r <- right(i)
if l <= heapsize[A] and A[l] > A[i]
then largest <- l
else largest <- i
if r <= heapsize[A] and A[r] > A[largest]
then largest <- r
if largest != i
then swap A[i] <-> A[largest]
Heapify(A, largest)
}
Buildheap(A){
heapsize[A] <- length[A]
for i <- |length[A]/2| downto 1
do Heapify(A, i)
}
Heapsort(A){
Buildheap(A)
for i <- length[A] downto 2
do swap A[1] <-> A[i]
heapsize[A] <- heapsize[A] - 1
Heapify(A, 1)
}
Heap Sort operates by first converting the initial array into a heap. The HeapSort algorithm uses a process called Heapify to accomplish its job. The Heapify algorithm, as shown above, receives a binary tree as input and converts it to a heap. The root is then compared with its two immediate children, and the larger child is swapped with it. This may result in one of the left or right subtrees losing their heap property. Consequently, the Heapify algorithm is recursively applied to the appropriate subtree rooted at the the node whose value was just swapped with the root and the process continues until either a leaf node is reached, or it is determined that the heap property is satisfied in the subtree.
The entire HeapSort method consists of two major steps:
STEP 1: Construct the initial heap using adjust (N/2) times on all non-leaf nodes.
STEP 2: Sort by swapping and adjusting the heap (N-1) times.
In step 2, since the largest element of the heap is always at the root, after the initial heap is constructed, the root value is swapped with the lowest, rightmost element. This node corresponds to the last element of the array and so after the swapping the righmost element of the array has the largest value, which is what we want it to have. Consequently, the rightmost element is correctly place, and so the corresponding node becomes a light gray in the tree display depicting the heap. Also, the elements (nodes) chosen for swapping at this point of the algorithm are shown as yellow nodes.
Thereafter, since the value of the lowest, rightmost node has moved up to the root, the heap property of the rest of the heap (minus the gray nodes) has been disturbed. Consequently, now the Heapify process is applied to the rest of the heap (treating the light gray nodes as though they were no longer a part of the heap). Once the rest of the heap is again converted to a proper heap, the swapping process as described in the previous paragraph, followed by the Heapify process is applied again. This continues until the root node of the heap turns light gray - i.e., the root has its correct value. Then, the array is sorted.
At each step of the Heapify algorithm, a node is compared to its children and one of them is chosen as the next root. One level of the tree is dropped at each step of this process. Since the heap is a complete binary tree, there are atmost log(N) levels. Thus, the worst case time complexity of Heapify is O(log(N)). In the Heapsort algorithm, Heapify is used (N/2) times to construct the initial heap and (N-1) times to sort. Thus the Heapsort algorithm has a worst case time complexity of O(N*log(N)).
******************************************************************************
POSTMAN SORT
Postman Sort is probably the newest linear order sorting algorithm for fixed domain sets in use today. It's developers claim that it is also the fastest such algorithm.
The algorithm works by sorting the numbers from their most significant digit to their least significant digit. Significant gain in speed is achieved by sorting the numbers on more than one digit at a time (the actual number is decided based on the size of the computer's memory). The process is also considerably speeded up by using some knowledge of the range in which the numbers lie, for example the fact that digits of octal numbers lie in the range 0 to 7.
For this visual demonstration we have sorted randomly input 9 digit binary numbers, using 3 digits at a time (The use of binary numbers enhances the clarity of the visual representation considerably).
""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""
RADIX SORT
Radix sort is one of the linear sorting algorithms for integers. It functions by sorting the input numbers on each digit, for each of the digits in the numbers. However, the process adopted by this sort method is somewhat counterintuitive, in the sense that the numbers are sorted on the least-significant digit first, followed by the second-least significant digit and so on till the most significant digit.
To appreciate Radix Sort, consider the following analogy: Suppose that we wish to sort a deck of 52 playing cards (the different suits can be given suitable values, for example 1 for Diamonds, 2 for Clubs, 3 for Hearts and 4 for Spades). The 'natural' thing to do would be to first sort the cards according to suits, then sort each of the four seperate piles, and finally combine the four in order. This approach, however, has an inherent disadvantage. When each of the piles is being sorted, the other piles have to be kept aside and kept track of. If, instead, we follow the 'counterintuitive' aproach of first sorting the cards by value, this problem is eliminated. After the first step, the four seperate piles are combined in order and then sorted by suit. If a stable sorting algorithm (i.e. one which resolves a tie by keeping the number obtained first in the input as the first in the output) it can be easily seen that correct final results are obtained.
As has been mentioned, the sorting of numbers proceeds by sorting the least significant to most significant digit. For sorting each of these digit groups, a stable sorting algorithm is needed. Also, the elements in this group to be sorted are in the fixed range of 0 to 9. Both of these characteristics point towards the use of Counting Sort as the sorting algorithm of choice for sorting on each digit (If you haven't read the description on Counting Sort already, please do so now).
The time complexity of the algorithm is as follows: Suppose that the n input numbers have maximum k digits. Then the Counting Sort procedure is called a total of k times. Counting Sort is a linear, or O(n) algorithm. So the entire Radix Sort procedure takes O(kn) time. If the numbers are of finite size, the algorithm runs in O(n) asymptotic time.
A graphical representation of the entire procedure has been provided in the attached applet. This program takes 8 randomly generated 3 digit integers as input and sorts them using Radix Sort.
RADIX-SORT(A,d)
1 for i - 1 to d
2 do use a stable sort to sort Array A on digit i
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
The mergesort algorithm closely follows the divide-and-conquer paradigm. Generally, Merge Sort is considered to be one of the best internal sorting methods. If the data is too large to be accommodated all at once in the memory then one has to use external sorting methods. In external sorting methods small blocks of data are loaded into the memory, sorted using an internal sorting method and written out to a tape or disk. Sorted parts are then merged using variations of the merging algorithm discussed below:
Mergesort(A,p,r){
if p <>
then q <- |(p+ r)/2|
Mergesort(A,p,q)
Mergesort(A,q+1,r)
Merge(A,p,q,r)
}
To sort the entire sequence A, Mergesort(A,1,length[A]) is called where length[A]=N.
Mergesort works by splitting the list into two halves and then sorting each half recursively. Mergesort may be considered to be a tree based algorithm and over here it is executed in a depth first manner. For the above list the algorithm starts by handling the merging of elements as follows (the trend in which the sublists are being considered): 1. First, elements 1 and 2 are handled.
2. Then, elements from 0 through 2 are handled (note the black items indicating the border elements).
3. Then, elements 3 and 4 are handled. After this, elements 5 and 6.
4. Then, elements 3 through 6 are handled.
Subsequently, elements 0 through 6 are handled and so on until elements 0 to 14 are handled.
The Merge algorithm takes two sorted lists and merges them to give a sorted list. It assumes the existence of a temporary merge space whose current contents are shown on the upper canvas of the above applet. Mereg takes the the smaller of the first elements of the two lists and places it into the merge space. When either input list is exhausted, the remainder of the other list is copied to the merge space. The sorted sublist is then copied back from the merge space into the appropriate indices.
Merge Sort algorithm uses the process of merging two sorted lists recursively to accomplish the sorting of an unsorted list. Firstly, two sorted lists of length M and N respectively can be merged in O(M+N) time. If the lists have the same size N then the time will be O(2*N) or O(N).
First, each individual element of the list is considered as a 1-element sorted list. The merge algorithm is then used N/2 times to merge pairs of elements into sorted lists of length 2. This will produce N/2 sorted lists each of length 2. It takes N/2 comparisons to accomplish this. Pairs of 2-element lists are then merged to produce N/4 sorted lists each of length 4. In this case there are N/4 merge operations each taking at most 4 comparisons. This process continues until we have two sorted lists of size N/2 and we merge them in O(N) time. There are log(N) levels of merging. Hence, Merge Sort has a worst-case complexity of O(N*log(N)).
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
HEAPSORT ii
The running time of heapsort is O(N*lgN) i.e. it achieves the lower bound for computational based sorting.
HEAP
The heap data structure is an array object which can be easily visualized as a complete binary tree.There is a one to one correspondence between elements of the array and nodes of the tree.The tree is completely filled on all levels except possibly the lowest,which is filled from the left upto a point.All nodes of heap also satisfy the relation that the key value at each node is at least as large as the value at its children.
Step I: The user inputs the size of the heap(within a specified limit).The program generates a corresponding binary tree with nodes having randomly generated key Values.
Step II: Build Heap Operation:Let n be the number of nodes in the tree and i be the key of a tree.For this,the program uses operation Heapify.when Heapify is called both the left and right subtree of the i are Heaps.The function of Heapify is to let i settle down to a position(by swapping itself with the larger of its children,whenever the heap property is not satisfied)till the heap property is satisfied in the tree which was rooted at (i).This operation calls
Step III: Remove maximum element:The program removes the largest element of the heap(the root) by swapping it with the last element.
Step IV: The program executes Heapify(new root) so that the resulting tree satisfies the heap property.
Step V: Goto step III till heap is empty
Quicksort is based on the divide and conquer approach and inspite of its slow worst case running time, it is often the best practical choice for sorting because it is remarkably efficient on the average. The following code describes the algorithm: QuickSort(A, p, r){
if p <>
then q <- Partition(A, p, r)
QuickSort(A, p, q)
QuickSort(A, q+1, r)
}
To sort an entire array A, the initial call is QuickSort(A, 1, length[A]).
Partition(A, p, r){
x <- A[p]
i <- p - 1
j <- r + 1
while TRUE
do repeat j <- j - 1
until A[j] <= x
repeat i <- i + 1
until A[i] >= x
if i <>
then exchange A[i] <-> A[j]
else return j
}
The algorithm starts by first performing a scan of the entire list, as indicated by the two black items at the two ends of the list. It attempts then to partition the list. The manner in which this partitioning is done is: First, the pivot element is considered to be the first element of the (sub)list being scanned, i.e., element 0. The high-pointer is shown in green and the low-pointer in blue. Scanning of the (sub)list consists of decrementing the high-pointer and incrementing the low-pointer until A[low-pointer]>= A[pivot] >= A[high-pointer]. As the scan of the (sub)list proceeds, the magnitudes of the list elements are compared with the magnitude of the pivot. First the high-pointer is decremented till it meets an element that is less than or equal to the pivot. Then the low-pointer is incremented till it meets an element greater than equal to the pivot. If the low-pointer is less than the high-pointer, then the elements pointed to by these are swapped else the element pointed by the high-pointer becomes the pivot. Conceptually, the partitioning procedure performs a simple function: it puts elemnts smaller than the pivot into the bottom region of the array and elements larger than the pivot into the top region. Now, the same partitioning approach can be recursively applied to the smaller sublist and also to the larger sublist obtained as a result of the partitioning. Repeated applications of this approach to all sublists generated results in a sorted list.
Quicksort works by partitioning the list into two parts. The first partitioning of the N elements in list positions 0 to N-1, compares and swaps them to produce a pivotal index j such that the elements in positions 0 to j-1 are less than or equal to the pivot which is now in the jth position and those elements in positions j+1 to N-1 are greater. This is accomplished in O(N) time.
The first partition produces two sublists such that sorting of each of them results in the sorting of the original list. The partitioning technique is applied recursively to each half until the halves reduce to single-element or empty lists.
Assuming that the list breaks into two halves of equal size, then we have two lists of size N/2 to sort. Each of these has to be partitioned which takes (N/2) + (N/2) = N comparisions. Continuing the same assumption, there will be atmost log(N) splits. This results in the best case time estimate of O(N*log(N)) for quicksort.
In the worst case, the partitioning routine produces one region with (N-1) elements and one with only one element (this happens when the list to be sorted is already sorted). This gives a worst case time of O(N^2). However, quicksort takes O(N*log(N)) in the average case.2
MERGE SORT
The mergesort algorithm is based on the classical divide-and-conquer paradigm. It operates as follows:
DIVIDE: Partition the n-element sequence to be sorted into two subsequences of n/2 elements each.
CONQUER: Sort the two subsequences recursively using the mergesort.
COMBINE: Merge the two sorted sorted subsequences of size n/2 each to produce the sorted sequence consisting of n elements.
Note that recursion "bottoms out" when the sequence to be sorted is of unit length. Since every sequence of length 1 is in sorted order, no further recursive call is necessary. The key operation of the mergesort algorithm is the merging of the two sorted sequencesin the "combine step". To perform the merging, we use an auxilliary procedure Merge(A,p,q,r), where A is an array and p,q and r are indices numbering elements of the array such that dure assumes that the subarrays A[p..q] and A[q+1...r] are in sorted order.It merges them to form a single sorted subarray that replaces the current subarray A[p..r]. Thus finally,we obtain the sorted array A[1..n], which is the solution.
MERGE SORT (A,p,r)
1 if p <>then q<-- [ (p + r) / 2 ] 3 MERGE SORT(A,p,q)
4 MERGER SORT(A,q + 1,r)
5 MERGE(A,p,q,r)
QUICK SORT
Quick sort,is based on the divide-and-conquer paradigm.It is a sorting algorithm with worst case running time O(n^2) on an input array of n numbers.In spite of this slow worst case running time,quicksort is often the best practical choice for sorting because it is remarkably efficient on the average : its expected running time is O(nlgn) and the constants hidden in the O-notation are quite small.Here is the three-step divide-and-conquer process for sorting a typical array A[p . . . r]
DIVIDE:The array >A is partitioned (rearranged) into two nonempty subarrays A[p . . q] and A[q+1 . . r].The index q is computed as a part of this partitioning procedure.
CONQUER:The two subarrays A[p . . q] and A[q+1 . . r] are sorted by recursive calls to quicksort.
COMBINE:Since the subarrays are sorted in place, no work is needed to combine them : the entire array A is now sorted.
QUICK SORT (A,p,r)
1 if p <>then q<-- PARTITION(A,p,r)
3 QUICK SORT(A,p,q)
4 QUICK SORT(A,q + 1,r)
