GeeksforGeeks
A computer science portal for geeks Practice GATE CS Placements Videos Contribute
Login/Register
Skip to content
ShellSort
ShellSort is mainly a variation of Insertion Sort. In insertion sort, we move elements only one position
ahead. When an element has to be moved far ahead, many movements are involved. The idea of
shellSort is to allow exchange of far items. In shellSort, we make the array h-sorted for a large value
of h. We keep reducing the value of h until it becomes 1. An array is said to be h-sorted if all sublists
of every hth element is sorted.
Following is C++ implementation of ShellSort.
C++
Java
// Java implementation of ShellSort
class ShellSort
/* An utility function to print array of size n*/
static void printArray(int arr[])
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
System.out.println();
}
/* function to sort arr using shellSort */
int sort(int arr[])
int n = arr.length;
// Start with a big gap, then reduce the gap
for (int gap = n/2; gap > 0; gap /= 2)
// Do a gapped insertion sort for this gap size.
// The first gap elements a[0..gap-1] are already
// in gapped order keep adding one more element
// until the entire array is gap sorted
for (int i = gap; i < n; i += 1)
// add a[i] to the elements that have been gap
// sorted save a[i] in temp and make a hole at
// position i
int temp = arr[i];
// shift earlier gap-sorted elements up until
// the correct location for a[i] is found
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
// put temp (the original a[i]) in its correct
// location
arr[j] = temp;
return 0;
// Driver method
public static void main(String args[])
int arr[] = {12, 34, 54, 2, 3};
System.out.println("Array before sorting");
printArray(arr);
ShellSort ob = new ShellSort();
ob.sort(arr);
System.out.println("Array after sorting");
printArray(arr);
/*This code is contributed by Rajat Mishra */
Python
Output:
Array before sorting:
12 34 54 2 3
Array after sorting:
2 3 12 34 54
Time Complexity: Time complexity of above implementation of shellsort is O(n2). In the above
implementation gap is reduce by half in every iteration. There are many other ways to reduce gap
which lead to better time complexity. See this for more details.
References:
https://www.youtube.com/watch?v=pGhazjsFW28
http://en.wikipedia.org/wiki/Shellsort
Snapshots:
scene00721
scene00793
scene00937
scene01009
scene01801
scene02305
Quiz on Shell Sort
Other Sorting Algorithms on GeeksforGeeks/GeeksQuiz:
Selection Sort
Bubble Sort
Insertion Sort
Merge Sort
Heap Sort
QuickSort
Radix Sort
Counting Sort
Bucket Sort
Coding practice for sorting.
Please write comments if you find anything incorrect, or you want to share more information about
the topic discussed above
GATE CS Corner Company Wise Coding Practice
Sorting
Recommended Posts:
Comb Sort
Cycle Sort
Merge Sort
Radix Sort
Sorting Terminology
Post navigation<< Previous PostNext Post >>
(Login to Rate and Mark)
0 Average Difficulty : 0/5.0
No votes yet.
Add to TODO List
Mark as DONE
Writing code in comment? Please use ide.geeksforgeeks.org, generate link and share the link here.
Share this post!
Trending Content
Printing Longest Common Subsequence
Modular multiplicative inverse
Segregate 0s and 1s in an array
Priority Queue | Set 1 (Introduction)
Reverse a stack using recursion
Dynamic Programming | Set 27 (Maximum sum rectangle in a 2D matrix)
A Programmers approach of looking at Array vs. Linked List
Union-Find Algorithm | Set 2 (Union By Rank and Path Compression)
Commonly asked Computer Networks Interview Questions | Set 1
Divide and Conquer | Set 1 (Introduction)
ProGeek Cup 1.0
Most Visited Posts
Top 10 Algorithms and Data Structures for Competitive Programming
Top 10 algorithms in Interview Questions
How to begin with Competitive Programming?
Step by Step Guide for Placement Preparation
How to prepare for ACM-ICPC?
Insertion Sort, Binary Search, QuickSort, MergeSort, HeapSort
Popular Categories
Common Interview Puzzles
Interview Experiences
Advanced Data Structures
Design Patterns
Dynamic Programming
Greedy Algorithms
Backtracking
Pattern Searching
Divide & Conquer
Geometric Algorithms
Searching
Sorting
Analysis of Algorithms
Mathematical Algorithms
Randomized Algorithms
Recursion
Game Theory
G-Facts
Tags
Advanced Data Structure Amazon Aptitude Aptitude Arrays Bit Magic C C C C++ C++ C/C++ cpp-library
Data Structures Data Structures DBMS Dynamic Programming Experienced GATE-CS-2009 GATE-CS-
2012 GATE-CS-2013 GBlog Graph Hash Internship Interview Experiences Java Java java- Linked Lists
Mathematical Matrix MCQ Microsoft Program Output Puzzles Python QA - Placement Quizzes QA -
Placement Quizzes Searching Sorting STL Strings Technical Scripter Trees
Recent Comments
@geeksforgeeks, Some rights reserved Contact Us! About Us! Advertise with us!
Privacy Policy
