Desparaate Housewives Reruns

DEFINITION

This method involves inserting an element in the array is an orderly and cornices of this vector and again with the remaining elements. because it is usually used by card players is also known by the name of the method of deck.
A if, for example, suppose you have the unordered list.

to insert the element 45, should be inserted between 43 and 65, which requires removing all those numbers right superior value 45, ie, jump on 65 and 84.

The put is based on comparisons and transport thereafter. classification algorithm of a vector X to N elements is made with a tour around the vector and the insertion of an element in the right place. the route is from the second element to the nth.

FEATURES

In the worst cases, the number of comparisons to be performed is
N * (N +1) / 2-1, leaving us with a runtime O (n2).
In the best case (when the list was already sorted), the number of comparisons is N-2.
All them are false, which produces no exchange.
runtime is O (n).

The average case depends on how the elements are initially distributed.
see that the more ordered is initially closest to O (n) and how much messier
, the closer to O (n2).

The worst case is the same as in the bubble and selection methods, but the best case
is linear, which did not occur in these, which to some entries we have
time savings implementation.

Pseudocode

This is the source code, which best explains the method. you're well and all are patient;). Example

c. Void

InsertionSort ( int numbers [], int ARRAY_SIZE) {

int i, j, index;
for (i = 1; i < index =" numbers[i];" j =" i;" style="font-weight: bold;"> while ((j> 0) & & (numbers [j-1]> index)) {
numbers [j] = numbers [j-1];
j = j - 1;
} / / end while
numbers [j] = index ;
} / / end for
} / / End example

Here is a link to an example in speech. C
http://rapidshare.com/files/449013398/barajamio.c


I hope the information presented will serve and it is understood or made a mistake, leave a comment to fix the problem, I am open to mistakes and doubts;)

NOTE: The books have the answer