Objective of Selection Sort:

The objective of Selection Sort is to sort a given list or array of elements in ascending or descending order by
repeatedly finding the smallest (or largest) element from the unsorted portion and placing it at the beginning
(or end) of the sorted portion.

Properties of Selection Sort:

1. Algorithm Type:
• In-place sorting algorithm, meaning it sorts the list without requiring extra space proportional to
the input size.
• Comparison-based sorting algorithm.
2. Time Complexity:
• Best Case: O(n2)
• Average Case: O(n2)
• Worst Case: O(n2)
3. Space Complexity:
• O(1) (requires a constant amount of extra memory).
4. Stability:
• It is not stable, as equal elements may change their relative order during sorting.
5. Efficiency:
• Inefficient for large datasets due to its quadratic time complexity but can be suitable for small
datasets or when memory usage is a critical constraint.
6. Selection Process:
• In each iteration, the smallest (or largest) element is selected from the unsorted part of the list
and swapped with the first unsorted element.

Objective of Bubble Sort

Bubble Sort is a simple comparison-based sorting algorithm used to arrange a list of elements in ascending
or descending order. The algorithm repeatedly steps through the list, compares adjacent elements, and swaps
them if they are in the wrong order. The process is repeated until the list is sorted.

Properties of Bubble Sort

1. Stability:
Bubble Sort is a stable sorting algorithm, meaning it maintains the relative order of elements with
equal keys.
2. Time Complexity:
• Best case (already sorted list): O(n)
• Average case: O(n2)
• Worst case (reversely sorted list): O(n2)
3. Space Complexity:
Bubble Sort is an in-place algorithm, requiring O(1) additional space for sorting.
4. Adaptive Nature:
Bubble Sort can be optimized to detect if the list is already sorted by using a flag. This makes it
adaptive to some extent.
5. Iterative Nature:
The algorithm uses multiple passes over the list. After each pass, the largest unsorted element is
moved to its correct position.
 6. Simplicity:
Bubble Sort is one of the simplest sorting algorithms, making it suitable for educational purposes and
for sorting small datasets.

Objective of Quick Sort

The objective of the Quick Sort algorithm is to efficiently sort a list or array of elements in ascending or
descending order. It achieves this by employing a divide-and-conquer approach, recursively partitioning the
data around a pivot element and sorting the subarrays independently.

Properties of Quick Sort

1. Divide-and-Conquer Approach
Quick Sort divides the input array into smaller subarrays, sorts them individually, and combines the
results.
2. Pivot Selection
A pivot element is selected to partition the array into two parts:
• Elements smaller than the pivot (left subarray).
• Elements larger than the pivot (right subarray).
3. Time Complexity
• Best Case: O(nlog⁡n)
• Average Case: O(nlog⁡n) (random data).
• Worst Case: O(n2) (unbalanced partitions, e.g., sorted/reverse-sorted data).
4. Space Complexity
Quick Sort is an in-place sorting algorithm with O(log n) auxiliary space due to recursive calls.
5. Stability
Quick Sort is generally not stable (elements with equal keys may not retain their relative order).

Objective of Merge Sort

The primary objective of Merge Sort is to efficiently sort a list or array by employing the divide-and-
conquer approach. It divides the input data into smaller subarrays, sorts them independently, and merges
the sorted subarrays to produce a single sorted array.

Properties of Merge Sort

1. Divide-and-Conquer Approach
• The algorithm recursively splits the array into two halves, sorts them, and merges them back
into a sorted order.

2. Time Complexity
• Best Case: O(n log n)
• Worst Case: O(n log n)
• Average Case: O(n log n)

3. Space Complexity
• Requires O(n) additional memory for temporary arrays used during merging.

4. Stability
• Merge Sort is a stable sorting algorithm, preserving the relative order of elements with equal
keys.
 5. Use Case
• Works well for large datasets and is particularly suitable for linked lists and external sorting (e.g.,
sorting data stored on disk).

6. Recursive and Non-In-Place

• Merge Sort uses recursion and is not in-place, as it requires additional space for merging
operations.

Objective of Heap Sort

The objective of Heap Sort is to sort an array or list of elements efficiently in ascending or descending order
by leveraging the properties of a heap data structure. It repeatedly extracts the maximum (or minimum)
element from a heap and rebuilds the heap until the entire array is sorted.

Properties of Heap Sort

1. Uses a Heap Data Structure

• Heap Sort is based on a binary heap (max-heap for ascending order, min-heap for descending
order), which allows efficient extraction of the largest or smallest element.

2. Time Complexity
• Best Case: O(n log n)
• Average Case: O(n log n)
• Worst Case: O(n log n)
The time complexity is consistent because heap operations like insertion and deletion are O(log
n).

3. Space Complexity
• Heap Sort is an in-place sorting algorithm with O(1) auxiliary space. It requires no additional
storage apart from the input array.

4. Stability
• Heap Sort is not stable because swapping operations during heapification can change the
relative order of equal elements.

5. Iterative Approach
• The algorithm works in two main phases:
1. Heap Construction: Build a max-heap (or min-heap) from the input array.
2. Sorting: Repeatedly swap the root (largest/smallest) with the last unsorted element and
heapify the remaining elements.

Performance and Comparison among all the methods

1. Bubble sort
• Bubble sort is a sorting algorithm that compares two adjacent elements and swaps them until they
are in the intended order.
• Just like the movement of air bubbles in the water that rise up to the surface, each element of the
array move to the end in each iteration. Therefore, it is called a bubble sort.

Working of Bubble Sort

Suppose we are trying to sort the elements in ascending order.

1. First Iteration (Compare and Swap)
1. Starting from the first index, compare the first and the second elements.

2. If the first element is greater than the second element, they are swapped.

3. Now, compare the second and the third elements. Swap them if they are not in order.

4. The above process goes on until the last element.

 Compare the Adjacent Elements

2. Remaining Iteration
The same process goes on for the remaining iterations.

After each iteration, the largest element among the unsorted elements is placed at the end.

Put the largest element at the end

In each iteration, the comparison takes place up to the last unsorted element.
 Compare the adjacent elements

The array is sorted when all the unsorted elements are placed at their correct positions.

The array is sorted if all elements are kept in the right order

Step by step process:

2. Selection sort

Selection sort algorithm

Selection Sort in C is a sorting algorithm that is used to sort a list of elements in either an ascending order or
a descending order.

This algorithm chooses the minimum element from the list of elements and swaps it with the first element
of the list. Similarly, it chooses the second minimum element from the list and swaps it with the second
element of the list. It continues swapping the elements until all the elements of the list are completely sorted
in either direction.

Algorithm of Selection Sort in C

The algorithm of the Selection Sort in C is as follows –

• Make a variable (say min_index) and initialize it to the location 0 of the array.
• Traverse the whole array to find the smallest element in the array.
• While traversing the array, if we find an element that is smaller than min_index then swap both these
elements.
• After which, increase the min_index by 1 so that it points to the next element of the array.
• Repeat the above process until the whole array is sorted.
The whole algorithm has been depicted with the help of a pictorial representation below.
Let us take an example of how the selection sort in c actually works.

• Let's take an array a that has the following elements.

a[] = {4,7,5,3,2,1}

• In the first iteration of the array -

• First of all, set the variable min =0 and then find the smallest element of the array which will
be 1 in this case. Therefore, we will swap 1 with a[min]

Now, the array becomes a[]= {1,7,5,3,2,4}

In the second iteration of the array

• We increment the min by 1 therefore min = 1. Now we will find the smallest element for the rest of
the array which comes out to be 2. Therefore, we will swap 2 with a[min].

Now, the array becomes a[]= {1,2,5,3,7,4}

In the third iteration of the array

• The value of min = 2 and the smallest element in the rest of the array comes out to be 3. Therefore
we will swap 3 with a[min]

Now, the array becomes a[] = {1,2,3,5,7,4}

In the fourth iteration of the array -
• The value of min = 3 and the smallest element in the rest of the array comes out to be 4. Therefore
we will swap 4 with a[min]

Now, the array becomes a[] = {1,2,3,4,7,5}

In the fifth iteration of the array –

• The value of min = 4 and the smallest element in the rest of the array comes out to be 5. Therefore
we will swap 5 with a[min]
Now, the array becomes a[] = {1,2,3,4,5,7}
3. Insertion sort

Insertion sort algorithm

Algorithm:

To achieve insertion sort, follow these steps:

1. We have to start with second element of the array as first element in the array is assumed to be
sorted.
2. Compare second element with the first element and check if the second element is smaller, then
swap them.
3. Move to the third element and compare it with the second element, then the first element and swap
as necessary to put it in the correct position among the first three elements.
4. Continue this process, comparing each element with the ones before it and swapping as needed to
place it in the correct position among the sorted elements.
5. Repeat until the entire array is sorted.

Example