Vetores_Ordenados.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Vetores Ordenados.ipynb",
      "provenance": [],
      "collapsed_sections": [],
      "authorship_tag": "ABX9TyMKE2xVSL5CksSOmLK83c3R",
      "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/emanamoura/estrutura_de_dados_com_python/blob/main/Vetores_Ordenados.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 15,
      "metadata": {
        "id": "iaqubR9yVD8F"
      },
      "outputs": [],
      "source": [
        "import  numpy as np"
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "class VetorOrdenado:\n",
        "  def __init__(self, capacidade):\n",
        "    self.capacidade = capacidade\n",
        "    self.ultima_posicao = -1\n",
        "    self.valores = np.empty(self.capacidade, dtype=int)\n",
        "\n",
        "  # O(n)\n",
        "  def imprime(self):\n",
        "    if self.ultima_posicao == -1:\n",
        "      print(\"O vetor está vazio\")\n",
        "    else:\n",
        "      for i in range(self.ultima_posicao + 1):\n",
        "        print(i, ' - ', self.valores[i])\n",
        "  # O(n)\n",
        "  def insere(self, valor):\n",
        "    if self.ultima_posicao == self.capacidade - 1:\n",
        "      print(\"O vetor está cheio\")\n",
        "      return\n",
        "    \n",
        "    posicao = 0\n",
        "    for i in range(self.ultima_posicao +  1):\n",
        "      posicao = i\n",
        "      if self.valores[i] > valor:\n",
        "        break\n",
        "      if i == self.ultima_posicao:\n",
        "        posicao = i + 1\n",
        "    \n",
        "    x = self.ultima_posicao\n",
        "    while x >= posicao:\n",
        "      self.valores[x + 1] = self.valores[x]\n",
        "      x -= 1\n",
        "    \n",
        "    self.valores[posicao] = valor\n",
        "    self.ultima_posicao += 1\n",
        "  # O(n)\n",
        "  def pesquisar(self, valor):\n",
        "    for i in range(self.ultima_posicao + 1):\n",
        "      if self.valores[i] > valor:\n",
        "        return -1\n",
        "      if valor == self.valores[i]:\n",
        "        return i\n",
        "      if i == self.ultima_posicao:\n",
        "        return -1\n",
        "  \n",
        "  def pesquisaBinaria(self, valor):\n",
        "    limite_inferior = 0\n",
        "    limite_superior = self.ultima_posicao\n",
        "\n",
        "    while True:\n",
        "      posicao_atual = int((limite_inferior + limite_superior) / 2)\n",
        "      # Se achou na primeira tentativa\n",
        "      if self.valores[posicao_atual] == valor:\n",
        "        return posicao_atual\n",
        "      elif limite_inferior > limite_superior:\n",
        "        return -1\n",
        "      else:\n",
        "        if self.valores[posicao_atual] < valor:\n",
        "          limite_inferior = posicao_atual + 1\n",
        "        else:\n",
        "          limite_superior = posicao_atual - 1\n",
        "  \n",
        "  # O(n)\n",
        "  def excluir(self, valor):\n",
        "    posicao = self.pesquisar(valor)\n",
        "    if posicao == -1:\n",
        "      return -1\n",
        "    else:\n",
        "      for i in range(posicao, self.ultima_posicao):\n",
        "        self.valores[i] = self.valores[i + 1]\n",
        "      \n",
        "      self.ultima_posicao -= 1"
      ],
      "metadata": {
        "id": "Ts2SNYJZZkCb"
      },
      "execution_count": 16,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "vetor = VetorOrdenado(10)\n",
        "vetor.insere(6)\n",
        "vetor.imprime()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "5OSMqlOObYJO",
        "outputId": "f0a7106f-aa5f-41b2-cefe-91e46d3cf876"
      },
      "execution_count": 17,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  6\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.insere(4)\n",
        "vetor.imprime()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "fS7WefFYbbRf",
        "outputId": "7e45977f-20df-469e-d516-cf690f815943"
      },
      "execution_count": 18,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  4\n",
            "1  -  6\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.insere(3)\n",
        "vetor.imprime()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "whbxBZRBbm0b",
        "outputId": "e1f022c0-b5fb-4be5-e281-018bb311fc46"
      },
      "execution_count": 19,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  3\n",
            "1  -  4\n",
            "2  -  6\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.insere(5)\n",
        "vetor.imprime()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "zy_cGRwIbrvm",
        "outputId": "6c92e5fa-d593-4964-cd52-5459aacf8821"
      },
      "execution_count": 20,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  3\n",
            "1  -  4\n",
            "2  -  5\n",
            "3  -  6\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.insere(9)\n",
        "vetor.imprime()\n",
        "vetor.pesquisar(8)\n",
        "vetor.pesquisar(10)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "MDIpozM5hyKl",
        "outputId": "8fc3d015-2603-4e97-f895-96df0de490e7"
      },
      "execution_count": 21,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  3\n",
            "1  -  4\n",
            "2  -  5\n",
            "3  -  6\n",
            "4  -  9\n"
          ]
        },
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "-1"
            ]
          },
          "metadata": {},
          "execution_count": 21
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.excluir(5)"
      ],
      "metadata": {
        "id": "hoHy0cqgkl5c"
      },
      "execution_count": 22,
      "outputs": []
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.imprime()"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "kODiRr52ks3V",
        "outputId": "c6c9aed8-00ef-42b1-d7c8-525ff01ebda6"
      },
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "0  -  3\n",
            "1  -  4\n",
            "2  -  6\n",
            "3  -  9\n"
          ]
        }
      ]
    },
    {
      "cell_type": "code",
      "source": [
        "vetor.pesquisaBinaria(6)"
      ],
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "id": "77h4fuf2x8Q8",
        "outputId": "ef8a9016-efea-4391-e369-e05034f3b2a9"
      },
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "execute_result",
          "data": {
            "text/plain": [
              "2"
            ]
          },
          "metadata": {},
          "execution_count": 24
        }
      ]
    }
  ]
}