Introduction to Algorithms chap.2

"off in the whiteness" by angela7dreams

Chapter.2 is entitled "Getting Started."

2.1 Insertion sort

I originally had a few knowledge about sort algorithms, like bubble sort, quick sort, merge sort. But this is the first time for me to learn (or write it by myself) insertion sort. Its worst-case running time is n², but its best-case running time is n. So it's faster than other O(n²) algorithms in a particular situation, and also faster than quick sort and merge sort for sufficiently small input data. Don't know insertion sort? It's the same procedure when you sort a hand of cards.

Another important concept in this section is loop invariants, which is used to assert the termination and the correctness of algorithms. There are three types of invariants for you to consider when you evaluate an algorithm:

1. Initialization
2. Maintenance
3. Termination

2.2 Analyzing algorithms

Analyzing algorithms means analyzing the resources required and its computational time. In the book, random-access machine(RAM) is used for analysis of algorithms, where arithmetic, data movement and control take a constant amount of time. As an example, running time of insertion sort is measured, and you analyze the worse-case and the average-case running time of it.

2.3 Designing algorithms

Insertion sort is based on incremental approach. In this section, another approach called divide-and-conquer is introduced. As an example, merge sort is explained. I just implemented merge sort for a Facebook Hacker Cup problem, but the implementation in the book is better than mine. In the function MERGE() sentinels are used, and this yields a concise procedure. (Sentinel is not so much an algorithm-related thing as an implementation skill, though. I just wrote it since I was just moved by its good point.) As in "insertion sort" part, some analysis is done for merge sort.

Exercises and Problems

I'll just introduce an interesting problem.

Let A[1..n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) is called an inversion of A. Give a Θ(n lg n) algorithm to determine the number of inversions in A[]. (Hint: Modify merge sort.)