WikiGalaxy
Insertion Sort: Overview
Insertion Sort is a simple and intuitive sorting algorithm that builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has the advantage of being easy to understand and implement.
Example 1: Basic Insertion Sort
In this example, we will sort an array of integers using the basic insertion sort algorithm. The algorithm iterates over the array, and at each iteration, it removes one element, finds the location it belongs to in the sorted list, and inserts it there.
public class InsertionSort {
public static void main(String[] args) {
int[] array = {5, 2, 9, 1, 5, 6};
insertionSort(array);
for(int i : array) {
System.out.print(i + " ");
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
}
Console Output:
1 2 5 5 6 9
Example 2: Insertion Sort with Strings
Insertion sort can also be applied to sort strings alphabetically. The algorithm remains the same, but the comparison is done lexicographically.
public class InsertionSortStrings {
public static void main(String[] args) {
String[] array = {"banana", "apple", "orange", "kiwi"};
insertionSort(array);
for(String str : array) {
System.out.print(str + " ");
}
}
public static void insertionSort(String[] array) {
for (int i = 1; i < array.length; i++) {
String key = array[i];
int j = i - 1;
while (j >= 0 && array[j].compareTo(key) > 0) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
}
Console Output:
apple banana kiwi orange
Example 3: Insertion Sort with Custom Comparator
Using a custom comparator, insertion sort can be adapted to sort objects based on specific attributes. This example demonstrates sorting an array of custom objects.
import java.util.Comparator;
class Person {
String name;
int age;
Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
public class InsertionSortCustom {
public static void main(String[] args) {
Person[] people = {new Person("Alice", 34), new Person("Bob", 23), new Person("Charlie", 29)};
insertionSort(people, Comparator.comparingInt(p -> p.age));
for(Person person : people) {
System.out.print(person + " ");
}
}
public static void insertionSort(T[] array, Comparator comparator) {
for (int i = 1; i < array.length; i++) {
T key = array[i];
int j = i - 1;
while (j >= 0 && comparator.compare(array[j], key) > 0) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
}
Console Output:
Bob(23) Charlie(29) Alice(34)
Example 4: Insertion Sort for Doubles
Sorting an array of floating-point numbers is straightforward with insertion sort. This example sorts an array of doubles in ascending order.
public class InsertionSortDoubles {
public static void main(String[] args) {
double[] array = {3.4, 2.2, 5.6, 1.8, 4.5};
insertionSort(array);
for(double d : array) {
System.out.print(d + " ");
}
}
public static void insertionSort(double[] array) {
for (int i = 1; i < array.length; i++) {
double key = array[i];
int j = i - 1;
while (j >= 0 && array[j] > key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
}
Console Output:
1.8 2.2 3.4 4.5 5.6
Example 5: Descending Order Insertion Sort
Insertion sort can easily be modified to sort in descending order by changing the comparison condition. This example demonstrates sorting an array in descending order.
public class InsertionSortDescending {
public static void main(String[] args) {
int[] array = {3, 1, 4, 1, 5, 9};
insertionSort(array);
for(int i : array) {
System.out.print(i + " ");
}
}
public static void insertionSort(int[] array) {
for (int i = 1; i < array.length; i++) {
int key = array[i];
int j = i - 1;
while (j >= 0 && array[j] < key) {
array[j + 1] = array[j];
j = j - 1;
}
array[j + 1] = key;
}
}
}
Console Output:
9 5 4 3 1 1
