Study Abroad Education Loan College News Placement Book Shops E - Books Engg-Admission Edu-Classifieds Students-Forum
Easy Studies
 « NS2  Projects »

Home Implementation Of Shell Sort▼

## Implementation Of Shell Sort:

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)

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

⇓ Student Projects ⇓
⇑ Student Projects ⇑