{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "# Algoritma Sorting (Pengurutan)\n",
    "Algoritma Sorting, atau pengurutan, adalah konsep penting dalam ilmu komputer yang memungkinkan pengaturan elemen-elemen data menjadi urutan yang teratur. Dengan mengikuti aturan tertentu, algoritma ini membantu data menjadi lebih teratur dan mudah diakses. Baik dalam aplikasi sehari-hari seperti daftar nama di telepon atau dalam analisis data besar, pemahaman tentang berbagai algoritma pengurutan memberikan fondasi bagi keterampilan pemrograman yang efektif."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 1. Bubble Sort\n",
    "Bubble Sort adalah metode pengurutan algoritma dengan cara melakukan penukaran data secara terus menerus sampai bisa dipastikan dalam suatu **iterasi** tertentu tidak ada lagi perubahan/penukaran. Algoritma ini menggunakan perbandingan dalam operasi antar elemennya."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Berikut ini adalah gambaran dari algoritma bubble sort:\n",
    "1. Bandingkan nilai data ke-1 dan data ke-2\n",
    "2. Jika data ke-1 lebih besar dari data ke-2 maka tukar posisinya\n",
    "3. Kemudian data yg lebih besar tadi dibandingkan dengan data ke-3\n",
    "4. Lakukan langkah nomer 2 hingga selesai.\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![gambar5](https://www.w3resource.com/w3r_images/bubble-short.png)\n",
    "Sumber: https://www.w3resource.com/w3r_images/bubble-short.png"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def bubble_sort(arr):\n",
    "    n = len(arr)\n",
    "    \n",
    "    for i in range(n):\n",
    "        swapped = False  # Inisialisasi flag untuk memantau apakah ada pertukaran pada iterasi ini\n",
    "        \n",
    "        # Loop untuk membandingkan dan menukar elemen-elemen\n",
    "        for j in range(n - 1 - i):\n",
    "            if arr[j] > arr[j + 1]:\n",
    "                arr[j], arr[j + 1] = arr[j + 1], arr[j]  # Tukar elemen jika urutan salah\n",
    "                swapped = True\n",
    "        \n",
    "        if not swapped:\n",
    "            break  # Jika tidak ada pertukaran, koleksi sudah terurut, hentikan iterasi"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Array sebelum diurutkan: [64, 34, 25, 12, 22, 11, 90]\n",
      "Array setelah diurutkan: [11, 12, 22, 25, 34, 64, 90]\n"
     ]
    }
   ],
   "source": [
    "# Contoh penggunaan\n",
    "arr = [64, 34, 25, 12, 22, 11, 90]\n",
    "print(\"Array sebelum diurutkan:\", arr)\n",
    "\n",
    "bubble_sort(arr)\n",
    "print(\"Array setelah diurutkan:\", arr)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Judul lagu sebelum diurutkan: ['Bintang Kehidupan', 'Pelangi', 'Seperti Yang Kau Minta', 'Menunggu Pagi', 'Kisah Klasik Untuk Masa Depan']\n",
      "Judul lagu setelah diurutkan: ['Bintang Kehidupan', 'Kisah Klasik Untuk Masa Depan', 'Menunggu Pagi', 'Pelangi', 'Seperti Yang Kau Minta']\n"
     ]
    }
   ],
   "source": [
    "# Contoh penggunaan\n",
    "judul_lagu = [\n",
    "    \"Bintang Kehidupan\",\n",
    "    \"Pelangi\",\n",
    "    \"Seperti Yang Kau Minta\",\n",
    "    \"Menunggu Pagi\",\n",
    "    \"Kisah Klasik Untuk Masa Depan\"\n",
    "]\n",
    "\n",
    "print(\"Judul lagu sebelum diurutkan:\", judul_lagu)\n",
    "\n",
    "bubble_sort(judul_lagu)\n",
    "print(\"Judul lagu setelah diurutkan:\", judul_lagu)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 2. Insertion Sort\n",
    "Insertion Sort adalah salah satu algoritma pengurutan sederhana yang bekerja dengan cara membandingkan dan menyisipkan elemen-elemen data dalam urutan yang benar satu per satu. Prinsip dasar Insertion Sort adalah bahwa algoritma ini mempertimbangkan setiap elemen dalam data dan memasukkannya ke dalam posisi yang tepat dalam subkoleksi yang telah diurutkan sebelumnya."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "Berikut adalah cara kerja Insertion Sort:\n",
    "1. Algoritma memulai dengan menganggap bahwa elemen pertama dalam data sudah dalam keadaan terurut.\n",
    "2. Algoritma kemudian memilih elemen kedua dan membandingkannya dengan elemen pertama. Jika elemen kedua lebih kecil, algoritma menukar posisi keduanya.\n",
    "3. Algoritma kemudian memasukkan elemen ketiga ke dalam subkoleksi yang terurut sebelumnya. Algoritma membandingkan elemen ketiga dengan elemen-elemen dalam subkoleksi dan memindahkan elemen-elemen yang lebih besar ke kanan untuk membuat ruang bagi elemen ketiga.\n",
    "4. Langkah ini diulang untuk setiap elemen dalam data, di mana setiap elemen dimasukkan ke dalam subkoleksi yang telah diurutkan sebelumnya dengan cara membandingkan dan menyisipkannya ke posisi yang tepat.\n",
    "5. Setelah semua elemen dimasukkan ke dalam subkoleksi yang telah diurutkan, hasil akhir adalah data yang terurut."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![image](https://media.geeksforgeeks.org/wp-content/uploads/insertion_sort-recursion.png)\n",
    "\n",
    "Sumber: https://www.geeksforgeeks.org/recursive-insertion-sort/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [],
   "source": [
    "def insertion_sort(arr):\n",
    "    n = len(arr)\n",
    "    \n",
    "    for i in range(1, n):\n",
    "        key = arr[i]\n",
    "        j = i - 1\n",
    "        \n",
    "        while j >= 0 and key < arr[j]:\n",
    "            arr[j + 1] = arr[j]  # Geser elemen yang lebih besar ke kanan\n",
    "            j -= 1\n",
    "        \n",
    "        arr[j + 1] = key  # Tempatkan elemen saat ini ke posisi yang benar"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Data sebelum diurutkan: [9, 7, 6, 15, 16, 5, 10, 11]\n",
      "Data setelah diurutkan: [5, 6, 7, 9, 10, 11, 15, 16]\n"
     ]
    }
   ],
   "source": [
    "# Contoh penggunaan\n",
    "data = [9, 7, 6, 15, 16, 5, 10, 11]\n",
    "print(\"Data sebelum diurutkan:\", data)\n",
    "\n",
    "insertion_sort(data)\n",
    "print(\"Data setelah diurutkan:\", data)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "## 3. Selection Sort\n",
    "Selection Sort adalah perbaikan dari algoritma bubble sort, dengan mengurangi jumlah perbandingan. Dikatakan selection sort karena algoritma ini mencoba memilih satu per satu elemen data dari posisi awal, untuk mencari data paling kecil dengan mencatat posisi index-nya saja, lalu dilakukan pertukaran hanya sekali pada akhir setiap tahapan."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "source": [
    "![selection sort](https://www.w3resource.com/w3r_images/selection-short.png)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    }
   },
   "outputs": [
    {
     "name": "stdin",
     "output_type": "stream",
     "text": [
      "Enter numbers separated by a comma:\n",
      " 5,1,2,3,4,5,6,222,222,99\n"
     ]
    },
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[1, 2, 3, 4, 5, 5, 6, 99, 222, 222]\n"
     ]
    }
   ],
   "source": [
    "def selection_sort(collection):\n",
    "    \"\"\"Pure implementation of the selection sort algorithm in Python\n",
    "    :param collection: some mutable ordered collection with heterogeneous\n",
    "    comparable items inside\n",
    "    :return: the same collection ordered by ascending\n",
    "    Examples:\n",
    "    >>> selection_sort([0, 5, 3, 2, 2])\n",
    "    [0, 2, 2, 3, 5]\n",
    "    >>> selection_sort([])\n",
    "    []\n",
    "    >>> selection_sort([-2, -5, -45])\n",
    "    [-45, -5, -2]\n",
    "    \"\"\"\n",
    "\n",
    "    length = len(collection)\n",
    "    for i in range(length - 1):\n",
    "        least = i\n",
    "        for k in range(i + 1, length):\n",
    "            if collection[k] < collection[least]:\n",
    "                least = k\n",
    "        if least != i:\n",
    "            collection[least], collection[i] = (collection[i], collection[least])\n",
    "    return collection\n",
    "\n",
    "\n",
    "user_input = input(\"Enter numbers separated by a comma:\\n\").strip()\n",
    "unsorted = [int(item) for item in user_input.split(\",\")]\n",
    "print(selection_sort(unsorted))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "def selection_sort(collection):\n",
    "    \"\"\"Pure implementation of the selection sort algorithm in Python\n",
    "    :param collection: some mutable ordered collection with heterogeneous\n",
    "    comparable items inside\n",
    "    :return: the same collection ordered by ascending\n",
    "    Examples:\n",
    "    >>> selection_sort([\"apple\", \"banana\", \"cherry\", \"date\"])\n",
    "    ['apple', 'banana', 'cherry', 'date']\n",
    "    >>> selection_sort([])\n",
    "    []\n",
    "    >>> selection_sort([\"zebra\", \"lion\", \"elephant\", \"tiger\"])\n",
    "    ['elephant', 'lion', 'tiger', 'zebra']\n",
    "    \"\"\"\n",
    "\n",
    "    length = len(collection)\n",
    "    for i in range(length - 1):\n",
    "        least = i\n",
    "        for k in range(i + 1, length):\n",
    "            if collection[k] < collection[least]:\n",
    "                least = k\n",
    "        if least != i:\n",
    "            collection[least], collection[i] = (collection[i], collection[least])\n",
    "    return collection\n",
    "\n",
    "user_input = input(\"Enter strings separated by a comma:\\n\").strip()\n",
    "unsorted = [item for item in user_input.split(\",\")]\n",
    "print(selection_sort(unsorted))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Slideshow",
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "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.11.4"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}