Aim :

To implement the following sorting algorithms:

• Bubble Sort
• Insertion Sort
• Quick Sort
• Selection Sort

.

Theory

Sorting is the process of arranging elements in a specific order, typically in ascending or descending order. Different sorting algorithms have different time complexities and efficiencies based on their approaches.

1️⃣ Bubble Sort:

Bubble Sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. This process repeats until the list is sorted.

Time Complexity: O(n²) in worst and average cases, O(n) in best case (when already sorted).

2️⃣ Insertion Sort:

Insertion Sort builds the final sorted array one item at a time by taking elements from an unsorted list and inserting them into the correct position in a new sorted portion.

Time Complexity: O(n²) in worst and average cases, O(n) in best case.

3️⃣ Quick Sort:

Quick Sort is a divide-and-conquer algorithm that picks a pivot element, partitions the array around the pivot, and then recursively sorts the left and right partitions.

Time Complexity: O(n log n) on average, O(n²) in worst case (if the pivot is the smallest or largest element).

4️⃣ Selection Sort:

Selection Sort repeatedly finds the minimum element from the unsorted portion and moves it to the beginning.

Time Complexity: O(n²) in all cases.

Algorithm:

Bubble Sort Algorithm:

1. Compare adjacent elements and swap them if they are in the wrong order.
2. Repeat the process until no swaps are required.

Insertion Sort Algorithm:

1. Take one element at a time and insert it into its correct position in the sorted portion.
2. Repeat for all elements.

Quick Sort Algorithm:

1. Choose a pivot element.
2. Partition the array so that elements smaller than the pivot go to one side, and larger elements go to the other.
3. Recursively sort both partitions.

Selection Sort Algorithm:

1. Find the minimum element and place it at the beginning.
2. Repeat for all positions.