Algorithms/Sorting/Bubble_Sort.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "\"\"\"This notebook shows the bubble sort\"\"\"\n",
    "# ----------------------------\n",
    "# Bubble sort\n",
    "\"\"\"\n",
    "Compare consecutive pairs of elements\n",
    "Swap elements in pair such that the smaller is first\n",
    "When reach the end of list start over again\n",
    "Stop when no more swaps have been made\n",
    "Largest unsorted element always at the end after a pass, \n",
    "so at most n passes\n",
    "\"\"\"\n",
    "#-----------------------------\n",
    "# We have list A\n",
    "# with n = 9 elements\n",
    "\n",
    "A = [6,5,7,4,8,3,1,9,2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "def bubble_sort(A):\n",
    "    '''Perform bubble sort and return the sorted list'''\n",
    "    n = len(A)\n",
    "    for i in range(n-1):\n",
    "        for j in range(i+1,n):\n",
    "            print(f\"index A[{i}], {A[i]}   A[{j}], {A[j]}\")\n",
    "            if A[i] > A[j]: \n",
    "                A[i], A[j] = A[j], A[i]\n",
    "        print(A)\n",
    "    return A"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "index A[0], 6   A[1], 5\n",
      "index A[0], 5   A[2], 7\n",
      "index A[0], 5   A[3], 4\n",
      "index A[0], 4   A[4], 8\n",
      "index A[0], 4   A[5], 3\n",
      "index A[0], 3   A[6], 1\n",
      "index A[0], 1   A[7], 9\n",
      "index A[0], 1   A[8], 2\n",
      "[1, 6, 7, 5, 8, 4, 3, 9, 2]\n",
      "index A[1], 6   A[2], 7\n",
      "index A[1], 6   A[3], 5\n",
      "index A[1], 5   A[4], 8\n",
      "index A[1], 5   A[5], 4\n",
      "index A[1], 4   A[6], 3\n",
      "index A[1], 3   A[7], 9\n",
      "index A[1], 3   A[8], 2\n",
      "[1, 2, 7, 6, 8, 5, 4, 9, 3]\n",
      "index A[2], 7   A[3], 6\n",
      "index A[2], 6   A[4], 8\n",
      "index A[2], 6   A[5], 5\n",
      "index A[2], 5   A[6], 4\n",
      "index A[2], 4   A[7], 9\n",
      "index A[2], 4   A[8], 3\n",
      "[1, 2, 3, 7, 8, 6, 5, 9, 4]\n",
      "index A[3], 7   A[4], 8\n",
      "index A[3], 7   A[5], 6\n",
      "index A[3], 6   A[6], 5\n",
      "index A[3], 5   A[7], 9\n",
      "index A[3], 5   A[8], 4\n",
      "[1, 2, 3, 4, 8, 7, 6, 9, 5]\n",
      "index A[4], 8   A[5], 7\n",
      "index A[4], 7   A[6], 6\n",
      "index A[4], 6   A[7], 9\n",
      "index A[4], 6   A[8], 5\n",
      "[1, 2, 3, 4, 5, 8, 7, 9, 6]\n",
      "index A[5], 8   A[6], 7\n",
      "index A[5], 7   A[7], 9\n",
      "index A[5], 7   A[8], 6\n",
      "[1, 2, 3, 4, 5, 6, 8, 9, 7]\n",
      "index A[6], 8   A[7], 9\n",
      "index A[6], 8   A[8], 7\n",
      "[1, 2, 3, 4, 5, 6, 7, 9, 8]\n",
      "index A[7], 9   A[8], 8\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
      "[1, 2, 3, 4, 5, 6, 7, 8, 9]\n"
     ]
    }
   ],
   "source": [
    "print(bubble_sort(A))"
   ]
  }
 ],
 "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.10"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}