Shell sort

1. 1

2. 2
Name Nauman Ali
Class BS CS 3
ReG # 024
Indroduction

3. 3
PROJECT NAME

4. 4
Shell Sort – Basic idea


generalization of insertion sort 
Create a gap by half the number of array.
Compare the elements and sort.

Repeat sorting until gap become equal to 1.
For gap Donald Knuth..
Start with h = 1
h = 3*h + 1
h > n
h = (h – 1) / 3

5. 5
Shell Sort - example
825 34 671
Total numbers of element 8.
Initialy Gap = 4
713 54 682

6. 6
Shell Sort - example (2)
725 34 681
Gap =4/ 2
Gap=2
315 82 674

7. 7
Shell Sort - example (3)
123 74 856
315 82 674
Gap = 2/2
Gap=1

8. 8

9. 9
Shell sorting code
for( gap=n/2; gap>0; gap/=2)
{
for( i= gap; i<n; i++ )
{
temp=array[i];
for(j=i; j>=gap && array[j-gap]>temp ; j - = gap)
{

array[j]=array[j-gap];

}
array[j]=temp;
}
}
N=8
Gap = 4

10. 10
references
Youtube and
en.wikipedia.org/wiki/Shellsort

11. 11