Selection, Insertion, and Bubble Sort

What is selection sort?

A selection sort sorts an array of elements by repeatedly finding the minimum element from the unsorted part of the array and placing it at the beginning of the sorted part of the array.

The algorithm works by iterating through the unsorted part of the array and keeping track of the minimum element found so far. Once the end of the unsorted part of the array is reached, the minimum element is swapped with the first element of the unsorted part of the array. This process is repeated until the entire array is sorted.

The implementation is as follows:

public static void selectionSort(int[] arr) {
	for (int i = 0; i ⋖ arr.length - 1; i++) {
		int minIndex = i;
		for (int j = i + 1; j ⋖ arr.length; j++) {
			if (arr[j] ⋖ arr[minIndex]) {
				minIndex = j;
			}
		}
		int temp = arr[i];
		arr[i] = arr[minIndex];
		arr[minIndex] = temp;
	}
}

What is insertion sort?

Insertion sort is a simple sorting algorithm that sorts an array of elements by iteratively inserting each element into its proper position in a sorted subarray.

The algorithm works by dividing the input array into two parts: a sorted subarray and an unsorted subarray. Initially, the sorted subarray contains only the first element of the input array, and the unsorted subarray contains the remaining elements. The algorithm then iterates through the unsorted subarray, removing one element at a time and inserting it into its proper position in the sorted subarray, shifting any larger elements to the right as necessary. This process is repeated until the entire input array is sorted.

The implementation is as follows:

public static void insertionSort(int[] arr) {
	for (int i = 1; i ⋖ arr.length; i++) {
		int key = arr[i];
		int j = i - 1;
		while (j ⋗= 0 && arr[j] ⋗ key) {
			arr[j + 1] = arr[j];
			j--;
		}
		arr[j + 1] = key;
	}
}

What is bubble sort?

Bubble sort is a simple sorting algorithm that repeatedly swaps adjacent elements in an array until the array is sorted.

The algorithm works by iterating through the array, comparing adjacent pairs of elements and swapping them if they are in the wrong order. This process is repeated until the entire array is sorted. Bubble sort gets its name from the way smaller elements "bubble" to the top of the array during each iteration.

The implementation is as follows:

public static void bubbleSort(int[] arr) {
	int n = arr.length;
	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;
			}
		}
	}
}

‍