{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Algorytm sortowania bąbelkowego" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "**Algorytym sortowania bąbelkowego (ang. bubble sort algorithm)**\n", "polega na porównywaniu par elementów leżących obok siebie i, jeśli jest to potrzebne, zmienianiu ich kolejności. Nazwa metody wzięła się stąd, że kolejne porównania powodują “wypychanie” kolejnego największego elementu na koniec." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Przebieg sortowania\n", "\n", "* Porównujemy pierwszy i drugi element tabeli i - jeśli trzeba - to zamieniamy je miejscami. Następnie podobnie porównujemy drugi i trzeci element i - jeśli to konieczne - zamieniamy je miejscami, itd.\n", "* Powyższe operacje wykonujemy, aż dojdziemy do końca tabeli.\n", "* Następnie ponownie rozpoczynamy porównywanie elementów od początku tabeli.\n", "* Sortowanie kończymy, gdy podczas kolejnego przejścia przez całą tabelę nie wykonana zostanie żadna zamiana.\n", "\n", "![](http://home.agh.edu.pl/~pkleczek/dokuwiki/lib/exe/fetch.php?w=951&h=702&tok=e8e20d&media=dydaktyka:aisd:2016:bubble_sort_example.png)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sortowanie bąbelkowe - pseudokod\n", "\n", "```c\n", "BUBBLE-SORT(n, T)\n", " for i := 1 to n\n", " do for j := n downto i + 1\n", " do if T[j] < T[j - 1]\n", " then swap T[j] and T[j-1]\n", "```\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Złożoność czasowa\n", "\n", "Algorytm wykonuje $n-1$ przejść, a w każdym przejściu wykonuje $n-k$ porównań (gdzie $k=1,2...n-1$ to numer przejścia), przez co jego teoretyczna złożoność czasowa wynosi $O(n^{2})$." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Optymalizacja\n", "\n", "Algorytm można rozbudować tak, by czas optymistyczny był lepszy, poprzez dodanie dodanie flagi informującej, czy w danej iteracji doszło do zmiany. Flaga jest zerowana na wejściu w przebiegu pętli, w przypadku natrafienia na zmianę jest podnoszona, a po wykonaniu przejścia sprawdzana. " ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Sortowanie bąbelkowe - python\n", "\n", "Poniższy program przeprowadza sortowanie listy z losowo ustawionymi wartościami o podanym przez użytkownika rozmiarze." ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "#zaimportowanie bibliotek\n", "import matplotlib.pyplot as plt #tworzenie wykresów\n", "from matplotlib.animation import FuncAnimation #animacja\n", "from IPython.display import HTML #animacja jako HTML\n", "import random #generowanie liczb pseudolosowych" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [], "source": [ "#funkcja pomocnicza do zamiany elementów i, j listy A\n", "def swap(A, i, j):\n", " \n", " if i != j:\n", " A[i], A[j] = A[j], A[i]\n", " \n", "#algorytm sortowania\n", "def bubblesort(A):\n", "\n", " if len(A) == 1:\n", " return\n", "\n", " swapped = True\n", " for i in range(len(A) - 1):\n", " if not swapped:\n", " break\n", " swapped = False\n", " for j in range(len(A) - 1 - i):\n", " if A[j] > A[j + 1]:\n", " swap(A, j, j + 1)\n", " swapped = True\n", " yield A" ] }, { "cell_type": "code", "execution_count": 3, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Podaj liczbę elementów w tablicy:\n", "10\n" ] } ], "source": [ "#podaj liczbę elementów w tablicy\n", "#stwórz listę pseudolosowych elementów \n", "N = int(input(\"Podaj liczbę elementów w tablicy:\\n\")) \n", "A = [i for i in range(1, N+1)] \n", "random.shuffle(A)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "data": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAXcAAAD4CAYAAAAXUaZHAAAAOXRFWHRTb2Z0d2FyZQBNYXRwbG90bGliIHZlcnNpb24zLjMuMywgaHR0cHM6Ly9tYXRwbG90bGliLm9yZy/Il7ecAAAACXBIWXMAAAsTAAALEwEAmpwYAAALYUlEQVR4nO3dUYidd5nH8e9vJ4qmtrGSoWjSML0oXUpBKsNutSBL04XuVowXslRo6YrL3KwaRZC4N73thYheLEKo1YKlssSCxV3clqrIwhI2SQtNE5dKrW1qaiqyKmWhln32Yk6ZbNiayXnfnDd55vuBMuecOWfeh5fmmzfvOfP+U1VIknr5k6kHkCSNz7hLUkPGXZIaMu6S1JBxl6SGti1yYzt37qyVlZVFblKSLntHjx79dVUtX8hrFhr3lZUVjhw5sshNStJlL8kvLvQ1npaRpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaOm/ckzyY5EyS42c99p4kTyR5bvb16os7piTpQmzmyP1bwB3nPHYAeLKqrgeenN2XJF0izhv3qvoJ8JtzHt4HPDS7/RDwsXHHkiQNMe8ye9dU1enZ7VeAa97qiUnWgDWAPXv2zLk5SYuycuCfF7atF+6/c2Hb2moGv6FaVQXUH/n+wapararV5eULWt9VkjSneeP+qyTvBZh9PTPeSJKkoeaN+2PAvbPb9wLfG2ccSdIYNvNRyEeAfwduSHIqyaeA+4G/TPIccPvsviTpEnHeN1Sr6hNv8a29I88iSRqJv6EqSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIbmXUNVA7lOpaSLySN3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpIeMuSQ0NinuSzyd5NsnxJI8kecdYg0mS5jd33JPsAj4LrFbVTcAScNdYg0mS5jf0tMw24J1JtgHbgV8OH0mSNNTca6hW1ctJvgy8CPw38HhVPX7u85KsAWsAe/bsmXdzo3HtUklbwZDTMlcD+4DrgPcBVyS5+9znVdXBqlqtqtXl5eX5J5UkbdqQ0zK3Az+vqler6g/Ao8CHxhlLkjTEkLi/CNySZHuSAHuBk+OMJUkaYu64V9Vh4BBwDHhm9rMOjjSXJGmAud9QBaiq+4D7RppFkjQSf0NVkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpoUFXhbxQz7z824Utc+cSd5K2Mo/cJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDU0KO5J3p3kUJKfJjmZ5INjDSZJmt/QlZi+Bvygqj6e5O3A9hFmkiQNNHfck+wAPgz8LUBVvQ68Ps5YkqQhhhy5Xwe8CnwzyfuBo8D+qnrt7CclWQPWAJauWh6wOUlbiestDzPknPs24APA16vqZuA14MC5T6qqg1W1WlWrS9t3DNicJGmzhsT9FHCqqg7P7h9iPfaSpInNHfeqegV4KckNs4f2AidGmUqSNMjQT8t8Bnh49kmZ54FPDh9JkjTUoLhX1dPA6jijSJLG4m+oSlJDxl2SGjLuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJamhoddz12VsUWtUQt91KqVLlUfuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8ZdkhoaHPckS0meSvL9MQaSJA03xpH7fuDkCD9HkjSSQXFPshu4E3hgnHEkSWMYuobqV4EvAle+1ROSrAFrAEtXLQ/cnDpyLVdpfHMfuSf5CHCmqo7+sedV1cGqWq2q1aXtO+bdnCTpAgw5LXMr8NEkLwDfAW5L8u1RppIkDTJ33KvqS1W1u6pWgLuAH1bV3aNNJkmam59zl6SGhr6hCkBV/Rj48Rg/S5I0nEfuktSQcZekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDY1yVUhJ41jUkoMuN9ifR+6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGpo77kmuTfKjJCeSPJtk/5iDSZLmN2QlpjeAL1TVsSRXAkeTPFFVJ0aaTZI0p7mP3KvqdFUdm93+PXAS2DXWYJKk+Y2yhmqSFeBm4PD/8701YA1g6arlMTYnjW5Ra5eC65dqMQa/oZrkXcB3gc9V1e/O/X5VHayq1apaXdq+Y+jmJEmbMCjuSd7GetgfrqpHxxlJkjTUkE/LBPgGcLKqvjLeSJKkoYYcud8K3APcluTp2X9/PdJckqQB5n5Dtar+DciIs0iSRuJvqEpSQ8Zdkhoy7pLUkHGXpIaMuyQ1ZNwlqSHjLkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDVk3CWpoVHWUJWkji7ntXU9cpekhoy7JDVk3CWpIeMuSQ0Zd0lqyLhLUkPGXZIaMu6S1JBxl6SGjLskNWTcJakh4y5JDRl3SWrIuEtSQ8Zdkhoy7pLU0KC4J7kjyX8m+VmSA2MNJUkaZu64J1kC/hH4K+BG4BNJbhxrMEnS/IYcuf8Z8LOqer6qXge+A+wbZyxJ0hCpqvlemHwcuKOq/m52/x7gz6vq0+c8bw1Ym929CTg+/7it7AR+PfUQlwj3xQb3xQb3xYYbqurKC3nBRV8gu6oOAgcBkhypqtWLvc3Lgftig/tig/tig/tiQ5IjF/qaIadlXgauPev+7tljkqSJDYn7fwDXJ7kuyduBu4DHxhlLkjTE3KdlquqNJJ8G/hVYAh6sqmfP87KD826vIffFBvfFBvfFBvfFhgveF3O/oSpJunT5G6qS1JBxl6SGFhJ3L1OwLsm1SX6U5ESSZ5Psn3qmqSVZSvJUku9PPcuUkrw7yaEkP01yMskHp55pKkk+P/vzcTzJI0neMfVMi5LkwSRnkhw/67H3JHkiyXOzr1dv5mdd9Lh7mYL/4w3gC1V1I3AL8PdbeF+8aT9wcuohLgFfA35QVX8KvJ8tuk+S7AI+C6xW1U2sf1jjrmmnWqhvAXec89gB4Mmquh54cnb/vBZx5O5lCmaq6nRVHZvd/j3rf4B3TTvVdJLsBu4EHph6likl2QF8GPgGQFW9XlX/NelQ09oGvDPJNmA78MuJ51mYqvoJ8JtzHt4HPDS7/RDwsc38rEXEfRfw0ln3T7GFg/amJCvAzcDhiUeZ0leBLwL/M/EcU7sOeBX45uwU1QNJrph6qClU1cvAl4EXgdPAb6vq8Wmnmtw1VXV6dvsV4JrNvMg3VCeQ5F3Ad4HPVdXvpp5nCkk+ApypqqNTz3IJ2AZ8APh6Vd0MvMYm/+ndzex88j7W/8J7H3BFkrunnerSUeufXd/U59cXEXcvU3CWJG9jPewPV9WjU88zoVuBjyZ5gfVTdbcl+fa0I03mFHCqqt78V9wh1mO/Fd0O/LyqXq2qPwCPAh+aeKap/SrJewFmX89s5kWLiLuXKZhJEtbPq56sqq9MPc+UqupLVbW7qlZY/3/ih1W1JY/QquoV4KUkN8we2gucmHCkKb0I3JJk++zPy1626JvLZ3kMuHd2+17ge5t50SKuCjnPZQq6uhW4B3gmydOzx/6hqv5lupF0ifgM8PDsAOh54JMTzzOJqjqc5BBwjPVPlz3FFroMQZJHgL8AdiY5BdwH3A/8U5JPAb8A/mZTP8vLD0hSP76hKkkNGXdJasi4S1JDxl2SGjLuktSQcZekhoy7JDX0v3/BZwRgOoMQAAAAAElFTkSuQmCC\n", "text/plain": [ "
" ] }, "metadata": { "needs_background": "light" }, "output_type": "display_data" } ], "source": [ "#obiekt generujący\n", "generator = bubblesort(A)\n", "\n", "#zainicjalizuj wykres i oś\n", "fig, ax = plt.subplots() \n", "\n", "rects = ax.bar(range(len(A)), A, align=\"edge\")\n", "\n", "#ustaw limit widoku dla osi x i y\n", "ax.set_xlim(0, len(A)) \n", "ax.set_ylim(0, int(1.1*len(A))) \n", "\n", "#ustaw tekst z liczbą operacji w odniesieniu do współrzędnych osi (do animacji)\n", "text = ax.text(0.02, 0.95, \"\", transform=ax.transAxes)\n", "iteration = [0]" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [], "source": [ "#funkcja animacji\n", "def animate(A, rects, iteration): \n", "\n", " #ustala wielkość słupka adekwatną do wielkości elementu tablicy\n", " for rect, val in zip(rects, A): \n", " rect.set_height(val)\n", " \n", " #iteracja po każdym dokonanym porównaniu\n", " #(liczba operacji)\n", " iteration[0] += 1\n", " text.set_text(\"Liczba operacji : {}\".format(iteration[0]))\n", "\n", "\n", "anim = FuncAnimation(fig, func=animate, \n", " fargs=(rects, iteration), frames=generator, interval=500, \n", " repeat=False)" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Animacja sortowania bąbelkowego" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "data": { "text/html": [ "" ], "text/plain": [ "" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "HTML(anim.to_html5_video())" ] }, { "cell_type": "code", "execution_count": null, "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.9.0" } }, "nbformat": 4, "nbformat_minor": 4 }