Insertion sort

Insertion sort is a simple, intuitive and stable sorting algorithm. Le byte

Insertion sort works much like people sort a poker hand. We start with our left hand empty and the cards on the table face down. Then, we take one card at a time from the table and insert it into the correct position in the left hand. To find the right position for a card, we compare it from right to left with every card we already have in hand, as shown below:

Requirements:

{4,3,2,10,12,1,5,6}

{1,2,3,4,5,6,10,12}

Sorting principle:

1. Divide all elements into two groups, sorted and unsorted;

2. Find the first element in the unsorted group and insert it into the sorted group.

3. Run backwards through the sorted elements and compare them with the elements to be inserted until one element is less than or equal to the element to be inserted

Insert elements in this position, other elements move back one bit;

2. Swap the values at the first index and the minimum index

Insert sort API design:

The name of the class

Insertion

A constructor

Insertion() : Creates Selection objects

Members of the method

1. Public static void sort(Comparable[] a)

2. Private static Boolean greater(Comparable V,Comparable W): Determine whether V is greater than W

Private static void exch(Comparable[] a,int I,int j)

Insert sort code implementation:

// Insert sort

public class Insertion { /*

Sort the elements in array A

* /

public static void sort(Comparable[] a) { for (int i = 1; i < a.length; i++) { for (int j = i; j > 0; J –) {// select * from j-1 where j-1 = 1; // select * from j-1 where j-1 = 1;

if (greater(a[j – 1], a[j])) { exch(a, j – 1, j);

} else { break;

}

}

}

}

/ *

Compares whether the v element is greater than the w element

* /

private static boolean greater(Comparable v, Comparable w) { return v.compareTo(w) > 0;

}

/ *

The array elements I and j swap places

* /

private static void exch(Comparable[] a, int i, int j) { Comparable temp;

temp = a[i];

a[i] = a[j];

a[j] = temp;

}

}

// Test the code

public class InsertionTest { public static void main(String[] args) { Integer[] a = {4, 3, 2, 10, 12, 1, 5, 6};

Insertion.sort(a);

System.out.println(Arrays.toString(a)); / /,2,3,4,5,6,10,12 {1}

}

}

Time complexity analysis of insertion sort

Insert sort uses a double-layer for loop, where the inner loop is the code that actually completes the sort. Therefore, we analyze the time complexity of insert sort, mainly analyzing the number of times the inner loop is executed.

The worst case is {12,10,6,5,4,3,2,1}.

The number of comparisons is :(n-1)+(n-2)+(n-3)+… +2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

The number of switches is :(n-1)+(n-2)+(n-3)+… +2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2;

(n2/2-n /2)+(n2/2-n /2)=N^ 2-n;

According to the big O derivation, the time complexity of the final insertion sort is O(N^2) if the highest order term in the function is reserved. This article turns to music bytes.