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.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- financial analysis of a company
- swot analysis of starbucks
- analysis of data procedure
- analysis of financial statements pdf
- free technical analysis of stocks
- analysis of financial statements ppt
- data analysis of research study
- financial analysis of company
- ratio analysis of financial statements
- analysis of financial performance
- financial analysis of project pdf
- financial analysis of development projects