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
A small shop sells 280 different items. Every item is identified by a 3 - digit code. All items which start with a zero (0) are cards, all items which start with a one (1) are swee

Double ended queues are implemented along doubly linked lists. A doubly link list can traverse in both of the directions as it contain two pointers namely left pointers and righ

an electrical student designed a circuit in which the impedence in one part of a series circuit is 2+j8 ohms and the impedent is another part of the circuit is 4-j60 ohm mm program

Write the algorithm for Binary search. Also apply this algorithm on the following data. 22, 44, 11, 88, 33, 55, 77, 66

Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

Q. How do we represent a max-heap sequentially? Explain by taking a valid   example.         Ans: A max heap is also called as a descending heap, of size n is an almos

A linear list of elements in which deletion can be done from one end (front) and insertion can take place only at the other end (rear) is called as a   Queue.

What are stored and derived attributes?  Stored attributes: The attributes kept in a data base are called stored attributes.  Derived attributes: The attributes that are

1)      Why space complexity is comparatively more critical than time complexity? 2)      Determine the space complexity of Euclid Algorithm?

Depth-first traversal A depth-first traversal of a tree visit a node and then recursively visits the subtrees of that node. Likewise, depth-first traversal of a graph visits