algoritmos_de_ordenacao.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "provenance": [],
      "authorship_tag": "ABX9TyOKMwwVo7F3c96QcF6M4Sdf",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/araujosantos-yasmin/atividades_curso_/blob/main/algoritmos_de_ordenacao.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algoritmo de Ordenação por Seleção (*Selection Sort*)"
      ],
      "metadata": {
        "id": "WO_HOg75z2-F"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_selection_sort(lista):\n",
        "    n = len(lista)\n",
        "\n",
        "    for i in range(0, n):\n",
        "        index_menor = i\n",
        "        for j in range(i+1, n):\n",
        "            if lista[j] < lista[index_menor]:\n",
        "                index_menor = j\n",
        "        lista[i], lista[index_menor] = lista[index_menor], lista[i]\n",
        "    return lista\n",
        "\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_selection_sort(lista)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kiPqUa9Dz-YM",
        "outputId": "8830c988-7c23-4e7e-a2a4-7fd4e691284e"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 4
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_selection_sort_2(lista):\n",
        "    lista_ordenada = []\n",
        "    while lista:\n",
        "        minimo = min(lista)\n",
        "        lista_ordenada.append(minimo)\n",
        "        lista.remove(minimo)\n",
        "    return lista_ordenada\n",
        "\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_selection_sort_2(lista)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "AhFt7XZ70Kc7",
        "outputId": "55a87394-440b-4c25-9e66-a2c66db6f41d"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 5
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algoritmo de Ordenação por Inserção (*Insertion Sort*)"
      ],
      "metadata": {
        "id": "CyBY85STXAts"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_insertion_sort(lista):\n",
        "    n = len(lista)\n",
        "    for i in range(1, n):\n",
        "        valor_inserir = lista[i]\n",
        "        j = i - 1\n",
        "\n",
        "        while j >= 0 and lista[j] > valor_inserir:\n",
        "            lista[j + 1] = lista[j]\n",
        "            j -= 1\n",
        "        lista[j + 1] = valor_inserir\n",
        "\n",
        "    return lista\n",
        "\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_insertion_sort(lista)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "-wcjQBTmXShL",
        "outputId": "b043c290-8c64-4435-a660-6e403d9e056a"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 1
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algoritmo de Ordenação por Bolha (*Bubble Sort*)"
      ],
      "metadata": {
        "id": "TWQiwNk-5FUb"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_bubble_sort(lista):\n",
        "    n = len(lista)\n",
        "    for i in range(n-1):\n",
        "        for j in range(n-1):\n",
        "            if lista[j] > lista[j + 1]:\n",
        "                lista[j], lista[j + 1] = lista[j + 1], lista[j]\n",
        "    return lista\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_bubble_sort(lista)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "cellView": "code",
        "id": "6RNkf8W_5Lmx",
        "outputId": "016f9e59-9d4e-4cb0-a149-e5c08d1fd54b"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 3
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algoritmo de Ordenação por Junção (*Merge Sort*)"
      ],
      "metadata": {
        "id": "aeJhLimADoji"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_merge_sort(lista):\n",
        "    if len(lista) <= 1: return lista\n",
        "    else:\n",
        "        meio = len(lista) // 2\n",
        "        esquerda = executar_merge_sort(lista[:meio])\n",
        "        direita = executar_merge_sort(lista[meio:])\n",
        "        return executar_merge(esquerda, direita)\n",
        "\n",
        "\n",
        "def executar_merge(esquerda, direita):\n",
        "    sub_lista_ordenada = []\n",
        "    topo_esquerda, topo_direita = 0, 0\n",
        "    while topo_esquerda < len(esquerda) and topo_direita < len(direita):\n",
        "        if esquerda[topo_esquerda] <= direita[topo_direita]:\n",
        "            sub_lista_ordenada.append(esquerda[topo_esquerda])\n",
        "            topo_esquerda += 1\n",
        "        else:\n",
        "            sub_lista_ordenada.append(direita[topo_direita])\n",
        "            topo_direita += 1\n",
        "    sub_lista_ordenada += esquerda[topo_esquerda:]\n",
        "    sub_lista_ordenada += direita[topo_direita:]\n",
        "    return sub_lista_ordenada\n",
        "\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_merge_sort(lista)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "lRRhajUPDxjn",
        "outputId": "d0c4a3fb-edfc-465f-db24-e371e26d52a9"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 6
        }
      ]
    },
    {
      "cell_type": "markdown",
      "source": [
        "Algoritmo de Ordenação Rápida (Quick Sort)"
      ],
      "metadata": {
        "id": "AUGsfV_YGDBq"
      }
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_quicksort(lista, inicio, fim):\n",
        "    if inicio < fim:\n",
        "        pivo = executar_particao(lista, inicio, fim)\n",
        "        executar_quicksort(lista, inicio, pivo-1)\n",
        "        executar_quicksort(lista, pivo+1, fim)\n",
        "    return lista\n",
        "\n",
        "\n",
        "def executar_particao(lista, inicio, fim):\n",
        "    pivo = lista[fim]\n",
        "    esquerda = inicio\n",
        "    for direita in range(inicio, fim):\n",
        "        if lista[direita] <= pivo:\n",
        "            lista[direita], lista[esquerda] = lista[esquerda], lista[direita]\n",
        "            esquerda += 1\n",
        "    lista[esquerda], lista[fim] = lista[fim], lista[esquerda]\n",
        "    return esquerda\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_quicksort(lista, inicio=0, fim=len(lista)-1)\n"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "rYTCoEIgGI4j",
        "outputId": "f7651b6d-2b0f-4eb1-bc93-b441b301e8d6"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 7
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "def executar_quicksort_2(lista):\n",
        "    if len(lista) <= 1: return lista\n",
        "    pivo = lista[0]\n",
        "    iguais  = [valor for valor in lista if valor == pivo]\n",
        "    menores = [valor for valor in lista if valor <  pivo]\n",
        "    maiores = [valor for valor in lista if valor >  pivo]\n",
        "    return executar_quicksort_2(menores) + iguais + executar_quicksort_2(maiores)\n",
        "\n",
        "\n",
        "lista = [10, 9, 5, 8, 11, -1, 3]\n",
        "executar_quicksort_2(lista)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "CIipwqRKGLXY",
        "outputId": "46f1a95a-cab3-43b6-cc5c-eff6a5f319f1"
      },
      "execution_count": null,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "[-1, 3, 5, 8, 9, 10, 11]"
            ]
          },
          "metadata": {},
          "execution_count": 8
        }
      ]
    }
  ]
}