Algorithmic Heights. Sorting.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 32,
   "id": "d17a5fd8-063c-46ec-9619-752a776ed42b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "\n",
    "from numba import njit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 334,
   "id": "ddc34134-b927-4a41-a617-ce5817dd047a",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'50295\\n'"
      ]
     },
     "execution_count": 334,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "with open('/home/hamit/Downloads/rosalind_med.txt', 'r') as ros:\n",
    "    data = ros.readlines()\n",
    "\n",
    "arr = [int(x) for x in data[1].split()]\n",
    "# b = [int(x) for x in data[3].split()]\n",
    "\n",
    "data[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 184,
   "id": "d958e7cc-bd86-45be-bb1e-160587975cf2",
   "metadata": {},
   "outputs": [],
   "source": [
    "with open('/home/hamit/Downloads/res.txt', 'w') as res:\n",
    "    res.write(' '.join([str(i) for i in arr]))\n",
    "\n",
    "# merge_sort(a, b)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "id": "d7694bcd-e48e-4bbd-b15c-e47cfb3a3ec2",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sorted_arrays(a, b):    # a and b are sorted arrays\n",
    "    n, m = len(a), len(b)\n",
    "    i, j = 0, 0\n",
    "    c = []\n",
    "    while i < n and j < m:\n",
    "        if a[i] <= b[j]:\n",
    "            c.append(a[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            c.append(b[j])\n",
    "            j += 1\n",
    "            \n",
    "    if i < n:\n",
    "        c.extend(a[i:])\n",
    "    else:\n",
    "        c.extend(b[j:])\n",
    "        \n",
    "    return c"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "id": "18f5b583-4f98-4b9c-96b5-b4c18eee9306",
   "metadata": {},
   "outputs": [],
   "source": [
    "def merge_sort(arr):\n",
    "    n = len(arr)\n",
    "    if n > 1:\n",
    "        middle = n // 2\n",
    "        return merge_sorted_arrays(\n",
    "            merge_sort(arr[:middle]), \n",
    "            merge_sort(arr[middle:])\n",
    "        )\n",
    "    return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "id": "8bd5ab02-4718-4435-b715-d52ade887302",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "(9, 10)"
      ]
     },
     "execution_count": 63,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "get_children(4)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "id": "9dd7a9c1-aa3a-407b-9317-169e5b76e342",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Building a Heap\n",
    "\n",
    "def check_heap(heap):\n",
    "    for i in range(1, len(heap)):\n",
    "        # print(heap[i], heap[get_parent(i)])\n",
    "        if heap[i] > heap[get_parent(i)]:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "def get_parent(i):\n",
    "    return (i - 1) // 2\n",
    "\n",
    "def get_children(i):\n",
    "    return i*2 + 1, i*2 + 2\n",
    "\n",
    "def bubble_up(heap, n):\n",
    "    i = n\n",
    "    while i and heap[get_parent(i)] < heap[i]:\n",
    "        j = get_parent(i)\n",
    "        heap[j], heap[i] = heap[i], heap[j]\n",
    "        i = j\n",
    "        \n",
    "def sift_down(heap, i):\n",
    "    heap_len = len(heap)\n",
    "    c1, c2 = get_children(i)\n",
    "    while (c1 < heap_len and c2 < heap_len) and (heap[i] < heap[c1] or heap[i] < heap[c2]):\n",
    "        j = c1 if heap[c1] >= heap[c2] else c2\n",
    "        # print(i)\n",
    "        heap[j], heap[i] = heap[i], heap[j]\n",
    "        i = j\n",
    "        c1, c2 = get_children(i)\n",
    "        \n",
    "    if c2 == heap_len and heap[i] < heap[c1]:\n",
    "        heap[c1], heap[i] = heap[i], heap[c1]\n",
    "        # print(i)\n",
    "        \n",
    "heap = arr.copy()\n",
    "\n",
    "# arr = [1, 3, 5, 7, 2]\n",
    "for i in range(len(heap) // 2)[::-1]:\n",
    "    sift_down(heap, i)\n",
    "    \n",
    "check_heap(heap)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 119,
   "id": "411199cf-643b-4b2c-ad01-e0b1fe56d439",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1700052466"
      ]
     },
     "execution_count": 119,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Counting Inversions\n",
    "\n",
    "# arr = [1, 3, 5, 7, 2]\n",
    "inv = 0\n",
    "\n",
    "def merge_sorted_arrays(a, b):    # a and b are sorted arrays\n",
    "    global inv\n",
    "    n, m = len(a), len(b)\n",
    "    i, j = 0, 0\n",
    "    c = []\n",
    "    while i < n and j < m:\n",
    "        if a[i] <= b[j]:\n",
    "            c.append(a[i])\n",
    "            i += 1\n",
    "        else:\n",
    "            inv += n - i\n",
    "            c.append(b[j])\n",
    "            j += 1\n",
    "            \n",
    "    if i < n:\n",
    "        c.extend(a[i:])\n",
    "    else:\n",
    "        c.extend(b[j:])\n",
    "        inv += n - i\n",
    "        \n",
    "    return c\n",
    "\n",
    "def merge_sort(arr):\n",
    "    # global inv\n",
    "    n = len(arr)\n",
    "    if n > 1:\n",
    "        middle = n // 2\n",
    "        return merge_sorted_arrays(\n",
    "            merge_sort(arr[:middle]), \n",
    "            merge_sort(arr[middle:])\n",
    "        )\n",
    "    return arr\n",
    "\n",
    "merge_sort(arr)\n",
    "inv"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 201,
   "id": "f955a7b4-af5c-4d8e-a25f-c34e4c74adfb",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 4, 1, 2, 4, 5, 5, 7, 6]"
      ]
     },
     "execution_count": 201,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# 2-Way Partition\n",
    "\n",
    "s = '4 5 6 4 1 2 5 7 4'\n",
    "arr = list(map(int, s.split()))\n",
    "# arr = [int(x) for x in data[1].split()]\n",
    "\n",
    "def check_part(part, x):\n",
    "    a = part < x\n",
    "    if (a[1:] ^ a[:-1]).sum() == 1:\n",
    "        return True\n",
    "    return False\n",
    "\n",
    "def two_way_part(arr):\n",
    "    part = arr.copy()\n",
    "    \n",
    "    def swap(i, j):\n",
    "        part[i], part[j] = part[j], part[i]\n",
    "        \n",
    "    x = part[0]\n",
    "    bottom_edge = 1\n",
    "    for i in range(1, len(arr)):\n",
    "        # print(part, bottom_edge, i)\n",
    "        if part[i] <= x:\n",
    "            swap(bottom_edge, i)\n",
    "            bottom_edge += 1\n",
    "    swap(0, bottom_edge-1)\n",
    "    return part\n",
    "            \n",
    "part = two_way_part(arr)\n",
    "part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 217,
   "id": "0dd3aac0-51ba-4d6b-ad28-8633e1fab8f6",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 3-Way Partition\n",
    "\n",
    "# s = '4 5 6 4 1 2 5 7 4'\n",
    "# arr = list(map(int, s.split()))\n",
    "arr = [int(x) for x in data[1].split()]\n",
    "\n",
    "def three_way_part(part):\n",
    "    # part = arr.copy()\n",
    "    \n",
    "    def swap(i, j):\n",
    "        part[i], part[j] = part[j], part[i]\n",
    "        \n",
    "    x = part[0]\n",
    "    bottom_edge_eq = 1\n",
    "    bottom_edge_gt = 1\n",
    "    for i in range(1, len(part)):\n",
    "        # print(part)\n",
    "        if part[i] == x:\n",
    "            swap(bottom_edge_gt, i)\n",
    "            bottom_edge_gt += 1\n",
    "        elif part[i] < x:\n",
    "            swap(bottom_edge_gt, i)\n",
    "            swap(bottom_edge_eq, bottom_edge_gt)\n",
    "            bottom_edge_gt += 1\n",
    "            bottom_edge_eq += 1\n",
    "            \n",
    "    swap(0, bottom_edge_eq-1)\n",
    "    return part\n",
    "            \n",
    "part = three_way_part(arr)\n",
    "# part"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 330,
   "id": "2056bb7b-a8d4-43e5-8526-240314a995cf",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Median\n",
    "\n",
    "from random import choice, randint\n",
    "\n",
    "def three_way_part(part, i):\n",
    "    # part = arr.copy()\n",
    "    \n",
    "    def swap(i, j):\n",
    "        part[i], part[j] = part[j], part[i]\n",
    "        \n",
    "    x = part[i]\n",
    "    swap(0, i)\n",
    "    bottom_edge_eq = 1\n",
    "    bottom_edge_gt = 1\n",
    "    for i in range(1, len(part)):\n",
    "        # print(part)\n",
    "        if part[i] == x:\n",
    "            swap(bottom_edge_gt, i)\n",
    "            bottom_edge_gt += 1\n",
    "        elif part[i] < x:\n",
    "            swap(bottom_edge_gt, i)\n",
    "            swap(bottom_edge_eq, bottom_edge_gt)\n",
    "            bottom_edge_gt += 1\n",
    "            bottom_edge_eq += 1\n",
    "            \n",
    "    swap(0, bottom_edge_eq-1)\n",
    "    return part[:bottom_edge_eq-1], part[bottom_edge_eq-1:bottom_edge_gt], part[bottom_edge_gt:]\n",
    "\n",
    "def kth_ordinal_statistics(arr, k):\n",
    "    i = randint(0, len(arr)-1)\n",
    "    # print(arr[i])\n",
    "    l, m, r = three_way_part(arr, i)\n",
    "    # print(l, m, r, k)\n",
    "    l_n, m_n, r_n = map(len, (l, m, r))\n",
    "    if k < l_n:\n",
    "        return kth_ordinal_statistics(l, k)\n",
    "    elif  k < l_n + m_n:\n",
    "        return m[0]\n",
    "    else:\n",
    "        return kth_ordinal_statistics(r, k - l_n - m_n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 152,
   "id": "c2f53863-0b67-4d29-ad4b-83c8fd867e47",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "-1\n",
      "705 1326 8457\n",
      "-1\n",
      "1566 6106 8492\n",
      "-1\n",
      "164 3507 5457\n",
      "-1\n",
      "5194 7571 8374\n",
      "719 1903 3393\n",
      "-1\n",
      "62 1336 7066\n",
      "4207 5208 7207\n",
      "563 2458 3277\n",
      "7057 8289 8432\n"
     ]
    }
   ],
   "source": [
    "# 3SUM\n",
    "\n",
    "@njit\n",
    "def sum3(arr):\n",
    "    arr = arr.copy()\n",
    "    arr.sort()\n",
    "    n = arr.size\n",
    "    for i in range(n):\n",
    "        for j in range(i+1, n):\n",
    "            ij_sum = arr[i] + arr[j]\n",
    "            k = np.searchsorted(arr[j+1:], -ij_sum) + j+1\n",
    "            if k < n and arr[k] == -ij_sum:\n",
    "                return [i, j, k]\n",
    "    return [-1, -1, -1]\n",
    "\n",
    "with open('/home/hamit/Downloads/rosalind_3sum (4).txt', 'r') as ros:\n",
    "    data = ros.readlines()\n",
    "\n",
    "k, N = [int(x) for x in data[0].split()]\n",
    "for i in range(k):\n",
    "    arr = np.array([int(x) for x in data[i+1].split()])\n",
    "    args = arr.argsort()\n",
    "    ind = sum3(arr)\n",
    "    if ind[0] == -1:\n",
    "        print(-1)\n",
    "        # sum3_old(arr, N)\n",
    "    else:\n",
    "        real_ind = sorted(args[ind])\n",
    "        for i in range(3):\n",
    "            real_ind[i] += 1\n",
    "        print(*real_ind) #, arr[real_ind], arr[real_ind].sum())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 156,
   "id": "69c12f63-0f85-435b-80e4-b89a864fe6c3",
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "array([-99995, -99995, -99986, ...,  99996, 100000, 100000])"
      ]
     },
     "execution_count": 156,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Heap Sort\n",
    "\n",
    "def get_parent(i):\n",
    "    return (i - 1) // 2\n",
    "\n",
    "def get_children(i):\n",
    "    return i*2 + 1, i*2 + 2\n",
    "\n",
    "def bubble_up(heap, n):\n",
    "    i = n\n",
    "    while i and heap[get_parent(i)] < heap[i]:\n",
    "        j = get_parent(i)\n",
    "        heap[j], heap[i] = heap[i], heap[j]\n",
    "        i = j\n",
    "        \n",
    "def sift_down(heap, i, n):\n",
    "    c1, c2 = get_children(i)\n",
    "    while (c1 < n and c2 < n) and (heap[i] < heap[c1] or heap[i] < heap[c2]):\n",
    "        j = c1 if heap[c1] >= heap[c2] else c2\n",
    "        heap[j], heap[i] = heap[i], heap[j]\n",
    "        i = j\n",
    "        c1, c2 = get_children(i)\n",
    "        \n",
    "    if c2 == n and heap[i] < heap[c1]:\n",
    "        heap[c1], heap[i] = heap[i], heap[c1]\n",
    "\n",
    "with open('/home/hamit/Downloads/rosalind_hs.txt', 'r') as ros:\n",
    "    data = ros.readlines()\n",
    "arr = np.array([int(x) for x in data[1].split()])\n",
    "        \n",
    "n = len(arr)\n",
    "for i in range(n//2)[::-1]:\n",
    "    sift_down(arr, i, n)\n",
    "    \n",
    "for i in range(n):\n",
    "    arr[0], arr[n-1-i] = arr[n-1-i], arr[0]\n",
    "    sift_down(arr, 0, n-1-i)\n",
    "    \n",
    "arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 164,
   "id": "be07840c-ae49-451d-9157-92cc7752adc4",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Partial Sort\n",
    "\n",
    "with open('/home/hamit/Downloads/rosalind_ps.txt', 'r') as ros:\n",
    "    data = ros.readlines()\n",
    "k = int(data[2].strip())\n",
    "arr = np.array([-int(x) for x in data[1].split()])\n",
    "\n",
    "# k = 3\n",
    "# s = '4 -6 7 8 -9 100 12 13 56 17'\n",
    "# arr = [-x for x in map(int, s.split())]\n",
    "        \n",
    "n = len(arr)\n",
    "for i in range(n//2)[::-1]:\n",
    "    sift_down(arr, i, n)\n",
    "    \n",
    "for i in range(k):\n",
    "    arr[0], arr[n-1-i] = arr[n-1-i], arr[0]\n",
    "    sift_down(arr, 0, n-1-i)\n",
    "    \n",
    "arr = [-x for x in arr[-k:]][::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 183,
   "id": "7d7da267-44e2-42a9-8c8b-00398118a60f",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Quick Sort\n",
    "\n",
    "from random import randint\n",
    "\n",
    "def three_way_part(arr, i):\n",
    "    \n",
    "    def swap(i, j):\n",
    "        arr[i], arr[j] = arr[j], arr[i]\n",
    "        \n",
    "    x = arr[i]\n",
    "    swap(0, i)\n",
    "    bottom_edge_eq = 1\n",
    "    bottom_edge_gt = 1\n",
    "    for i in range(1, len(arr)):\n",
    "        # print(arr)\n",
    "        if arr[i] == x:\n",
    "            swap(bottom_edge_gt, i)\n",
    "            bottom_edge_gt += 1\n",
    "        elif arr[i] < x:\n",
    "            swap(bottom_edge_gt, i)\n",
    "            swap(bottom_edge_eq, bottom_edge_gt)\n",
    "            bottom_edge_gt += 1\n",
    "            bottom_edge_eq += 1\n",
    "            \n",
    "    swap(0, bottom_edge_eq-1)\n",
    "    return arr[:bottom_edge_eq-1], arr[bottom_edge_eq-1:bottom_edge_gt], arr[bottom_edge_gt:]\n",
    "\n",
    "def quick_sort(arr):\n",
    "    i = randint(0, len(arr)-1)\n",
    "    l, m, r = three_way_part(arr, i)\n",
    "    if l:\n",
    "        l = quick_sort(l)\n",
    "    if r:\n",
    "        r = quick_sort(r)\n",
    "    return l + m + r\n",
    "\n",
    "with open('/home/hamit/Downloads/rosalind_qs.txt', 'r') as ros:\n",
    "    data = ros.readlines()\n",
    "arr = [int(x) for x in data[1].split()]\n",
    "\n",
    "arr = quick_sort(arr)"
   ]
  }
 ],
 "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.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}