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
need c++ algorithmic software program to derive one numerical outcome from 10 levels of variables with 135 combinations cross computed

write pseudocode to implement a queue with two stacks

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

Need help with Data Structures assignment requiring C++ program

What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Explain an efficient way of storing two symmetric matrices of the same order in memory. A n-square matrix array is said to be symmetric if a[j][k]=a[k][j] for all j and k. For

Let us assume a file of 5 records that means n = 5 And k is a sorted array of keys of those 5 records. Let key = 55, low = 0, high = 4 Iteration 1: mid = (0+4)/2 = 2

Ask consider the file name cars.text each line in the file contains information about a car ( year,company,manufacture,model name,type) 1-read the file 2-add each car which is repr

Have you ever thought about the handling of our files in operating system? Why do we contain a hierarchical file system? How do files saved & deleted under hierarchical directories

what is folding method?