Sorting Algorithms Comparison
Not what you're looking for?
We have considered the following sorting algorithms in this book:
Heap, Insertion, Merge, Quicksort, Radix, Selection
For each sort, give the average and worst case running time and the space requirements, and make some additional comments about the efficiency of the algorithm. The additional comments may specify how probable the worst case is, the number of interchanges performed by the algorithm, and special situations that make the algorithm run faster
Purchase this Solution
Solution Summary
The average and worst case running time and the space requirements for each of the sorting algorithms Heap, Insertion, Merge, Quicksort, Radix, Selection are given.
Solution Preview
Complexities below are in terms of:
- n, the number of items to be sorted,
- k, the size of each key, and
- s, the chunk size used by the implementation
Best Average Worst Space Stable Method Efficiency
Heap O(n log n) O(n log n) O(n log n) O(1) No Selection One of the best general-purpose sorting algorithms, a comparison sort and part of the selection sort family. Although somewhat slower in practice on most machines than a good implementation of quicksort, it has the advantages of worst-case O(n log n) runtime. Heapsort is an in-place algorithm and is not a stable sort.
Insertion O(n) O(n+d) O(n2) O(1) Yes Insertion d is number of inversions which is O(n2). This is
a simple sorting algorithm that is relatively efficient for small lists and mostly-sorted lists
Merge O(n log n) O(n log n) O(n log n) O(n) auxiliary space Yes Merging Takes advantage of the ease of merging already sorted lists into a new sorted list. Scales well to very large lists.
Quicksort O(n log n) O(n log n) O(n2) O(log n) extra storage ...
Purchase this Solution
Free BrainMass Quizzes
C++ Operators
This quiz tests a student's knowledge about C++ operators.
Word 2010: Tables
Have you never worked with Tables in Word 2010? Maybe it has been a while since you have used a Table in Word and you need to brush up on your skills. Several keywords and popular options are discussed as you go through this quiz.
Javscript Basics
Quiz on basics of javascript programming language.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.