Chapter: Programming and Data Structures - Sorting And Searching

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Shell sort

Shell sort, also known as the diminishing increment sort, is one of the oldest sorting algorithms, named after its inventor Donald. L. Shell (1959).

SHELL SORT


Shell sort, also known as the diminishing increment sort, is one of the oldest sorting algorithms, named after its inventor Donald. L. Shell (1959).

Founded by Donald Shell and named the sorting algorithm after him in 1959.

 

      1st algorithm to break the quadratic time barrier but few years later, a sub quadratic time bound was proven

 

      Shell sort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared.

      Shell sort uses a sequence h1, h2,   …t,calledhthe increment sequence. Any increment

sequence is fine as long as h1 = 1 and some other choices are better than others. We can choose the increment sequence with the following range,


#include<stdio.h>

#include<conio.h> h1 1 int main()

{

 

int arr[30];

int i,j,k,tmp,num;

 

printf("Enter total no. of elements : "); scanf("%d", &num);

 

for(k=0; k<num; k++)

{

 

printf("\nEnter %d number : ",k+1); scanf("%d",&arr[k]);

 

}

for(i=num/2; i>0; i=i/2)

 

{

for(j=i; j<num; j++)

 

{

tmp=arr[j];

for(k=j; k>=i; k=k-i)

 

{

if(tmp<arr[k-i])

 

{

 

arr[k]=arr[k-i];

}

 

else

{

 

break;

}

 

arr[k-i]=tmp;

}

 

}

}

 

printf("\t**** Shell Sorting ****\n");

 

for(k=0; k<num; k++) printf("%d\t",arr[k]);

 

getch(); return 0;

}

 

Execution of Algorithm:


For the Span value 5 the comparisons and swapping will be as follows


Now the comparison between 72 and 45 left value should be least value so 45 swapped to first location. Now the altered list was,


Then span 5 repeatedly compare following elements,


On these comparisons with span value 5 the elements 45 and 42 , 65 and 13 are get interchanged.

 

For SPAN=3

 


Then the altered array will be as follows, 


The resultant array is sorted now.

 


Complexity Analysis:




Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.