Compare and contrast various sorting techniques, Data Structure & Algorithms

Q. Compare and contrast various sorting techniques or methods with respect to the memory space and the computing time.                                                                                                    

Ans:

Insertion sort:- Because of the presence of nested loops, each of which can take n iterations, insertion sort is O(n2). This bound is very tight, because the input in reverse order can actually achieve this bound. So complexity is equal to= (n(n-1))/2 = O(n2). Shellsort: - The running time of Shellsort depends on the option of increment sequence. The worst-case running time of the Shellsort, using the Shell's increments, is (n2).

Heapsort:- The basic approach is to build a binary heap of the n elements. This stage takes the O(n) time. We then perform n delete_min operations on it. The elements leave the heap smallest first, in the sorted order. By recording these elements in the second array and then copying the array back again, we sort the n elements. Since each delete_min takes O(log n) time, the total running time becoms O(n log n).

Mergesort:- Mergesort is a the example of the techniques which is used to analyze recursive routines. We may assume that n is a power of 2, so that we always divide into even halves. For n = 1, the time to mergesort is constant, to which we will

The two recursive mergesorts of size n/2,  in addition the time to merge, which is linear. The equations below say this exactly:

T(1) = 1

T(n) = 2T(n/2) + n

Quicksort:-  Similar to  mergesort,  quicksort  is  recursive,  and  hence,  its  analysis needs solving a recurrence formula. We will do the analysis for a quicksort, assuming a random pivot (no median-of-three partitioning) and no cutoff for such small files. We will take T(0) = T(1) = 1, as in mergesort. The running time of quicksort is equal to the running time of the two recursive calls an addition to the linear time spent in the partition (the pivot selection takes some constant time). This gives the basic quicksort relation as follows

T(n) = T(i) + T(n - i - 1) + cn

Posted Date: 7/11/2012 1:32:01 AM | Location : United States







Related Discussions:- Compare and contrast various sorting techniques, Assignment Help, Ask Question on Compare and contrast various sorting techniques, Get Answer, Expert's Help, Compare and contrast various sorting techniques Discussions

Write discussion on Compare and contrast various sorting techniques
Your posts are moderated
Related Questions
The advantage of list over Arrays is flexibility. Over flood is not a problem until the computer memory is bushed. When the individual record are quite large, it may be difficult t

What are the Dynamic arrays Dynamic arrays are convenient for programmers since they can never be too small-whenever more space is needed in a dynamic array, it can simply be e

Q. What do you understand by the term sparse matrix? How sparse matrix is stored in the memory of a computer? Write down the function to find out the transpose of a sparse matrix u

Q. Write down an algorithm to delete the specific node from binary search tree. Trace the algorithm to delete a node (10) from the following given tree. Ans. Algor

Data array A has data series from 1,000,000 to 1 with step size 1, which is in perfect decreasing order. Data array B has data series from 1 to 1,000,000, which is in random order.

adjacency multilist

nested for loop for (i = 0; i for (j = 0; j sequence of statements } } Here, we observe that, the outer loop executes n times. Every time the outer loop execute

what are grounded header linked lists?

RENDERING, SHADING AND COLOURING By introducing hidden line removal we have already taken one step away from wire-frame drawings towards being able to realistically model and d

red black tree construction for 4,5,6,7,8,9