Lab 10.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "relative-nomination",
   "metadata": {},
   "source": [
    "## Sortowanie przez wstawianie"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "american-scene",
   "metadata": {},
   "source": [
    "arr - tablica którą chcemy posortować <br>\n",
    "p - lewy indeks tablicy <br>\n",
    "r - prawy indeks tablicy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "weekly-dryer",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Insertion_Sort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(1, n):\n",
    "        key = arr[i]\n",
    "        j = i-1\n",
    "        while j >= 0 and key < arr[j]:\n",
    "                arr[j + 1] = arr[j]\n",
    "                j -= 1\n",
    "        arr[j + 1] = key"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "understood-round",
   "metadata": {},
   "outputs": [],
   "source": [
    "# arr[1], arr[2], ..., arr[j], arr[i] -key\n",
    "# [arr[1], ... arr[j]] - jest już posortowana"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "textile-alabama",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "array = [ 10, 7, 8, 9, 1, 5 ]\n",
    "Insertion_Sort(array)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "potential-priest",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-101, -20, -5, 1, 2, 20, 101, 499]\n"
     ]
    }
   ],
   "source": [
    "array_ = [-20, -101, 499, 20, 1, -5, 101, 2]\n",
    "Insertion_Sort(array_)\n",
    "print(array_)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "normal-november",
   "metadata": {},
   "source": [
    "## Sortowanie przez wybieranie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "included-professor",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Selection_Sort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n):\n",
    "        min_idx = i\n",
    "        for j in range(i+1, n):\n",
    "            if arr[min_idx] > arr[j]:\n",
    "                min_idx = j\n",
    "        temp = arr[i]\n",
    "        arr[i] = arr[min_idx]\n",
    "        arr[min_idx] = temp\n",
    "    # A[i], A[min_idx] = A[min_idx], A[i]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "hired-collector",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "array = [ 10, 7, 8, 9, 1, 5 ]\n",
    "Selection_Sort(array)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "intelligent-cisco",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-101, -20, -5, 1, 2, 20, 101, 499]\n"
     ]
    }
   ],
   "source": [
    "array_ = [-20, -101, 499, 20, 1, -5, 101, 2]\n",
    "Selection_Sort(array_)\n",
    "print(array_)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "olympic-hospital",
   "metadata": {},
   "source": [
    "## Sortowanie bąbelkowe"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "therapeutic-affairs",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Bubble_Sort(arr):\n",
    "    n = len(arr)\n",
    "    for i in range(n):\n",
    "        for j in range(n-i-1):\n",
    "            if arr[j] > arr[j+1]:\n",
    "                temp = arr[j]\n",
    "                arr[j] = arr[j + 1]\n",
    "                arr[j + 1] = temp\n",
    "                # arr[j], arr[j+1] = arr[j+1], arr[j]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "accessible-element",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "array = [ 10, 7, 8, 9, 1, 5 ]\n",
    "Bubble_Sort(array)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "id": "expected-corps",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-101, -20, -5, 1, 2, 20, 101, 499]\n"
     ]
    }
   ],
   "source": [
    "array_ = [-20, -101, 499, 20, 1, -5, 101, 2]\n",
    "Bubble_Sort(array_)\n",
    "print(array_)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dried-plasma",
   "metadata": {},
   "source": [
    "## Sortowanie przez scalanie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "id": "sixth-lithuania",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Merge_Sort(arr, p, q):\n",
    "    def MergeSort(arr):\n",
    "        if len(arr) <= 1:\n",
    "            return arr\n",
    "        mid = len(arr)//2\n",
    "        L = arr[:mid]\n",
    "        R = arr[mid:]\n",
    "\n",
    "        MergeSort(L)\n",
    "        MergeSort(R)\n",
    "        i = j = k = 0\n",
    "        while i < len(L) and j < len(R):\n",
    "            if L[i] < R[j]:\n",
    "                arr[k] = L[i]\n",
    "                i += 1\n",
    "            else:\n",
    "                arr[k] = R[j]\n",
    "                j += 1\n",
    "            k += 1\n",
    "\n",
    "        while i < len(L):\n",
    "            arr[k] = L[i]\n",
    "            i += 1\n",
    "            k += 1\n",
    "\n",
    "        while j < len(R):\n",
    "            arr[k] = R[j]\n",
    "            j += 1\n",
    "            k += 1\n",
    "        return arr\n",
    "    return MergeSort(arr[p:q + 1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "id": "unable-radius",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "array = [ 10, 7, 8, 9, 1, 5 ]\n",
    "arr = Merge_Sort(array, 0, len(array) - 1)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "id": "available-differential",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-101, -20, -5, 1, 2, 20, 101, 499]\n"
     ]
    }
   ],
   "source": [
    "array_ = [-20, -101, 499, 20, 1, -5, 101, 2]\n",
    "arr = Merge_Sort(array_, 0, len(array_) - 1)\n",
    "print(arr)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "comfortable-hometown",
   "metadata": {},
   "source": [
    "## Sortowanie szybkie"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "id": "lonely-hawaiian",
   "metadata": {},
   "outputs": [],
   "source": [
    "def Quick_Sort(arr, p, q):  \n",
    "    if (p < q):\n",
    "        r = partition(arr, p, q)\n",
    "        Quick_Sort(arr, p, r -1)\n",
    "        Quick_Sort(arr, r + 1, q)\n",
    "        \n",
    "def partition(arr, p, q):\n",
    "    pivot = arr[q] # element do partycjonowania, na wykładzie było arr[p]\n",
    "    i = p - 1 # indeks gdzie musi trafić pivot\n",
    "    for j in range(p, q):\n",
    "        if arr[j] < pivot:\n",
    "            i += 1 # zwiększamy indeks pivotu\n",
    "            temp = arr[i]\n",
    "            arr[i] = arr[j]\n",
    "            arr[j] = temp\n",
    "            # arr[i], arr[j] = arr[j], arr[i]\n",
    "            \n",
    "    temp = arr[i + 1]\n",
    "    arr[i + 1] = arr[q]\n",
    "    arr[q] = temp\n",
    "    # arr[i + 1], arr[q] = arr[q], arr[i + 1]\n",
    "    # w tym momencie wszystko to co na lewo od arr[i + 1] jest mniejsze\n",
    "    # bądź równe pivot, a to co na prawo od arr[i + 1] jest większe bądź równe pivot\n",
    "    return i + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "id": "capital-workshop",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 5, 7, 8, 9, 10]\n"
     ]
    }
   ],
   "source": [
    "array = [ 10, 7, 8, 9, 1, 5 ]\n",
    "Quick_Sort(array, 0, len(array) - 1)\n",
    "print(array)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "id": "confirmed-tribute",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[-101, -20, -5, 1, 2, 20, 101, 499]\n"
     ]
    }
   ],
   "source": [
    "array_ = [-20, -101, 499, 20, 1, -5, 101, 2]\n",
    "Quick_Sort(array_, 0, len(array_) - 1)\n",
    "print(array_)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "annual-price",
   "metadata": {},
   "source": [
    "## Zadania"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "moral-newcastle",
   "metadata": {},
   "source": [
    "1)* Zmodyfikować kod z sortowania szybkiego tak, aby w funkcja partycjonowania wybierała pierwszy element."
   ]
  },
  {
   "cell_type": "markdown",
   "id": "demanding-facial",
   "metadata": {},
   "source": [
    "2)* Usprawnij kod z sortowania bąbelkowego tak, aby polepszyć jego złożoność optymistyczną"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "upset-procedure",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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.8.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}