1.

Insertion Sort

Insertion sort is a simple sorting algorithm that builds the final sorted array
one element at a time. It works similarly to how you might sort playing cards
in your hands: you pick cards one by one and insert them into the correct
position relative to the already sorted cards.

Algorithm:

1. Start from the second element (index 1) because the first element is
already "sorted."

2. Compare the current element with the element before it.

3. If the current element is smaller than the previous element, swap them.

4. Continue comparing and shifting elements to the right until the current
element is in its correct position.

5. Repeat the process for all elements until the entire array is sorted.

Example:

Let’s consider an array of numbers to sort: [5, 2, 9, 1, 5, 6]

Step 1: Start with the second element (2). Compare with 5 (first element),
and since 2 < 5, shift 5 to the right and place 2 in the first position.

Array after Step 1: [2, 5, 9, 1, 5, 6]

Step 2: Now, consider 9. It is already greater than 5, so no change.

Array after Step 2: [2, 5, 9, 1, 5, 6]

Step 3: Consider 1. It is smaller than 9, 5, and 2, so shift all of them to the

right and place 1 in the first position.

Array after Step 3: [1, 2, 5, 9, 5, 6]

Step 4: Now, consider 5. It is less than 9 but greater than 2, so shift 9 and
place 5 in the third position.

Array after Step 4: [1, 2, 5, 5, 9, 6]

Step 5: Consider 6. It is less than 9, so shift 9 to the right and place 6 in the
fifth position.

Array after Step 5: [1, 2, 5, 5, 6, 9]

Sorted Array: [1, 2, 5, 5, 6, 9]

Time Complexity:

Best case: (if the array is already sorted)

Worst and Average case:

Example

#include <stdio.h>

Void insertionSort(int arr[], int n) {

For (int I = 1; I < n; i++) {

Int key = arr[i];

Int j = I – 1;

While (j >= 0 && arr[j] > key) {

Arr[j + 1] = arr[j];

J = j – 1;

Arr[j + 1] = key;

// Function to print the array

Void printArray(int arr[], int n) {

For (int I = 0; I < n; i++) {

Printf(“%d “, arr[i]);

Printf(“\n”);
}

Int main() {

Int arr[] = {12, 11, 13, 5, 6};

Int n = sizeof(arr) / sizeof(arr[0]);

Printf(“Original array: “);

printArray(arr, n);

insertionSort(arr, n);

printf(“Sorted array: “);

printArray(arr, n);

return 0;

Output

2. Bubble Sort

Bubble sort is another simple sorting algorithm that repeatedly steps through
the list, compares adjacent elements, and swaps them if they are in the
wrong order. The process is repeated until the array is sorted. It gets its
name because smaller elements "bubble" to the top (beginning) of the array.

Algorithm:

1. Start at the beginning of the array.

2. Compare the first two adjacent elements.

3. If the first element is greater than the second, swap them.

4. Move to the next pair of adjacent elements and repeat the process until
you reach the end ofthe array.

5. After each complete pass, the largest element in the unsorted portion will
be placed in its correct position.

6. Repeat the process for the remaining unsorted portion of the array.

7. Continue until no swaps are needed, indicating that the array is sorted.

Example:

Let’s consider an array of numbers: [5, 2, 9, 1, 5, 6]

First Pass

Compare 5 and 2: swap them → [2, 5, 9, 1, 5, 6]

Compare 5 and 9: no swap needed.

Compare 9 and 1: swap them → [2, 5, 1, 9, 5, 6]

Compare 9 and 5: swap them → [2, 5, 1, 5, 9, 6]

Compare 9 and 6: swap them → [2, 5, 1, 5, 6, 9]

After the first pass, 9 is in its correct position

Second Pass:

Compare 2 and 5: no swap needed.

Compare 5 and 1: swap them → [2, 1, 5, 5, 6, 9]

Compare 5 and 5: no swap needed.

Compare 5 and 6: no swap needed.

After the second pass, 6 is in its correct position.

Third Pass:
Compare 2 and 1: swap them → [1, 2, 5, 5, 6, 9]

No further swaps needed

Sorted Array: [1, 2, 5, 5, 6, 9]

Time Complexity:

Best case: (if the array is already sorted)

Worst and Average case:

Comparison of Insertion Sort and Bubble Sort:

Insertion Sort tends to perform better than Bubble Sort in practical cases
because fewer swaps are made. It can be more efficient if the data is already
partially sorted.

Bubble Sort, while conceptually simpler, can be less efficient because it

requires more swaps and is generally slower, especially on large arrays.

Both algorithms are easy to understand but inefficient for large datasets, as
their time complexity grows quadratically.

Example :

Input

#include <stdio.h>

Void bubbleSort(int arr[], int n) {

For (int I = 0; I < n – 1; i++) {

For (int j = 0; j < n – I – 1; j++)

If (arr[j] > arr[j + 1]) {

Int temp = arr[j];

Arr[j] = arr[j + 1];

Arr[j + 1] = temp;

}
}

Void printArray(int arr[], int n) {

For (int I = 0; I < n; i++) {

Printf(“%d “, arr[i]);

Printf(“\n”);

Int main() {

Int arr[] = {64, 34, 25, 12, 22, 11, 90};

Int n = sizeof(arr) / sizeof(arr[0]);

Printf(“Original array: “);

printArray(arr, n);

bubbleSort(arr, n);

printf(“Sorted array: “);

printArray(arr, n);

return 0;

Out put