Review Algorithms And Data Structure -- Insertion-Sort

文章目錄

• • • • Insertion-Sort
      • • Pseudocode
        • C++
        • More about Insertion-Sort
        • • Loop invariants and the correctness of insertion sort
        • Conclusion

Insertion-Sort

Know about it by writing CODE.

Because it’s really easy!!!

Pseudocode

for j = 2 to A.length
	key = A[j]
	// Insert A[j] into the sorted sequence A[1...j-1]
	i = j - 1
	while i > 0 and A[i] > key
		A[i+1] = A[i]
		i = i - 1
	A[i + 1] = key
           

C++

#include <iostream>

using namespace std;

void insert_sort(int *p, int length);

void insert_sort(int *p, int length)
{
	int key = 0;
	for (int i = 1; i < length; ++i)
	{
		key = p[i];
		int j = i - 1;
		while (j >= 0 && p[j] > key)
		{
			p[j + 1] = p[j];
			j = j - 1;
		}
		p[j + 1] = key;
	}
}

int main()
{
	int a[] = {15, 1, 51, 6, 13};
	cout << "before sorted!" << endl;
	for (int i = 0; i < 5; ++i)
	{
		cout << a[i] << endl;
	}
	insert_sort(a, 5);
	cout << "after sorted!" << endl;
	for (int i = 0; i < 5; ++i)
	{
		cout << a[i] << endl;
	}
	return 0;
}
           

More about Insertion-Sort

Loop invariants and the correctness of insertion sort

At the start of each iteration of the for loop, the subarray A[i…j-1] consists of the elements originally in A[1…j-1], but in sorted order.

We use loop invariants to help us understand why an algorithms is correct.

We must show three things about a loop invariants.

1. Initalization: It is true prior to the first iteration of the loop.
2. Maintenance: If it is true before an iteration of the loop, it remains true before the next iteration.
3. Termination: When the loop terminates, the invariant gives us a useful property that helps show that the algorithm is correct.

Now Let’s talk about Insertion-Sort:

1. Initalization: Before the first loop, we got the A[1]. Moreover, this subarray is sorted, which shows that the loop invariant holds prior to the first iteration of the loop.
2. Maintenance: here, we should talk about the second property: showing that each iteration maintains the loop invariant. That’s pretty easy. If you got A[1…2], and you must know the subarray consists of the elements originally in A[1…2], and it gets sorted. Moreover, you can know about A[1…3], A[1…4] and so on. So it’s true before an iteration of the loop, it remains true before the next iteration. It’s Maintenance.
3. Termination: We already know that the subarray is sorted, so when we finished the loop, we got a subarray has already been sorted. You know even A[0…A.length] is a subarray of A.

So that, we can know the algorithms is correct by check the loop invariants. It’s a bit like mathematical induction. But we stop the “induction” when loop terminates.

Conclusion

Nothing!!! But next time we’ll analyze the cost of Insertion-Sort.