WOLLO UNIVERSITY

KOMBOLCHA INSTITUTES OF TECHNOLOGY

Data Structures and Algorithms

Tegegn.A
ayalewtegegn2008@gm
[Link]
 Outline
Advanced Sorting Algorithms
 Shell Sort
 Heap Sort
 Quick Sort
 Merge Sort

10/25/2025 2
 Shell Sort
 It is developed by Donald Shell in 1959.
 Shell sort is an improvement of insertion sort.
 It improves on the insertion sort by breaking the original list into a number of smaller sub
lists, each of which is sorted using an insertion sort.
 The unique way that these sub lists are chosen is the key to the shell sort.
 Instead of breaking the list into sub lists of contiguous items, the shell sort uses an
increment i, sometimes called the gap, to create a sub list by choosing all items that are i
items apart.
 It is also sometimes called the diminishing increment sort.

10/25/2025 3
How should the original array be divided into subarrays?
One approach would be to divide the array into a number of subarrays
consisting of contiguous elements (i.e. elements that are next to each other).
For example, the array [abcdef] could be divided into the subarrays [abc]
and [def]. However, shell sort uses a different approach: the subarrays are
constructed by taking elements that are regularly spaced from each other.
 For example, a subarray may consist of every second element in an array,
or every third element, etc.
For example, dividing the array [abcdef] into two subarrays by taking every
second element results in the subarrays [ace] and [bdf]
10/25/2025 4
 …cont’d
Actually, shell sort uses several iterations of this technique.
First, a large number of subarrays, consisting of widely spaced elements,
are sorted.
Then, these subarrays are combined into the overall array, a new division is
made into a smaller number of subarrays and these are sorted.
In the next iteration a still smaller number of subarrays is sorted.
This process continues until eventually only one subarray is sorted, the
original array itself.

10/25/2025 5
10/25/2025 6
 Algorithm
1. Choose gap gk between elements to be partly ordered.
2. Generate a sequence (called increment sequence) gk, gk-1,…., g2, g1 where for
each sequence gi, A[j]<=A[j+gi] for 0<=j<=n-1-gi and k>=i>=1
It is advisable to choose gk =n/2 and gi-1 = gi/2 for k>=i>=1.
After each sequence gk-1 is done and the list is said to be gi-sorted.
Shell sorting is done when the list is 1-sorted (which is sorted using
insertion sort) and A[j]<=A[j+1] for 0<=j<=n-2.
Time complexity is O(n3/2).
10/25/2025 7
 Heap Sort
Heap sort operates by first converting the list in to a heap tree.
Heap tree is a binary tree in which each node has a value greater than both
its children (if any).
It uses a process called "adjust to accomplish its task (building a heap tree)
whenever a value is larger than its parent.
The time complexity of heap sort is O(nlogn).

10/25/2025 8
 Algorithm
1. Construct a binary tree
 The root node corresponds to Data[0].
 If we consider the index associated with a particular node to be i,
 then the left child of this node corresponds to the element with index 2*i+1 and the right child
corresponds to the element with index 2*i+2.
 If any or both of these elements do not exist in the array, then the corresponding child node does
not exist either.

2. Construct the heap tree from initial binary tree using "adjust" process.
3. Sort by swapping the root value with the lowest, right most value and deleting
the lowest, right most value and inserting the deleted value in the array in it
proper position.
10/25/2025 9
 Example
5 8 2 4 1 3 9 7 6 0

10/25/2025 10
 …cont’d
Swap the root node with the lowest, right most node and delete the lowest,
right most value;
insert the deleted value in the array in its proper position;
adjust the heap tree; and
repeat this process until the tree is empty.

10/25/2025 11
10/25/2025 12
10/25/2025 13
10/25/2025 14
 Quick Sort
Quick sort is the fastest known algorithm.
It uses divide and conquer strategy and in the worst case its complexity is O (n 2).
But its expected complexity is O(nlogn).
Algorithm:
1. Choose a pivot value (mostly the first element is taken as the pivot value)
2. Position the pivot element and partition the list so that:
 the left part has items less than or equal to the pivot value
 the right part has items greater than or equal to the pivot value
3. Recursively sort the left part
4. Recursively sort the right part

10/25/2025 15
The following algorithm can be used to position a pivot value and create partition.
Left=0; else
Right=n-1; // n is the total number of elements in Right--;
the list }
else
PivotPos=Left;
{
while(Left<Right)
if(Data[Left]>Data[Right])
{
{
if(PivotPos==Left)
swap(data[Left], Data[Right]);
{
PivotPos=Left;
if(Data[Left]>Data[Right])
Right--;
{
}
swap(data[Left], Data[Right]);
else
PivotPos=Right;
Left++;
Left++;
}
}
}

10/25/2025 16
 Example
Sort the following list using quick sort algorithm.

10/25/2025 17
10/25/2025 18
 Merge Sort
Like quick sort, merge sort uses divide and conquer strategy and its time
complexity is O(nlogn).
Algorithm:
1. Divide the array in to two halves.
2. Recursively sort the first n/2 items.
3. Recursively sort the last n/2 items.
4. Merge sorted items (using an
auxiliary array).

10/25/2025 19
10/25/2025 20
10/25/2025 21
Example: Sort the following list using merge sort algorithm.

10/25/2025 22
 End of Ch.8
Questions, Ambiguities, Doubts,
… ???

10/25/202 23
5