BAHIRDAR UNIVERSITY
FACULITY OF COMPUTING
Course: Data Structure and Algorithm
Group Assignment
Title:Shell Sort
submission date :24/08/2017
submited to :Lec. Workie
1
Prepared by:Member of group 3
Introduction
Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. Various
sorting algorithms exist, each with unique strengths.
we will focus on Shell Sort, an optimized version of Insertion Sort introduced by Donald Shell in 1959.
Shell Sort improves efficiency by allowing comparisons between elements that are far apart, leading to
faster sorting of large datasets.
In this presentation, we'll cover how Shell Sort works, its advantages, and its applications in real-world
scenarios
Objective:
Introduce sorting algorithms with a focus on Shell Sort.
Detail the mechanism and process of Shell Sort.
Discuss the benefits and efficiency of Shell Sort compared to other algorithms.
Identify real-world scenarios where Shell Sort is effectively utilized.
2
what is sorting?
• sorting refers to arranging a set of data in some logical order, typically in accending or
decending order .This can involve organizing numbers, strings or othe data types based
on defined criteria.
• the main goal of sorting is to facilitate easier data retriveal and analysis ,making it a
fundamental operation in compter science and data processing.
• There are various sorting algorithms, which can be categorized into simple and
advanced types.
A. simpleSorting Algorithms
• These algorithms are straight forward to implement and understand but may not be
efficient for large datasets. e.g:bubble Sort,selection sort and insertion sort.
B. Advanced Sorting Algorithms
• These algorithms are more complex but generally more efficient for larger datasets.
e.g:merge sort ,quick sort,heap sort and shell sort.
In this presentation, we will focus on Shell Sort, an advanced version of insertion sort.
3
what is shell sort?
the shell sort was introduced to improve the efficiency of simple insertion sort.
Shell Sort is an optimization of the Insertion Sort algorithm that allows the exchange of
elements that are far apart. The basic idea is to arrange the list of elements so that,
starting anywhere, taking every i -th element produces a sorted list. This is done using a
gap sequence that reduces over time until it becomes 1, at which point the algorithm
performs a final insertion sort.
3
Insertion sort Vs shell sort
shell sort
insertion sort
• Builds a sorted array one element at a time. • Generalizes insertion sort by allowing exchanges of
elements that are far apart.
• It works by taking an element from the unsorted
part and inserting it into its correct position in the • It sorts elements at specific intervals (gaps),
sorted part. progressively reducing the gap until it becomes 1
(which effectively becomes insertion sort).
• It compares each new element with the already
sorted elements and shifts larger elements to the • The idea is to move elements closer to their final
right. position sooner.
Key terms
Gap or interval :the spacing between elements or the distance between items being.
swap:exchanging one thing for another.when an element is swapped, move the position
of the swapped items.
sort: the arrangment of data in a prescriped sequence.
sub-list: At each gap size, the algorithm creates sublists by taking elements that are gap
indices apart.The idea is to take each element in the sublist and insert it into its correct
position relative to the other elements in that sublist
Characteristics of Shell Sort
• Time Complexity: ranges from O(n log n) to O(n^2), depending on the gap sequence
used.
Space Complexity: O(1), as it is an in-place sorting algorithm.
:
Cont.…
In Shell Sort, the choice of gap sequence significantly affects the algorithm's performance and time
complexity.
common gap sequence.
Original Sequence
• Start with a gap of n/2 and reduce it by half each time until the gap is 1.
• Sequence: n/2, n/4, n/8, …, 1
• Time Complexity: O(n^2) in the worst case
Knuth's Sequence:
• Formula: hₖ = (3ᵏ - 1)/2 for k = 1, 2, …
• Sequence: 1, 4, 13, 40, 121, ...
• Time Complexity: O(n^(3/2)) in the worst case.
And other sequences, like Hibbard's Sequence and Marcin Ciura’s Sequence
Implimentation of shell sort
steps for shell sort implimentation:
1.count number of elements in a given array:
2. Choose Initial Gap:
Start with a large gap, typically half the length of the array, and reduce it in each iteration.
3 Gap Sorting:
• For each gap, perform a modified insertion sort:
• Iterate through the array from the index of the gap to the end.
• For each element, compare it with elements that are gap indices apart.
4. Element Comparison:
• If the current element is greater than the one at the gap index, swap them.
• Continue comparing and swapping until the correct position for the current element is found.
5. Reduce Gap:
After sorting with the current gap, reduce the gap (e.g., divide by 2) and repeat the process until the
gap is 0.
6. Final Pass: When the gap reaches 1, perform a final pass using standard insertion sort to ensure
complete sorting.
Cont.…
3 9 5 0 23 1 4
Example: sorting of array {3,9,5,0,23,1,4} 0 9 1 3 23 5 4 Gap=3
based on the original shell sequence
gap=7/2=3
the next gap=3/2=1
0 1 9 3 23 5 4
explanation:
for gap=3 0 1 3 9 23 5 4
swap (3, 0) and swap(5,1) Gap=1
in gap=1 0 1 3 5 9 23 4
• swap(9,1) ............... j=1
• there is no swaping ............j=2
• swap(9,3) ........................... j=1 0 1 3 4 5 9 23
• there is no swaping at j=4
• swap(23,5) at this time 5 inserted before 9.
Before increament of ‘j’................. j=5
• swap(23,4) at this time 4 inserted before sorted array
9 and 5.Before increament of ‘j’.......... j=6
C++ shell sort code
//for original shell sequence
void shellsort(int arr[], int n) {
for (int gap = n / 2; gap >= 1; gap = gap / 2) {
for (int j = gap; j < n; j++) {
for (int i = j - gap; i >= 0; i = i - gap) {
if (arr[i + gap] >= arr[i]) {
break;
} else {
swap(arr[i + gap], arr[i]);
}
}
}
}
}
Cont.…
Improved Shell Sort using Knuth's sequence
#include <iostream>
using namespace std;
void shellsort(int arr[], int n) {
int gap = 1;
// Build the initial gap using Knuth's sequence
while (gap < n / 3) {
gap = gap * 3 + 1; // 1, 4, 13, 40, 121, ...
}
while (gap >= 1) {
for (int j = gap; j < n; j++) {
for (int i = j - gap; i >= 0; i = i - gap) {
if (arr[i + gap] >= arr[i]) {
break;
} else {
swap(arr[i + gap], arr[i]);
}
}
}
gap = gap / 3; // Reduce the gap
}
}
Application of shell sort
Sorting Large Datasets:
Efficiently sorts large files or data that may not fit entirely in memory, reducing
comparisons and swaps.
Embedded Systems:
Ideal for resource-constrained environments due to its low memory overhead and
efficiency.
Real-Time Systems:
Suitable for applications requiring fast sorting of data, optimizing performance with
better average case time complexity.
Database Management:
Utilized for ordering query results and organizing records efficiently in databases.
Graphics Image Processing: Used in sorting pixel values or color intensities,
facilitating faster image processing tasks.
Shell Sort is a versatile and efficient algorithm suitable for various applications across
different domains, balancing simplicity and performance
Advantages and Disadvantages of Shell Sort
Advantage
Improved Efficiency Over Insertion Sort:Shell Sort can be significantly faster than simple
insertion sort, especially for larger lists. It reduces the number of inversions and allows elements to
move closer to their final position more quickly
Flexibility with Gap Sequences:Various gap sequences can be used, allowing for
optimization based on the specific characteristics of the data being sorted
Simplicity:The algorithm is relatively easy to understand and implement, especially when
compared to more complex sorting algorithms like Quick Sort
Disadvantage
Unpredictable Time Complexity: The worst-case time complexity can vary significantly
depending on the gap sequence use
Performance on Large Datasets:While Shell Sort performs better than insertion sort, it is
generally not as fast as more advanced algorithms like Quick Sort, Merge Sort, or Heap Sort for
large datasets.
Not Widely Used in Practice: Due to its unpredictable performance and the availability of
more efficient algorithms, Shell Sort is not commonly used in practice for large-scale sorting tasks.
conclusion
In this presentation, we examined the Shell Sort algorithm, which enhances insertion sort by using a gap-based
approach to improve efficiency. By allowing distant elements to be exchanged, Shell Sort reduces the number of
comparisons and movements needed for sorting, especially in larger datasets.
Our exploration highlighted the significance of gap selection in optimizing performance. Overall, Shell Sort serves
as an effective and adaptable sorting method, bridging simplicity and efficiency in various applications.
*
