Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Bubblesort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubbleSort(alist):\n",
    "    for passnum in range(len(alist)-1,0,-1):  # count len-1 down to 1\n",
    "        for i in range(passnum):        # count 0 to passnum-1\n",
    "            if alist[i]>alist[i+1]:\n",
    "                # swap alist[i], alist[i+1]\n",
    "                temp = alist[i]\n",
    "                alist[i] = alist[i+1]\n",
    "                alist[i+1] = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Selection Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selectionSort(alist):\n",
    "    for fillslot in range(len(alist)-1):   # count 0 to len-2\n",
    "        positionOfMin=fillslot\n",
    "        for i in range(fillslot,len(alist)):  # count fillslot to len-1\n",
    "            if alist[i]<alist[positionOfMin]:\n",
    "                positionOfMin = i\n",
    "        # swap alist[fillslot], alist[positionOfMin]\n",
    "        temp = alist[fillslot]\n",
    "        alist[fillslot] = alist[positionOfMin]\n",
    "        alist[positionOfMin] = temp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Merge Sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge(alist, p, q, r):\n",
    "    mergedList = []\n",
    "    left = p\n",
    "    right = q+1\n",
    "    while (left <= q and right <= r):\n",
    "        if alist[left] <= alist[right]:\n",
    "            mergedList.append(alist[left])\n",
    "            left += 1\n",
    "        else:\n",
    "            mergedList.append(alist[right])\n",
    "            right += 1\n",
    "    # Copy any remaining elements of left\n",
    "    while left <= q:\n",
    "        mergedList.append(alist[left])\n",
    "        left += 1\n",
    "    # Copy any remaining elements of right\n",
    "    while right <= r:\n",
    "        mergedList.append(alist[right])\n",
    "        right += 1\n",
    "    # Copy merged list back to alist at index p..r\n",
    "    for i in range(len(mergedList)):\n",
    "        alist[i+p] = mergedList[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def mergeSort(alist, p, r):\n",
    "    if p < r:\n",
    "        q = int((p+r)/2)\n",
    "        mergeSort(alist, p, q)\n",
    "        mergeSort(alist, q+1, r)\n",
    "        merge(alist, p, q, r)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Selection and Quicksort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def partition(alist, p, r):\n",
    "    x = alist[p]   # Choose first element as the partition/pivot\n",
    "    i = p-1\n",
    "    j = r+1\n",
    "    while True:\n",
    "        j = j-1\n",
    "        while alist[j] > x:\n",
    "            j = j-1\n",
    "        i = i + 1\n",
    "        while alist[i] < x:\n",
    "            i = i + 1\n",
    "        if i < j:\n",
    "            # swap alist[i], alist[j]\n",
    "            temp = alist[i]\n",
    "            alist[i] = alist[j]\n",
    "            alist[j] = temp\n",
    "        else:\n",
    "            return j     # Indicates index of the partition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection(alist, p, r, i):\n",
    "    if p==r:\n",
    "        return alist[p]\n",
    "    q = partition(alist, p, r)  # q = index of partition\n",
    "    k = q - p + 1               # k is size of left partition\n",
    "    if i <= k:\n",
    "        return selection(alist, p, q, i)    # recurse on left partition\n",
    "    else:\n",
    "        return selection(alist, q+1, r, i-k)   # recurse on right partition"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def quickSort(alist, p, r):\n",
    "    if p>=r:\n",
    "        return\n",
    "    q = partition(alist, p, r)\n",
    "    quickSort(alist, p, q)\n",
    "    quickSort(alist, q+1, r)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}