Selectio Sort : Complete anlysis¶

Jirawat kantalo  
Department of Mathenatica and Computer Science

Sorting picture

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