Bubble Sort

1. Core Concept:
Starting from the beginning of an unordered sequence, compare adjacent elements and swap them if needed to place larger (or smaller) values at the end of the sorted portion. This process continues until all elements are properly ordered.

2. Execution Flow
The bubble sort algorithm works as follows:
(1) Compare two adjacent elements. If the first is greater (less) then the second, swap them.
(2) Repeat this for every pair of adjacent elements from the start to the end of the list. After one pass, the largest (smallest) element will have "bubbled" to its correct position.
(3) Apply the same process to the remaining unsorted elements.
(4) Continue reducing the number of comparisons until no swaps are needed, indicating that the array is sorted.

One Pass Example:

Index 0 1 2 3 4     Value 5 3 2 4 1   

Index 0 1 2 3 4     Value 5 3 2 1 4   

Index 0 1 2 3 4     Value 5 3 1 2 4   

Index 0 1 2 3 4     Value 5 1 3 2 4   

Index 0 1 2 3 4     Value 1 5 3 2 4   

3. Implementation (Core Logic)

void BubbleSort(int arr[], int size)
{
  
  
   for(int round = size - 1; round > 0; round--)
       for(int idx = 0; idx < round; idx++)
           if(arr[idx] > arr[idx + 1])
               swap(arr[idx], arr[idx + 1]);
}

public int[] bubbleSort(int[] data, int length) {
  
  
   for (int i = 0; i < length - 1; i++) {
  
  
       for (int j = 0; j < length - i - 1; j++) {
  
  
           if (data[j] > data[j + 1]) {
  
  
               int temp = data[j];
               data[j] = data[j + 1];
               data[j + 1] = temp;
           }
       }
   }
   return data;
}

The number of swaps in bubble sort corresponds to the number of inversions, which indicates disorder in the data.

boolean swapped = true;
int start = 0;
int count = 0;

while(swapped) {
  
  
   swapped = false;
   for(int j = N - 1; j >= start + 1; j--) {
  
  
       if(data[j] < data[j - 1]) {
  
  
           swap(data[j], data[j - 1]);
           count++;
           swapped = true;
       }
   }
   start++;
}

Since bubble sort only exchanges adjacent elements, equal elements maintain their relative order, making it a stable sorting method. However, changing the comparison condition from data[j] > data[j - 1] to data[j] >= data[j - 1] would make it unstable. For an array of size N, the maximum number of comparisons is (N² - N)/2, resulting in a worst-case time complexity of O(N²).

Selection Sort

1. Basic Principle
Compare elements sequential, keeping track of the smallest (largest) element found so far. Once a complete scan is done, swap this element with the first element of the unsorted segment. Continue this process for each subsequent element.
2. Execution Steps
(1) Keep a reference endex for the minimum value in the current unsorted section.
(2) Iterate through the unsorted elements, updating the reference if a smaller element is found.
(3) After scanning, swap the identified minimum element with the first element of the unsorted part.
(4) Repeat for all positions until the entire array is sorted.

Index 0 1 2 3     Value 3H 5S 3D 1S   

Index 0 1 2 3     Value 1S 5S 3D 3H   

Index 0 1 2 3     Value 1S 3D 5S 3H   

Index 0 1 2 3     Value 1S 3D 3H 5S   

3. Implementation (Core Logic)

void selectionSort(int arr[], int size)
{
  
  
   int minIdx, swaps = 0;
   for(int i = 0; i < size - 1; i++) {
  
  
       minIdx = i;
       for(int j = i + 1; j < size; j++)
           if(arr[j] < arr[minIdx])
               minIdx = j;
       if(i != minIdx) {
  
  
           swaps++;
           swap(arr[i], arr[minIdx]);
       }
   }
   return swaps;
}

public static int[] selectionSort(int[] array) {
  
  
   for (int i = 0; i < array.length - 1; ++i) {
  
  
       int minIndex = i;
       for (int j = i + 1; j < array.length; ++j) {
  
  
           if (array[minIndex] > array[j])
               minIndex = j;
       }
       if (minIndex != i) {
  
  
           int temp = array[minIndex];
           array[minIndex] = array[i];
           array[i] = temp;
       }
   }
   return array;
}

Selection sort involves swapping non-adjacent elements, hence it's not stable. It performs approximately (N² - N)/2 comparisons to find the minimum element in each iteration, leading to a time complexity of O(N²).

Stability check and time complexity of O(N⁴)

bool isStable(int input[], int output[], int size)
{
  
  
   for(int i = 0; i < size; i++)
       for(int j = i + 1; j < size; j++)
           for(int a = 0; a < size; a++)
               for(int b = a + 1; b < size; b++)
                   if(input[i] == output[j] && input[i] == output[b] && input[j] == output[a])
                       return false;
   return true;
}

Insertion Sort

1. Fundamental Idea
Each new element is inserted into its correct position within the already sorted portion of the array.