Analysis of Algorithms: Insertion, Selection, and Bubble Sort

This assignment provides a detailed analysis of fundamental sorting algorithms. It covers the algorithms for Insertion Sort, Selection Sort, and Bubble Sort, explaining their steps, best-case, average-case, and worst-case time complexities. The assignment also includes the algorithm for Binary Search. The document breaks down each algorithm's process, from initialization to completion, and offers insights into their efficiency and performance characteristics. This comprehensive guide is designed to help students understand the underlying principles of these sorting techniques and their practical applications in computer science.

Q1. Algorithm for Insertion Sort
Ans.
1. Start from all elements from first to last.
2. Pick the element.
3. If an element is already sorted, move to the next element.
4. Compare with all the elements, in the already sub-sorted list.
5. Shift all the elements from the element which is greater than the current element, one step ahead
and insert this element at that position.
6. Repeat all the steps until all elements are checked.
Best Case: n
Average Case: n2
Worst Case:n2
Q2. Algorithm for Selection Sort
Ans
1. Start from index 0.
2. Take a temporary element min and set its value to the element at the current index.
3. Search the minimum element from this index and swap its value with min.
4.Increment min to next element
5. Repeat all the steps until this list is sorted.
Best Case: n2
Average Case: n2
Worst Case:n2
Q3. Algorithm for Bubble Sort
Ans
1. Set start index as 0
2. From all the elements of the list starting from the current index.
3. If element[index]>element[index-1], swap the elements
4. Continue to the next element
5. Increment the index at repeat till the step is performed for all the indexes
6. Finally, the list is sorted.
Best Case: n
Average Case: n2

Worst Case:n2
Q4 Algorithm for Binary Search
Ans
1. Set start as index 0
2. Set end as the last index
3. set middle as start+end/2
4. Repeat till end > = start
5. if list[middle]==element, print the result and return
6. If list[middle]>element, set start as middle+1 and repeat all steps from step 3.
7. If list[middle]<element, set start as middle-1 and repeat all steps from step 3.
8. If no element is found print error message and return
Best Case:O(1)
Average Case: log2n
Worst Case: log(n)