Heap, Bubble, Quick, Shell

Sort Algorithms
Data Structure
Introduction

• Heap sort is a fundamental sorting algorithm used in data structures.

It efficiently organizes elements into a sorted sequence by using the
properties of a binary heap.
• Understanding the heap sort algorithm is essential for computer
science students and beginners learning data structures, as it
combines the advantages of both selection and tree-based sorting
methods.
• This algorithm is known for its optimal time complexity and in-place
sorting capabilities, making it a crucial tool for handling large data
sets.
 What is Heap Sort?
• Heap sort is a way to sort a list of items, like numbers, in order. It uses a
special tree structure called a heap.
A heap is a kind of binary tree where each parent node is greater than
or equal to its child nodes. This helps in easily finding the largest or
smallest item.
Here’s how it works:
• Build a Heap: First, we arrange the list of numbers into a heap. This
makes sure the largest number is at the top of the heap.
• Remove the Top: Then, we remove the top (the largest number) and
place it at the end of the list.
• Rebuild the Heap: After removing the top, we rebuild the heap with
the remaining numbers.
• Repeat: We keep repeating the process of removing the top and
rebuilding the heap until all numbers are sorted.
• By repeatedly moving the largest number to the end of the list and
restructuring the heap, we end up with a sorted list. Heap sort is
efficient and works well for large lists.
Heap Sort
• Heap sort is a comparison-based sorting technique based on Binary
Heap Data Structure. It can be seen as an optimization over selection
sort where we first find the max (or min) element and swap it with
the last (or first).
• We repeat the same process for the remaining elements. In Heap
Sort, we use Binary Heap so that we can quickly find and move the
max element in O(Log n) instead of O(n) and hence achieve the O(n
Log n) time complexity.
Heap Sort Algorithm

• First convert the array into a max heap using heapify, Please note
that this happens in-place. The array elements are re-arranged to
follow heap properties.
• Then one by one delete the root node of the Max-heap and replace it
with the last node and heapify. Repeat this process while size of heap
is greater than 1.
• Rearrange array elements so that they form a Max Heap.
• Repeat the following steps until the heap contains only one element:
• Swap the root element of the heap (which is the largest element in current
heap) with the last element of the heap.
• Remove the last element of the heap (which is now in the correct position).
We mainly reduce heap size and do not remove element from the actual
array.
• Heapify the remaining elements of the heap.
• Finally we get sorted array.
References
• [Link]
• [Link]
• [Link]
data-structures
• [Link]
explained-time-and-space-complexity
• [Link]
sort/tutorial/
 Runtime Analysis of Algorithms
The performance of an algorithm depends on n i.e. the size of the input or the
number of operations required for each input item.
The algorithms can be classified from the best-to-worst performance (Running
Time Complexity):

• Logarithmic algorithm – O(logn) Runtime grows logarithmically in proportion to n.

• Linear algorithm – O(n) Runtime grows directly in proportion to n.
• Superlinear algorithm – O(nlogn) Runtime grows in proportion to n.
• Polynomial algorithm – O(nc) Runtime grows quicker than previous all based on
n.
• Exponential algorithm – O(cn) Runtime grows even faster than the polynomial
algorithm based on n.
• Factorial algorithm – O(n!) Runtime grows the fastest and becomes quickly
unusable for even small values of n.
 Bubble Sort
• Bubble Sort is the simplest sorting algorithm that works by repeatedly
swapping the adjacent elements if they are in the wrong order.
This algorithm is not suitable for large data sets as its average and
worst-case time complexity are quite high.
• We sort the array using multiple passes. After the first pass, the
maximum element goes to end (its correct position). Same way, after
second pass, the second largest element goes to second last position
and so on.
• In every pass, we process only those elements that have already not
moved to correct position. After k passes, the largest k elements must
have been moved to the last k positions.
• In a pass, we consider remaining elements and compare all adjacent
and swap if larger element is before a smaller element. If we keep
doing this, we get the largest (among the remaining elements) at its
correct position.
Advantages of Bubble Sort:
• Bubble sort is easy to understand and implement.
• It does not require any additional memory space.
• It is a stable sorting algorithm, meaning that elements with the same
key value maintain their relative order in the sorted output.
Disadvantages of Bubble Sort:
• Bubble sort has a time complexity of O(n2) which makes it very slow
for large data sets.
• Bubble sort has almost no or limited real world applications. It is
mostly used in academics to teach different ways of sorting.
Quick Sort
• QuickSort is a sorting algorithm based on the Divide and Conquer that
picks an element as a pivot and partitions the given array around the
picked pivot by placing the pivot in its correct position in the sorted
array.
• It works on the principle of divide and conquer, breaking down the
problem into smaller sub-problems.
What is Quick Sort?

• Quick sort is a method used to arrange a list of items, like numbers, in

order. It works by selecting one item from the list, called the "pivot,"
and then arranging the other items so that all the smaller items come
before the pivot and all the larger items come after it.
• This process is repeated for the smaller groups of items until the
entire list is sorted.
How Does Quick Sort Work?

• Pick a Pivot: Choose one item from the list. It can be any item, but
people often pick the middle item or the first one.
• Divide the List: Compare all the other items to the pivot. Put the
items smaller than the pivot on the left side and the items larger than
the pivot on the right side.
• Repeat: Now, do the same thing with the left side and the right side
separately. Pick new pivots and keep dividing the list until each group
has only one item left.
• Combine: Once all the small groups are sorted, you put them back
together to get the full, sorted list.
Quick Sort Example

• Imagine you have a list of numbers like [8, 3, 7, 1, 9, 2].

• Here’s how quick sort would work:
1. Pick a Pivot: Let’s choose 7 as the pivot.

2. Divide: Compare each number to 7:

• Numbers smaller than 7: [3, 1, 2]
• Numbers larger than 7: [8, 9]
• Now, your list looks like this: [3, 1, 2], [7], [8, 9].
3. Repeat: Sort the smaller groups:
• For [3, 1, 2], pick 3 as the pivot.
Compare:
• Numbers smaller than 3: [1, 2]
• Numbers larger than 3: []
• Now, you have: [1, 2], [3], [7], [8, 9].
4. Combine: Put it all together: [1, 2, 3, 7, 8, 9].
• And that’s your sorted list using quick sort!
• Sorting is a fundamental operation in computer science, and Quick
Sort stands out as one of the most efficient and widely used sorting
algorithms. It follows the divide-and-conquer approach, breaking
down a problem into smaller subproblems and solving them
recursively.
• The algorithm works by selecting a pivot element, partitioning the
array into two halves—one with elements smaller than the pivot and
another with elements greater than the pivot—and then sorting them
independently.
References
[Link]
[Link]
[Link]
Shell sort algorithm
• Sorting is a fundamental operation in computer science, used to
arrange data in a specific order for efficient searching, retrieval, and
processing. One such sorting algorithm is Shell Sort, an optimization
of Insertion Sort that significantly improves performance for larger
datasets.
• Developed by Donald Shell in 1959, this algorithm introduces the
concept of gap-based sorting, which allows elements to move over
larger distances in the initial stages, reducing the total number of
swaps required.
• Shell Sort in data structures introduces the idea of gap-based sorting,
where elements are initially compared and swapped at a certain gap
distance rather than adjacent positions.
• This allows larger elements to move faster toward their correct
position, reducing the number of swaps in later stages.

• As the algorithm progresses, the gap size decreases until it becomes

1, effectively turning into Insertion Sort for the final pass.
Real-Life Analogy For Shell Sort
• Imagine you are arranging books on a messy bookshelf, but instead of
sorting them one by one like Insertion Sort, you decide to use a more
efficient approach:
• Large Gaps First:
• Initially, you pick books that are far apart (let’s say every 5th book) and arrange them
in order.
• This ensures that roughly sorted sections appear quickly, reducing the need for
excessive small adjustments later.
• Smaller Gaps Next:
• Now, you refine the order by arranging books every 2nd position.
• This further organizes the shelf with fewer movements compared to placing each
book one by one from the beginning.
• Final Fine-Tuning:
• Finally, when books are almost in place, you switch to sorting adjacent books,
making small adjustments to achieve the perfectly ordered shelf.
Working Of Shell Sort Algorithm

• Shell Sort works by sorting elements at a certain gap interval and

gradually reducing the gap until it becomes 1. Here’s how it works step by
step:
• Example: Let's sort the array: [12, 34, 54, 2, 3]
• Step 1: Choose An Initial Gap
• A common approach is to start with gap = n/2, where n is the number of
elements.
• Here, n = 5, so the initial gap = 5/2 = 2.
• Step 2: Perform Gap-Based Sorting
• Now, we compare and swap elements at the given gap.
Shell Sort Example

Let’s say you have a list of numbers: [22, 7, 9, 13, 16].

Step 1: Start with a big gap (let’s use a gap of 2)

• Compare 22 and 9: Swap them since 22 is larger.
• Compare 7 and 13: No swap needed.
• Compare 9 and 16: No swap needed.
Now the list looks like this: [9, 7, 22, 13, 16].
• Step 2: Reduce the gap to 1 (now it’s like a simple insertion sort)
• [9, 7, 22, 13, 16].
• Compare 9 and 7: Swap them.
• Compare 7 and 22: No swap needed.
• Compare 22 and 13: Swap them.
• Compare 13 and 16: No swap needed.

• Now the list is fully sorted: [7, 9, 13, 16, 22].

Advantages Of Shell Sort Algorithm
• Some common advantages of shell sort algorithms are:
• Improves Over Insertion Sort: By allowing far-apart elements to move
earlier, Shell Sort reduces the number of shifts required in the final pass.
• Efficient for Moderate-Sized Data: Performs significantly better than
Bubble Sort and Insertion Sort for medium-sized datasets.
• In-Place Sorting Algorithm: Requires no extra space (O(1) space
complexity), making it memory-efficient.
• Adaptive for Nearly Sorted Data: If the array is already partially sorted,
Shell Sort performs very efficiently.
• Flexible Choice of Gap Sequence: Different gap sequences can optimize
performance for specific datasets.
Disadvantages Of Shell Sort Algorithm

• Some common disadvantages of shell sort algorithms are:

• Not Stable: Shell Sort does not maintain the relative order of equal
elements, making it unstable.
• Performance Depends on Gap Sequence: A poorly chosen gap sequence
(e.g., simple division by 2) can lead to O(n²) worst-case complexity.
• Not Optimal for Very Large Datasets: While better than Insertion Sort, it is
still outperformed by Quick Sort, Merge Sort, and Heap Sort for large
datasets.
• Complex to Implement Efficiently: Finding the best gap sequence requires
additional research and tuning for different datasets.
References
• [Link]
• [Link]