Research Report

Introduction:
Using a computer to solve a problem involves providing explicit
instructions to guide it through a finite sequence of steps, known as
an algorithm. Algorithms play a crucial role in computer
programming, dictating the process by which a problem is solved
with a finite amount of effort and time.
A sort is a process that rearranges the records of a file into a
sequence that is sorted on some key. Sorting organizes a collection
of data into either ascending or descending order.
Sorting algorithms play a fundamental role in computer science and
data processing, facilitating the efficient arrangement of data
elements in a specific order. Among the numerous sorting
algorithms, Bubble Sort and Insertion Sort hold significance due to
their simplicity and ease of implementation
Bubble Sort, a straightforward comparison-based algorithm,
repeatedly steps through the list, compares adjacent elements, and
swaps them if they are in the wrong order.
On the other hand, Insertion Sort is characterized by building the
sorted array one element at a time, iteratively placing each element
in its proper position. This algorithm's simplicity and adaptability
make it well-suited for small datasets and partially ordered lists.

By delving into the inner workings of Bubble Sort and Insertion Sort,
this research aims to provide valuable insights into their comparative
performances, strengths, and weaknesses. Understanding these
aspects is crucial for informed algorithm selection, particularly in
scenarios where computational resources are a consideration.
Research Background:
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 is quite high.
In Bubble Sort algorithm,
 Traverse from left and compare adjacent elements and the
higher one is placed at right side.
 In this way, the largest element is moved to the rightmost end at
first.
 This process is then continued to find the second largest and
place it and so on until the data is sorted.
Procedure:

Algorithm:
 for i = 1 to length[A] - 1
for j = length[A] down to i + 1
if A[j] < A[j - 1]
exchange A[j] with A[j - 1]

Time Complexity:
The time complexity of the Bubble Sort algorithm varies in different
scenarios:
1. Best Case (Ordered Input):
In the best-case scenario, the input array is already sorted. In this case,
Bubble Sort performs better because it can quickly detect that no
swaps are needed after a single pass through the array. The time
complexity in the best-case scenario is O(n), where "n" is the number
of elements in the array. This is because the algorithm makes a single
pass through the array, checking adjacent elements and making swaps
if necessary.
2. Worst Case (Reversed Input):
In the worst-case scenario, the input array is in reverse order,
requiring the maximum number of comparisons and swaps. The time
complexity in the worst-case scenario is O(n^2), where "n" is the
number of elements. The quadratic time complexity arises from the
nested loops, where each pass through the array involves n
comparisons and swaps.
3. Average Case:
The average-case time complexity of Bubble Sort is also O(n^2). This
is based on the assumption that, on average, half of the elements are
out of order, leading to the same number of comparisons and swaps as
in the worst-case scenario.
Space Complexity:
For Bubble Sort, the algorithm has a space complexity of O(1), which
is considered constant space. This means that the amount of additional
memory used by the algorithm does not grow with the size of the
input data.
The primary reason for Bubble Sort's constant space complexity is
that it doesn't require additional data structures (like extra arrays) to
perform the sorting. The algorithm operates by swapping elements
within the existing array. The only additional space used is for a few
variables, such as loop indices and temporary variables for element
swaps.
Insertion Sort: Insertion sort is a simple sorting algorithm that works
similar to the way of sorting playing cards. The array is virtually split
into a sorted and an unsorted part. Values from the unsorted part are
picked and placed at the correct position in the sorted part.
In Insertion Sort algorithm,
1. Start with the second element (index 1) of the array, assuming
that the first element (index 0) is already sorted.
2. Compare the current element with the elements in the sorted part
of the array, moving from right to left.
 If the current element is smaller than the element being
compared, swap them.
 Continue swapping until the current element is in its
correct sorted position.
3. Move on to the next unsorted element (increment the index) and
repeat steps 2 and 3 until all elements are in their correct
positions.
Procedure:

Algorithm:

while i < length(A)

Time Complexity:
The time complexity of Insertion Sort can be analyzed based on its
behavior in different scenarios:
1. Best Case:
The best-case scenario occurs when the input array is already sorted.
In this case, each element is compared with its preceding elements
until a smaller element is encountered, or until the beginning of the
array is reached. No swaps are needed in the sorted array. The time
complexity in the best case is O(n), where "n" is the number of
elements in the array.
2. Average Case:
In the average case, Insertion Sort generally requires approximately
(n^2)/4 comparisons and (n^2)/4 swaps, where "n" is the number of
elements in the array. The average time complexity is O(n^2). This is
because, on average, each element needs to be compared and swapped
with approximately half of the sorted elements.
3. Worst Case:
The worst-case scenario occurs when the input array is in reverse
order. In this case, each element must be compared and swapped with
every preceding element until it reaches its correct position at the
beginning of the array. The time complexity in the worst case is
O(n^2), as it involves nested loops and a quadratic number of
operations.
Space Complexity:
The space complexity of Insertion Sort is generally considered to be
O(1), indicating that the algorithm uses a constant amount of extra
space regardless of the size of the input data.
Insertion Sort is an in-place sorting algorithm, meaning that it doesn't
require additional data structures or memory proportional to the input
size. The primary memory usage is for a few variables, such as loop
indices and temporary variables for element swaps
Result:
Bubble Sort:
Size Swap Time taken
100 2559 0.0010
200 9052 0.0036
300 21326 0.0079
400 42473 0.0163
500 61950 0.0255
600 89553 0.0365
700 118947 0.0501
800 162877 0.0682
1000 250389 0.1052
5000 6237953 2.78
10000 25108895 12.88

Insertion Sort:
Size Swap Time taken
100 2434 0.0006
200 9591 0.0020
300 22493 0.0053
400 39306 0.0181
500 63722 0.0132
600 87565 0.0198
700 117744 0.0601
800 164025 0.0353
1000 249930 0.0548
5000 6136423 2.76
10000 24755509 5.56
References:
1. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C.
(2009). Introduction to Algorithms (3rd ed.). MIT Press.
2. Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.).
Addison-Wesley.
3. Knuth, D. E. (1997). The Art of Computer Programming,
Volume 1: Fundamental Algorithms (3rd ed.). Addison-Wesley.
4. Bubble Sort
5. Insertion Sort
6. https://medium.com/austins-software-engineering-journey/
insertion-sort-ea0645cc5a23
7. https://en.wikipedia.org/wiki/Insertion_sort