Sorting:
Sorting algorithm is an algorithm that puts elements of a list in a certain order . The most-used orders are numerical order and lexicographical order.
Sorting algorithm classification:
Computaional complexcity.
Memory utilization
Stability-Maintaining relative order of records with equal keys.
No.of comparisions
Methods applied like insertion,exchange,,selection,merging etc.
Sorting is a process of linear ordering of list of objects
Sorting techniques are categoried into:
1. Internal sorting
2. External sorting
Internal sorting:
It takes the place in the main memory of a computer.
Eg: Bubble sort,Insertion sort,Shell sort,Quick sort,Heap Sort,etc
External sorting:
It takes the place in secondary memory of a computer,Since the number of objects to be stored is too large to fit in main memory.
Eg:Merge sort,Multiway Merge,Polyphase merge.
Shell sort:
Shell sort is a sorting algorithm that is a generalization of insertion sort, with two observations:
- insertion sort is efficient if the input is "almost sorted", and
- insertion sort is typically inefficient because it moves values just one position at a time.
Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) . It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.
Analysis of the shell sort:
Worest case performance O(n2)
Best case performance O(n log n)
Average case performance O(n1.5)
Advantages of shell sort:
1. It is one of the fastest algorithms for sorting small number of elements.
2. It requires relatively small amounts of memory.
Alogrithm steps:
Step 1:
The whole array is first fragmented into K segments, where K is preferably a prime number.
Step 2:
Now the whole are is partially sorted.
Step 3:
The value of K is reduced which increase the size of each segment and reduce the no of segments.
Step 4:
The next value of K is chosen so that it is relatively prime to its previous value.
Step 5:
Repeat the step 4 until K=1,at which the array is sorted.
The insertion sort is applied in each segment, so each successive segment is partially sorted.
C Program To Implement Shell Sort
CPP Program To Implement Shell Sort
|