MIZAN TEPI UNIVERSITY
SCHOOL OF COMPUTING AND INFORMATICS
DEPARTMENT OF COMPUTER SCIENCE
PROGRAM WEEKEND YEAR 3 TERM 1
COURSE TITLE:- DATA STRUCTURES ALGORITHMS
GROUP ONE ASSIGNMENT
Student Name ID No
1. Yohannes Bheru ------------------------------- scie/042/13
2. Ashagera Lewi ------------------------------- scie/ 004/13
3. Mikael Gemechu ------------------------------- scie/023/13
4. Lideya Belachew --------------------- ---------scie/020/13
5. Asefa Ketema ---------------------- --------scie/0 07/13
6. Petros Shiferaw ------------------------------- scie/028 /13
7. Fikadu Shaz ------------------------------- scie/014/13
Jul , 2022 Tepi, Ethiopia
Table of Contents
1. Sorting.....................................................................................................................................................1
1.1 What is Sorting?................................................................................................................................1
1.2 Why is Sorting Necessary?................................................................................................................1
1.3 Classification of Sorting Algorithms.................................................................................................1
1.4.Bubble Sort........................................................................................................................................2
1.5.Implementation..................................................................................................................................3
1.6.Selection Sort....................................................................................................................................4
1.6.2.Algorithm...................................................................................................................................4
1.8.Implementation..................................................................................................................................5
1.9.Insertion Sort.....................................................................................................................................5
1.9.1.Algorithm...................................................................................................................................6
1.9.2.Implementation...........................................................................................................................7
2.Heap sort..................................................................................................................................................8
2.1.Heap Sort Algorithm.........................................................................................................................8
2.3.Detailed Working of Heap Sort.........................................................................................................8
2.4.Implementation of Heap Sort...........................................................................................................11
2.5.Advantages of Heap Sort:................................................................................................................14
I
1. Sorting
1.1 What is Sorting?
Sorting is an algorithm that arranges the elements of a list in a certain order [either ascending or
descending]. The output is a permutation or reordering of the input.
1.2 Why is Sorting Necessary?
Sorting is one of the important categories of algorithms in computer science and a lot of research
has gone into this category. Sorting can significantly reduce the complexity of a problem, and is
often used for database algorithms and searches.
1.3 Classification of Sorting Algorithms
Sorting algorithms are generally categorized based on the following parameters.1
By Number of Comparisons
In this method, sorting algorithms are classified based on the number of comparisons. For
comparison based sorting algorithms, best case behavior is O(nlogn) and worst case behavior is
O(n2). Comparison-based sorting algorithms evaluate the elements of the list by key comparison
operation and need at least O(nlogn) comparisons for most inputs.
Later in this chapter we will discuss a few non – comparison (linear) sorting algorithms like
Counting sort, Bucket sort, Radix sort, etc. Linear Sorting algorithms impose few restrictions on
the inputs to improve the complexity.
By Number of Swaps
In this method, sorting algorithms are categorized by the number of swaps (also called
inversions).
By Memory Usage
Some sorting algorithms are “in place” and they need O(1) or O(logn) memory to create
auxiliary locations for sorting the data temporarily.
By Recursion
1
Sorting algorithms are either recursive [quick sort] or non-recursive [selection sort, and insertion
sort], and there are some algorithms which use both (merge sort).
By Stability
Sorting algorithm is stable if for all indices i and j such that the key A[i] equals key A[j], if
record R[i] precedes record R[j] in the original file, record R[i] precedes record R[j] in the sorted
list. Few sorting algorithms maintain the relative order of elements with equal keys (equivalent
elements retain their relative positions even after sorting).
By Adaptability
With a few sorting algorithms, the complexity changes based on pre-sortedness [quick sort]:
presortedness of the input affects the running time. Algorithms that take this into account are
known to be adaptive.2
Other Classifications
Another method of classifying sorting algorithms is:
• Internal Sort
• External Sort
Internal Sort
Sort algorithms that use main memory exclusively during the sort are called internal sorting
algorithms. This kind of algorithm assumes high-speed random access to all memory.
External Sort
Sorting algorithms that use external memory, such as tape or disk, during the sort come under
thiscategory.
1.4.Bubble Sort
Bubble sort is the simplest sorting algorithm. It works by iterating the input array from the first
element to the last, comparing each pair of elements and swapping them if needed. Bubble sort
continues its iterations until no more swaps are needed. The algorithm gets its name from the
way smaller elements “bubble” to the top of the list. Generally, insertion sort has better
2
performance than bubble sort. Some researchers suggest that we should not teach bubble sort
because of its simplicity and high time complexity.
The only significant advantage that bubble sort has over other implementations is that it can
detect whether the input list is already sorted or not.3
1.5.Implementation3
Algorithm takes O(n2) (even in best case). We can improve it by using one extra flag. No more
swaps indicate the completion of sorting. If the list is already sorted, we can use this flag to skip
the
remaining
passes.
3
his modified version improves the best case of bubble sort to O(n).
Performance
Worst case complexity : O(n2)
Best case complexity (Improved version) : O(n)4
Average case complexity (Basic version) : O(n2)
Worst case space complexity : O(1) auxiliary4
1.6.Selection Sort
Selection sort is an in-place sorting algorithm. Selection sort works well for small files. It is used
for sorting the files with very large values and small keys. This is because selection is made
based on keys and swaps are made only when required.
Advantages
• Easy to implement
• In-place sort (requires no additional storage space)
Disadvantages
• Doesn’t scale well: O(n2)
1.6.2.Algorithm
1. Find the minimum value in the list
2. Swap it with the value in the current position
3. Repeat this process for all the elements until the entire array is sorted
4
This algorithm is called selection sort since it repeatedly selects the smallest element5
1.8.Implementation
Worst case complexity : O(n2)
Best case complexity : O(n2)5
5
Average case complexity : O(n2)6
Worst case space complexity: O(1) auxiliary6
Performance
1.9.Insertion Sort
Insertion sort is a simple and efficient comparison sort. In this algorithm, each iteration removes
an element from the input data and inserts it into the correct position in the list being sorted. The
choice of the element being removed from the input is random and this process is repeated until
all input elements have gone through.
Advantages
• Simple implementation
• Efficient for small data
• Adaptive: If the input list is presorted [may not be completely] then insertions sort
takes O(n + d), where d is the number of inversions
• Practically more efficient than selection and bubble sorts, even though all of them
have O(n2) worst case complexity6
• Stable: Maintains relative order of input data if the keys are same
• In-place: It requires only a constant amount O(1) of additional memory space
• Online: Insertion sort can sort the list as it receives it
1.9.1.Algorithm
Every repetition of insertion sort removes an element from the input data, and inserts it into the
correct position in the already-sorted list until no input elements remain. Sorting is typically done
in-place. The resulting array after k iterations has the property where the first k + 1 entries are
sorted.
6
6
sorted partial result unsorted element
Each element greater than x is copied to
the right as it is compared against x.
1.9.2.Implementation
Example
7
Given an array: 6 8 1 4 5 3 7 2 and the goal is to put them in ascending order.
2.Heap sort
Heap sort is a comparison-based sorting technique based on Binary Heap data structure. It is
similar to the selection sort where we first find the minimum element and place the minimum
element at the beginning. Repeat the same process for the remaining elements.
2.1.Heap Sort Algorithm
To solve the problem follow the below idea:
First convert the array into heap data structure using heapify, then one by one delete the root
node of the Max-heap and replace it with the last node in the heap and then heapify the root of
the heap. Repeat this process until size of heap is greater than 1.
8
Build a heap from the given input
array.
Repeat the following steps until
the heap contains only one element:
Swap the root element of the heap (which is the largest element) with the last element of the
heap.
Remove the last element of the heap (which is now in the correct position).
Heapify the remaining elements of the heap.
The sorted array is obtained by reversing the order of the elements in the input array.
2.3.Detailed Working of Heap Sort
To understand heap sort more clearly, let’s take an unsorted array and try to sort it using heap
sort.
Consider the array: arr[] = {4, 10, 3, 5, 1}.
Build Complete Binary Tree: Build a complete binary tree from the array.
Heap sort algorithm | Build Complete Binary Tree
9
Transform into max heap: After that, the task is to construct a tree from that unsorted array and
try to convert it into max heap.
To transform a heap into a max-heap, the
parent node should always be greater
than or equal to the child nodes
.Here, in this example, as the parent node 4 is
smaller than the child node 10, thus, swap them
to build a max-heap.
Now, 4 as a parent is smaller than the child 5, thus swap both of these again and the
resulted heap and array should be like this:
Heap sort algorithm | Max Heapify constructed binary tree
Perform heap sort: Remove the
maximum element in each step (i.e.,
move it to the end position and remove
that) and then consider the remaining
elements and transform it into a max
heap.
Delete the root element (10) from the max heap. In order to delete this node, try to swap
it with the last node, i.e. (1). After removing the root element, again heapify it to convert
it into max heap.
Resulted heap and array should look like this:
10
Heap sort algorithm | Remove maximum from root and max heapify
Repeat the above steps and it will look like the following:
Heap sort algorithm | Remove next maximum from
root nad max heapify
Now remove the root (i.e. 3) again and
perform heapify.
Heap sort algorithm | Repeat previous
step
Now when the root is removed once again it is sorted. and the sorted array will be like
arr[] = {1, 3, 4, 5, 10}.
11
Heap sort algorithm | Final sorted
array
2.4.Implementation of Heap Sort
// C++ program for implementation of Heap Sort
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i
// which is an index in arr[].
// n is size of heap
void heapify(int arr[], int N, int i)
// Initialize largest as root
int largest = i;
// left = 2*i + 1
int l = 2 * i + 1;
// right = 2*i + 2
int r = 2 * i + 2;
12
// If left child is larger than root
if (l < N && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest
// so far
if (r < N && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i) {
swap(arr[i], arr[largest]);
// Recursively heapify the affected
// sub-tree
heapify(arr, N, largest);
// Main function to do heap sort
void heapSort(int arr[], int N)
// Build heap (rearrange array)
13
for (int i = N / 2 - 1; i >= 0; i--)
heapify(arr, N, i);
// One by one extract an element
// from heap
for (int i = N - 1; i > 0; i--) {
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
// A utility function to print array of size n
void printArray(int arr[], int N)
for (int i = 0; i < N; ++i)
cout << arr[i] << " ";
cout << "\n";
// Driver's code
int main()
int arr[] = { 12, 11, 13, 5, 6, 7 };
14
int N = sizeof(arr) / sizeof(arr[0]);
// Function call
heapSort(arr, N);
cout << "Sorted array is \n";
printArray(arr, N);
Output
Sorted array is
5 6 7 11 12 13
2.5.Advantages of Heap Sort:
Efficiency – The time required to perform Heap sort increases logarithmically while other
algorithms may grow exponentially slower as the number of items to sort increases. This sorting
algorithm is very efficient.
Memory Usage – Memory usage is minimal because apart from what is necessary to hold the
initial list of items to be sorted, it needs no additional memory space to work
Simplicity – It is simpler to understand than other equally efficient sorting algorithms because it
does not use advanced computer science concepts such as recursion.
Disadvantages of Heap Sort:
Costly: Heap sort is costly.
Unstable: Heap sort is unstable. It might rearrange the relative order.
Efficient: Heap Sort is not very efficient when working with highly complex data.
REFERENCES
15
[1].https://www.enjoyalgorithms.com
[2]. Narasimha Karumanchi. Data Structures And Algorithms Made Easy CareerMonk.com16
[3].https://www.tutorialspoint.com/data_structures_algorithms/shell_sort_algorithm.htm
[4].https://www.geeksforgeeks.org/heap-sort/
16
16
