Computer Science‎ > ‎

Arrays and Sorting: Shell Sort (C Program/Java Program source codes, a tutorial and an MCQ Quiz on Sorting)






A few recommendations for Data Structures and Algorithms:
Data Structures, Algorithm Design and Analysis of Complexity


Introduction to Algorithms 3r...
List Price: Rs.525
Our Price: Rs.357
Buy from FlipKart


   Introduction to Algorithms (CLRS) 



Algorithms 4th Edition
Our Price: Rs.599
Buy from FlipKart


 Algorithms (By Robert Sedgewick) 


An Introduction to the Analys...
List Price: Rs.550
Our Price: Rs.500
Buy from FlipKart


Analysis of Algorithms (By Robert Sedgewick) 

 


Basic Sorting and Searching Algorithms for Arrays, at a glance



To go through the C program/ Java Program / source-code, scroll down to the end of this page

Shell Sort


Shell sort works by comparing elements that are distant rather than adjacent elements in an array or list where adjacent elements are compared. Shellsort uses an increment sequence. The increment size is reduced after each pass until the increment size is 1. With an increment size of 1, the sort is a basic insertion sort, but by this time the data is guaranteed to be almost sorted, which is insertion sort's "best case". The distance between comparisons decreases as the sorting algorithm runs until the last phase in which adjacent elements are compared hence, it is also known as diminishing increment sort.

Algorithm:


1. n = length of the list, increment = n/2
2. Do the following until increment>0 i = increment until i<n do the following
Store the value at index i in a temporary variable(temp)
j = i until j>= increment do the following
• If temp is less than the value at index j-increment
Replace the value at index j with the value at index j-increment and
decrease j by increment.
• Else break out of the j loop.
Replace the value at index j with temp and increase i by 1.
Divide increment by 2.

Property:


1. Best-Case Complexity- O(n) when array is already sorted.
2. Worst-Case Complexity-It depends on gap sequence; best known is O( n (log n)2 ) and
occurs when array is sorted in reverse order.
3. Average-Case Complexity- It also depends on gap sequence.
4. O(1) extra space and it is not stable.
5. It’s only efficient for medium size lists. it is a complex algorithm and it’s not nearly as
efficient as the merge, heap, and quick sorts.

The gadget spec URL could not be found


Shell Sort - C Program Source Code

#include<stdio.h>
void ShellSort(int *array, int number_of_elements)
{
        int iter, jter, increment, temp;
        for(increment = number_of_elements/2;increment > 0; increment /= 2)
        {
                for(i = increment; i<number_of_elements; i++)
                {
                        temp = array[i];
                        for(j = i; j >= increment ;j-=increment)
                        {
                                if(temp < array[j-increment])
                                {
                                        array[j] = array[j-increment];
                                }
                                else
                                {
                                        break;
                                }
                        }
                        array[j] = temp;
                }
        }
}
int main()
{
        int number_of_elements;
        scanf("%d",&number_of_elements);
        int array[number_of_elements];
        int iter;
        for(iter = 0;iter < number_of_elements;iter++)
        {
                scanf("%d",&array[iter]);
        }
        /* Calling this functions sorts the array */
        ShellSort(array,number_of_elements);
        for(iter = 0;iter < number_of_elements;iter++)
        {
                printf("%d ",array[iter]);
        }
        printf("\n");
        return 0;
}


Shell Sort - Java Program Source Code

Post to LiveJournal
import java.io.*;
class ShellSort
{
void ShellSort(int array[], int number_of_elements)
{
        int iter, jter, increment, temp,i,j;
        for(increment = number_of_elements/2;increment > 0; increment /= 2)
        {
                for(i = increment; i<number_of_elements; i++)
                {
                        temp = array[i];
                        for(j = i; j >= increment ;j-=increment)
                        {
                                if(temp < array[j-increment])
                                {
                                        array[j] = array[j-increment];
                                }
                                else
                                {
                                        break;
                                }
                        }
                        array[j] = temp;
                }
        }
}
int main()throws IOException
{
    BufferedReader in=new BufferedReader(new InputStreamReader(System.in));
        int number_of_elements;
        System.out.println("Enter the number of elements");
        number_of_elements=Integer.parseInt(in.readLine());
        int array[]=new int[number_of_elements]; 
        int iter;
         System.out.println("Enter the elements one by one");
        for(iter = 0;iter < number_of_elements;iter++)
        {
                array[iter]=Integer.parseInt(in.readLine());;
        }
        /* Calling this functions sorts the array */
        ShellSort(array,number_of_elements); 
        for(iter = 0;iter < number_of_elements;iter++)
        {
               System.out.print(array[iter]+"\t");
        }
        System.out.print("\n");
        return 0;
}
}
Related Tutorials :

Bubble Sort    

One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort

Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort. 

Selection Sort

Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort. 

 Shell Sort

An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort 

An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort

In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort

 Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure. 

Binary Search Algorithm

 Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time. 



Testing Zone For Programmers- 

Try out our online Multiple-Choice-Question tests in Programming and Computer Science!



Photo-credits: www.istockphoto.com

 Quizzes on Basic Object Oriented Programming with C++   Quizzes on Java Programming
 Quizzes on C Programming- Arrays, Strings and Pointers
  1. C Programming MCQ Quiz #1:  Strings- 1
  2. C Programming MCQ Quiz #2: Strings (2)
  3. C Programming MCQ Quiz #3: Strings (3)
  4. C Programming MCQ Quiz #4: Arrays(1)
  5. C Programming MCQ Quiz #5: Arrays (2)
  6. C Programming MCQ Quiz #6: Arrays (3)
  7. C Programming MCQ Quiz #7: Pointers (1)
  8. C Programming MCQ Quiz #8: Pointers (2)
 Quizzes on Data Structures, Algorithms and Complexity
  1. MCQ Quiz #1: The Basics of Sorting Algorithms- Quadratic Sorts
  2. MCQ Quiz #2: Efficient Sorting Algorithms- Quick sort, Merge Sort, Heap Sort
  3. MCQ Quiz #3- The Radix Sort
  4. MCQ Quiz #4: Divide and Conquer Techniques- Binary Search, Quicksort, Merge sort, Complexities
  5. MCQ Quiz #5- Dynamic Programming
  6. MCQ Quiz #6- Complexity of Algorithms
  7. MCQ Quiz #7- Application of Master's Theorem
  8. MCQ Quiz #8: Binary Search Trees
  9. MCQ Quiz #9: B-Trees
  10. 10 MCQ Quiz #9: AVL-Trees
  11. 11 MCQ Quiz #10: Representing Graphs as Data Structures
  12. 12 MCQ Quiz #11: Spanning Trees
  13. 13 MCQ Quiz #12: Algorithms - Graphs: Spanning Trees - Kruskal and Prim Algorithms
  14. 14 MCQ Quiz #13: Algorithms - Graphs: Depth and Breadth First Search


The gadget spec URL could not be found



 






Tutorials on Sorting- at a glance

 Bubble Sort One of the most elementary sorting algorithms to implement - and also very inefficient. Runs in quadratic time. A good starting point to understand sorting in general, before moving on to more advanced techniques and algorithms. A general idea of how the algorithm works and a the code for a C program.

Insertion Sort - Another quadratic time sorting algorithm - an example of dynamic programming. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs insertion sort.

Selection Sort - Another quadratic time sorting algorithm - an example of a greedy algorithm. An explanation and step through of how the algorithm works, as well as the source code for a C program which performs selection sort.

Shell Sort- An inefficient but interesting algorithm, the complexity of which is not exactly known.

Merge Sort An example of a Divide and Conquer algorithm. Works in O(n log n) time. The memory complexity for this is a bit of a disadvantage.

Quick Sort In the average case, this works in O(n log n) time. No additional memory overhead - so this is better than merge sort in this regard. A partition element is selected, the array is restructured such that all elements greater or less than the partition are on opposite sides of the partition. These two parts of the array are then sorted recursively.

Heap Sort- Efficient sorting algorithm which runs in O(n log n) time. Uses the Heap data structure.

Binary Search Algorithm- Commonly used algorithm used to find the position of an element in a sorted array. Runs in O(log n) time.


Try out our Quizzes!