Selectio Sort : Complete anlysis

Jirawat kantalo  
Department of Mathenatica and Computer Science

Background

Problem specification

A user must define the problem using the standard form. The statement is the 'Precondition' which specifies the input of the problem.The second statement is the 'postcondition' which specifies conditions for the output.

The sorting problem is
Precondition: $A$ is the list of $n$ munber.
Postcondition:$A$ having the following condition.
$$A[0] \leq A[1] \leq ... \leq A[n-1]$$

Asymptotic Analysis

Given positive function $f$ and $g$ , we state that $f(n)$ if and only if
$$\exists c > 0 \exists n_0 \in \mathbb{N} \forall n \geq n_0, f(n) < c g(n)$$
Given positive function $f$ and $g$ , we state that $\Theta(g(n))$ if and only if
$$\exists c_1,c_2 > 0 \exists n_0 \in \mathbb{N} \forall n \geq n_0, c_1g(n)

Selection Sort

Pseudocode for the selection sort from http://www.sorting-algorithms.com

1.  for i = 1:n,
2.  k = i
3.  for j = i+1:n, if a[j] < a[k], k = j
4.  → invariant: a[k] smallest of a[i..n]
5.  swap a[i,k]
6.  → invariant: a[1..i] in final position
7.end

Analysis

Let $T_{worst}(n)$ be the worst - case running time for the Selecting sort.
Line2., we need 1 operation for assigning k = i Line 5 ., we need 1 operation for swapping a[i,k]
Line3.-5 need i+1, i+2, ... n steps. We conclude that we perform n-i operations. Line1.-7 we count

$$\sum_{i=1}^{n} (n - i) + \sum_{i=1}^{n} 1= \sum_{i=1}^{n}n - \sum_{i=1}^{n} i+n=n^2 - \frac{n(n+1)}{2} +n= \frac{n^2}{2} + \frac{n}{2} $$

Hence , $T_{worst}(n)$ = $\Theta(n^2)$

Let $T_{best}(n)$ be the best - case running time for the Selecting sort.
Line 5 ., we need 1 operation for swapping a[i,k]
Line3.-5 need i+1, i+2, ... n steps. We conclude that we perform n-i operations. Line1.-7 we count

$$\sum_{i=1}^{n} (n - i) + \sum_{i=1}^{n}1= \sum_{i=1}^{n}n - \sum_{i=1}^{n} i+n =n^2 - \frac{n(n+1)}{2}+n = \frac{n^2}{2} + \frac{n}{2} $$

Hence , $T_{best}(n)$ = $\Theta(n^2)$

Experimental results

We perform our selection sort algorithm on 50 example. Each example is simulated using varous seed with equal size 10.

import random