what is Shell Sort?

Shell Sort

Shell sort is the generalization of insertion sort which overcomes the drawbacks of insertion sort by comparing elements separated by a gap of several positions. In general, Shell sort performs the following steps.

• Step 1: Arrange the elements in the tabular form and sort the columns by using insertion sort.
• Step 2: Repeat Step 1; each time with smaller number of longer columns in such a way that at the end, there is only one column of data to be sorted.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	Ω(n log(n))	θ(n log(n)2)	O(n log(n)2)
Space Complexity			O(1)

Algorithm

Shell_Sort(Arr, n)

• Step 1: SET FLAG = 1, GAP_SIZE = N
• Step 2: Repeat Steps 3 to 6 while FLAG = 1 OR GAP_SIZE > 1
• Step 3:SET FLAG = 0
• Step 4:SET GAP_SIZE = (GAP_SIZE + 1) / 2
• Step 5:Repeat Step 6 for I = 0 to I < (N -GAP_SIZE)
• Step 6:IF Arr[I + GAP_SIZE] > Arr[I]
  SWAP Arr[I + GAP_SIZE], Arr[I]
  SET FLAG = 0
• Step 7: END

C Program

1. #include <stdio.h>  
2. void shellsort(int arr[], int num)    
3. {    
4. int i, j, k, tmp;    
5. for (i = num / 2; i > 0; i = i / 2)    
6. {    
7. for (j = i; j < num; j++)    
8. {    
9. for(k = j - i; k >= 0; k = k - i)    
10. {    
11. if (arr[k+i] >= arr[k])    
12. break;    
13. else    
14. {    
15. tmp = arr[k];    
16. arr[k] = arr[k+i];    
17. arr[k+i] = tmp;    
18. }    
19. }    
20. }    
21. }    
22. }    
23. int main()    
24. {    
25. int arr[30];    
26. int k,  num;    
27. printf("Enter total no. of elements : ");    
28. scanf("%d", &num);    
29. printf("\nEnter %d numbers: ", num);    
30.   
31. for (k =  0 ; k < num; k++)    
32. {    
33. scanf("%d", &arr[k]);    
34. }    
35. shellsort(arr, num);    
36. printf("\n Sorted array is: ");    
37. for (k = 0; k < num; k++)    
38. printf("%d ", arr[k]);    
39. return 0;    
40. }    

Output:

Enter total no. of elements : 6

Enter 6 numbers: 3
2
4
10
2
1

Sorted array is: 1 2 2 3 4 10 

Java Program

1. import java.util.*;  
2. public class Shell_Sort   
3. {  
4. static void shellsort(int[] arr, intnum)    
5. {    
6. int i, j, k, tmp;    
7. for (i = num / 2; i> 0; i = i / 2)    
8. {    
9. for (j = i; j<num; j++)    
10. {    
11. for(k = j - i; k>= 0; k = k - i)    
12. {    
13. if (arr[k+i] >= arr[k])    
14. break;    
15. else  
16. {    
17. tmp = arr[k];    
18. arr[k] = arr[k+i];    
19. arr[k+i] = tmp;    
20. }    
21. }    
22. }    
23. }    
24. }     
25. public static void main(String[] args)   
26. {    
27. Scanner sc = new Scanner(System.in);  
28. int arr[]= newint[30];    
29. intk,  num;    
30. System.out.println("Enter total no. of elements : ");      
31. num = sc.nextInt();  
32. for (k =  0 ; k<num; k++)    
33. {    
34. arr[k]=sc.nextInt();    
35. }    
36. shellsort(arr, num);    
37. System.out.println("\n Sorted array is: ");    
38. for (k = 0; k<num; k++)    
39. System.out.println(arr[k]);    
40. }    
41. }  

Output:

Enter total no. of elements : 6
3
2
4
10
2
1

Sorted array is: 1 2 2 3 4 10 

C# Program

1. using System;  
2. public class Shell_Sort   
3. {  
4. static void shellsort(int[] arr, int num)    
5. {    
6. int i, j, k, tmp;    
7. for (i = num / 2; i > 0; i = i / 2)    
8. {    
9. for (j = i; j < num; j++)    
10. {    
11. for(k = j - i; k >= 0; k = k - i)    
12. {    
13. if (arr[k+i] >= arr[k])    
14. break;    
15. else    
16. {    
17. tmp = arr[k];    
18. arr[k] = arr[k+i];    
19. arr[k+i] = tmp;    
20. }    
21. }    
22. }    
23. }    
24. }     
25. public void Main()   
26. {    
27.     int[] arr=new int[10];    
28. int k,  num;    
29. Console.WriteLine("Enter total no. of elements : ");      
30. num = Convert.ToInt32(Console.ReadLine());  
31. for (k =  0 ; k < num; k++)    
32. {    
33. arr[k]=Convert.ToInt32(Console.ReadLine());  
34. }    
35. shellsort(arr, num);    
36. Console.WriteLine("\n Sorted array is: ");    
37. for (k = 0; k < num; k++)    
38. Console.WriteLine(arr[k]);    
39. }    
40. }  

Output:

Enter total no. of elements : 6

3
2
4
10
2
1

Sorted array is: 1 2 2 3 4 10