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.                                                                                                    


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
Explain principle of Optimality It indicates that an optimal solution to any instance of an optimization problem is composed of  optimal solutions to its subinstances.

Explain Dijkstra's algorithm Dijkstra's algorithm: This problem is concerned with finding the least cost path from an originating node in a weighted graph to a destination node

Question 1 Write a program in 'C' to read N numbers and print them in descending order Question 2 Discuss the properties of ADT Question 3 Write a note on

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

Readjusting for tree modification calls for rotations in the binary search tree. Single rotations are possible in the left or right direction for moving a node to the root position

1) Which graph traversal uses a queue to hold vertices which are to be processed next ? 2) Which of the graph traversal is recursive by nature? 3) For a dense graph, Prim's a

State the range of operation of ADT Operations of the Range of T ADT includes following, where a, b ∈ T and r and s are values of Range of T: a...b-returns a range value (an

Operations on B-Trees Given are various operations which can be performed on B-Trees: Search Create Insert B-Tree does effort to minimize disk access and t

merging 4 sorted files containing 50 10 25 and 15 records will take time

What is String Carrier set of the String ADT is the set of all finite sequences of characters from some alphabet, including empty sequence (the empty string). Operations on s