{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Sorting Algorithms"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The problem of sorting is an ideal problem to introduce many concepts of fundamental algorithm design. Some good reasons to study sorting are:\n",
"\n",
"* sorting is used by many applications,\n",
"\n",
"* sorting is the (first) step of many algorithms,\n",
"\n",
"* many techniques can be illustrated by studying sorting.\n",
"\n",
"For us the last reason is most important. In particular, sorting allows us to study the algorithmic techniques that we have seen for the searching problem on a more complex algorithmic problem. In the following I give an overview of the sorting algorithms discussed in the course. Before I do so, let me define the swap routine that is used by many of the sorting algorithms."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": true
},
"outputs": [],
"source": [
"def swap(A, i, j):\n",
" A[i], A[j] = A[j], A[i]"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 1. Selection Sort"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Selection sort is possibly the conceptually simplest sorting algorithm. It finds the smallest element and places it on the first position. Then it finds the second smallest and places it at the second position, and so on."
]
},
{
"cell_type": "code",
"execution_count": 9,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 5, 6, 8]\n"
]
}
],
"source": [
"def selection_sort(A):\n",
" n = len(A)\n",
" for i in range(n):\n",
" smallest = i\n",
" for j in range(i+1 , n):\n",
" if A[j] < A[smallest]: smallest = j\n",
" swap(A, smallest, i )\n",
" \n",
"A = [5,2,8,6]\n",
"selection_sort(A)\n",
"print(A)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"The correctness of selection\\_sort can be shown by first analyzing the inner loop (lines 5-6) and then the outer loop (lines 3-7). For both steps a loop invariant proof can be used. The running time of th inner loop is $O(n-i)$. The overall running time is therefore \n",
"$$\n",
"O(1) + \\sum_{i=0}^{n-1} O(n-i) = O(n^2)\\;.\n",
"$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 2. Insertion Sort"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Insertion sort is an *incremental algorithm*. That means that it incrementally computes the solution for an increasing subset of the input. Specifically it sorts the subarray $A[0..i-1]$ for increasing $i$. While Insertion Sort is slow asymptotically, it is fast for small input."
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 5, 6, 8]\n"
]
}
],
"source": [
"def insertion_sort(A):\n",
" n = len(A)\n",
" # at the beginning of the j-th iteration the subarray A[0..j-1] is sorted\n",
" for j in range(1,n):\n",
" key = A[j]\n",
" i = j -1\n",
" while i >= 0 and A[i] > key:\n",
" A[i+1] = A[i]\n",
" i = i -1\n",
" A[i+1] = key\n",
" \n",
"A = [5,2,8,6]\n",
"insertion_sort(A)\n",
"print(A)"
]
},
{
"cell_type": "markdown",
"metadata": {
"collapsed": true
},
"source": [
"Also for insertion\\_sort the correctness can be shown by first analyzing the inner loop (lines 7-9) and then the outer loop (lines 4-10). For both steps a loop invariant proof can be used. \n",
"The running time of th inner loop is $O(j)$. (Note that it is better in the best case.) The overall running time is therefore $$O(1) + \\sum_{j=1}^{n-1} O(j) = O(n^2)\\;.$$"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"## 3. Merge Sort"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"Merge Sort is an example of a recursive *divide&conquer* algorithm. A divide&conquer algorithm divides the problem into smaller subproblems, solves the subproblems recursively, and then combines the solutions to the subproblems. "
]
},
{
"cell_type": "code",
"execution_count": 4,
"metadata": {
"collapsed": false
},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"[2, 5, 6, 8]\n"
]
}
],
"source": [
"def merge_sort(A):\n",
" n = len(A)\n",
" if n>1:\n",
" mid = n//2\n",
" A1 = A[:mid]\n",
" A2 = A[mid:]\n",
" # recursive calls:\n",
" merge_sort(A1)\n",
" merge_sort(A2)\n",
" # merge solutions\n",
" i=0\n",
" j=0\n",
" while i