View source for Algorithmic Analysis of Sort Functions

==Analysis of Selection Sort==

Consider the following selection sort algorithm:

<pre>
selection_sort(int s[], int n)
{
    int i, j; // counters
    int min; // index of minimum

    for(i=0; i<n; i++) {
        min = i;
        for(j=i+1; j<n; j++) 
          if(s[j] < s[min]) min = j;
        swap(&s[i], &s[min]);
    }
}
</pre>

performing the algorithmic analysis:
* for loop with i index operates O(n) times
* second for loop operates O(i) times, within the loop that runs n times, for an algorithmic complexity given below.

<math>
O(i) : \sum_{i=1}^{n} i = \dfrac{n(n+1)}{2} \sim O(n^2)
</math>

Overall this algorithm is ''quadratic''.

==Analysis of Insertion Sort==

Consider the following insertion sort algorithm:

<pre>
for(i=1; i<n; i++) { 
    j = i;
    while((j>0)&&(s[j]<s[j-1])) {
        swap(&s[j],&s[j-1]);
        j=j-1;
    }
}
</pre>

This algorithm requires focusing on the worst case scenario. 

The outer for loop runs n times, and is O(n).

The inner for loop has two conditions that must be met. We can assume j>0 always, and focus on when the other condition would be true - when would a random index of S be less than its neighbor? Worst case assumption is, it will always be smaller, and so the while loop will run every single time. This gives us a while loop where j iterates from i to 0.

As before, the outer loop is O(n) and the inner loop is O(i), and therefore runs <math>\frac{n(n+1)}{2}</math> times, or <math>O(n^2)</math>.


[[Category:C]]
[[Category:Java]]
[[Category:CS]]

[[Category:Algorithms]]