ANALYSIS OF ALGORITHMS



ANALYSIS OF ALGORITHMS

Sorts

a) Insertion Sort

We can represent the list on n integers (or reals) as

A0, A1, A2,(((, An-1

In Insertion Sort, we first sort the first 2 elements, A0, A1 (we will assume that A0 is the smallest element of the list, i.e., A0 = -(), we then compare the third element A2 with A1, and, if A2 is larger o equal to A1, then we stop; otherwise, we swap A2 with A1, and we compare A2 with A0. Since A0 is the smallest possible element, we know that the algorithm will stop.

In general, in the ith iteration the first i elements will be sorted, and Ai will be located (inserted) in the correct position, by comparing it with the elements of the sorted sub-list (from right to left), and every time Ai is smaller than an element of this sub-list, let's say Ar, we swap Ai with Ar , and continue to compare it with the remaining elements. If Ai is larger or equal to an element Ar, we then stop, since the sub list was already sorted and we know that Ai is also larger or equal to Ar, Ar-1, …., A0.

ith iteration:

A0, A1, A2,(((, Ai-1 Ai

Example:

Consider the following list of integers

-( , 4, 1, 3, 2, 5, 6

First iteration:

|- ( | 4

4 is compared with -(, and we stop because 4 is larger o equal to -(.

Second Iteration:

| -(, 4 | 1

1 is compared with 4, and since it is less, we swap it with 4.

-(, 1, 4,

we then compare 1 with (, and we stop.

Third Iteration:

| -(, 1, 4| 3

We compare 3 with 4, and since is less, we swap them

- (, 1, 3, 4

Next we compare 3 with 1, and we stop.

Fourth Iteration:

| -(, 1, 3, 4| 2

We compare 2 with 4, and swap them. Next we compare 2 with 3, and swap them. Finally, we compare 2 with 1, and we stop:

-(, 1, 2, 3, 4

Fifth Iteration:

| -(, 1, 2, 3, 4| 5

5 is compared with 4 and we stop

-(, 1, 2, 3, 4, 5

Sixth Iteration:

|-(, 1, 2, 3, 4, 5| 6

We compare 6 with 5 and stop.

-(, 1, 2, 3, 4, 5, 6

A3: void Insertion (int A[ ], int n) // in reality the elements to be sorted are indexed from

// index 1 to index n

{

int i,j, temp;

A[0]=-32768; //smallest possible integer using 2 bytes integer representation

for (i=1; i ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download