sorting algorithm.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Sorting algorithm\n",
    "### Bubble sort, Insertion sort, Selection sort, Heap sort, Quick sort"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 4, 5, 8]\n"
     ]
    }
   ],
   "source": [
    "def bubbleSort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n):\n",
    "        for j in range(0, n-i-1):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                arr[j], arr[j+1] = arr[j+1], arr[j]\n",
    "\n",
    "arr = [5, 1, 4, 2, 8]\n",
    "bubbleSort(arr)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def insertionsort(list_a):\n",
    "    index_length=range(1,len(list_a))\n",
    "    for i in index_length:\n",
    "        value_to_sort = list_a[i]\n",
    "\n",
    "        while list_a[i-1]>value_to_sort and i>0:\n",
    "            list_a[i], list_a[i-1] = list_a[i-1], list_a[i]\n",
    "            i = i-1\n",
    "    return list_a\n",
    "\n",
    "def selectionsort(list_a):\n",
    "    index_length = range(0, len(list_a)-1)\n",
    "\n",
    "    for i in index_length:\n",
    "        min_value_index = i\n",
    "        \n",
    "        for j in range(i+1, len(list_a)):\n",
    "            if list_a[j] < list_a[min_value_index]:\n",
    "                min_value_index = j\n",
    "        \n",
    "        if min_value_index != i:\n",
    "            list_a[min_value_index], list_a[i] = list_a[i], list_a[min_value_index]\n",
    "    \n",
    "    return list_a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 5, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "def heapify(arr, N, i):\n",
    "    largest = i\n",
    "    l = 2*i+1\n",
    "    r = 2*i+2\n",
    "\n",
    "    if l<N and arr[largest]<arr[l]:\n",
    "        largest=l\n",
    "    \n",
    "    if r<N and arr[largest]<arr[r]:\n",
    "        largest=r\n",
    "    \n",
    "    if largest!=i:\n",
    "        arr[i], arr[largest] = arr[largest], arr[i]\n",
    "        heapify(arr, N, largest)\n",
    "    \n",
    "def heapsort(arr):\n",
    "    N = len(arr)\n",
    "\n",
    "    for i in range(N//2-1, -1, -1):\n",
    "        heapify(arr, N, i)\n",
    "    \n",
    "    for i in range(N-1, 0, -1):\n",
    "        arr[i], arr[0] = arr[0], arr[i]\n",
    "        heapify(arr, i, 0)\n",
    "    \n",
    "    return arr\n",
    "\n",
    "print(heapsort(arr=[2,8,5,3,9,1]))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "def partition(array, low, high):\n",
    "    pivot = array[high]\n",
    "    i = low - 1\n",
    "    for j in range(low, high):\n",
    "        if array[j] <= pivot:\n",
    "            i = i + 1\n",
    "            array[i], array[j] = array[j], array[i]\n",
    "\n",
    "    #start to sort after pivot \n",
    "    array[i + 1], array[high] = array[high], array[i + 1]\n",
    "    return i + 1\n",
    "\n",
    "def quick_sort(array, low, high):\n",
    "    if low < high:\n",
    "        pi = partition(array, low, high)\n",
    "        quick_sort(array, low, pi - 1)\n",
    "        quick_sort(array, pi + 1, high)\n",
    "    return array\n",
    "\n",
    "array = [10, 7, 8, 9, 1, 5]\n",
    "print(quick_sort(array, 0, len(array) - 1))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3.7.13 ('deepcv')",
   "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.13"
  },
  "orig_nbformat": 4,
  "vscode": {
   "interpreter": {
    "hash": "bc8728ca46fe0e46829d869d02c49a317711a0a5ed1f065b44257a00e89bb2e2"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}