# Algorithmic Analysis of Sort Functions

### From charlesreid1

## Analysis of Selection Sort

Consider the following selection sort algorithm:

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]); } }

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.

Overall this algorithm is *quadratic*.

## Analysis of Insertion Sort

Consider the following insertion sort algorithm:

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; } }

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 times, or .

# Flags

AlgorithmsSeries on Algorithms
Algorithms/Sort Three solid O(n log n) search algorithms: Merge Sort Algorithm Analysis/Merge Sort
Algorithms/Search
Algorithms/Combinatorics
Algorithms/Strings
Algorithm complexity Amortization Algorithm Analysis/Matrix Multiplication
Estimation
Project Euler
· Template:AlgorithmsFlag · e |