marathon_day7.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "marathon_day7.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyPw6fNRqCzYpw7s3v6fHo+o",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sweetpand/Algorithms/blob/master/marathon_day7.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "HS5L0RJPsVki",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "1. Отсортировать по убыванию методом «пузырька» одномерный целочисленный массив, заданный случайными числами \n",
        "на промежутке [-100; 100). Вывести на экран исходный и отсортированный массивы.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYwH98ZirQox",
        "colab_type": "code",
        "outputId": "0593e5c9-2ccb-4413-e4de-ac2d2820ac8a",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 51
        }
      },
      "source": [
        "import random\n",
        "\n",
        "lst = [random.randrange(-100, 100, 1) for _i in range(30)]\n",
        "print('unsort', lst)\n",
        "\n",
        "def babble_sort(array):\n",
        "    n = len(array)\n",
        "    not_ordered = True\n",
        "    while not_ordered:\n",
        "        not_ordered = False # немного сократит число внешних итераций\n",
        "        for i in range(n): # оптимизация, позволяющая сократить число внутренних итераций в 2 раза\n",
        "            index = len(array) - i - 1\n",
        "            if array[index] > array[index - 1]:\n",
        "                array[index - 1], array[index] = array[index], array[index - 1]\n",
        "                not_ordered = True\n",
        "        n -= 1\n",
        "    return array\n",
        "\n",
        "print('sort', babble_sort(lst))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "unsort [-90, 50, -26, 82, 93, -95, -66, 77, 96, 28, 98, -31, -6, -1, 8, -1, -74, -27, -32, 39, 56, 60, 69, -46, -75, -1, -66, 5, 5, 38]\n",
            "sort [98, 96, 93, 82, 77, 69, 60, 56, 50, 39, 38, 28, 8, 5, 5, -1, -1, -1, -6, -26, -27, -31, -32, -46, -66, -66, -74, -75, -90, -95]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "NDArd8frskST",
        "colab_type": "text"
      },
      "source": [
        "\n",
        "2. Отсортируйте по возрастанию методом слияния одномерный вещественный массив, заданный случайными числами \n",
        "на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mM_LJ_aBsrhj",
        "colab_type": "code",
        "outputId": "2136e7c3-0a4a-4258-8aa9-b4de840aebc8",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 105
        }
      },
      "source": [
        "import random\n",
        "\n",
        "lst = [random.random() * 50 for _i in range(30)]\n",
        "print('Исходный массив\\n', lst)\n",
        "\n",
        "def merge(left, right):\n",
        "    result = []\n",
        "    i ,j = 0, 0\n",
        "    while i < len(left) and j < len(right):\n",
        "        if left[i] <= right[j]:\n",
        "            result.append(left[i])\n",
        "            i += 1\n",
        "        else:\n",
        "            result.append(right[j])\n",
        "            j += 1\n",
        "    result += left[i:]\n",
        "    result += right[j:]\n",
        "    return result\n",
        "\n",
        "\n",
        "def merge_sort(array):\n",
        "    if len(array) < 2:\n",
        "        return array\n",
        "    middle = len(array) // 2\n",
        "    left = merge_sort(array[:middle])\n",
        "    right = merge_sort(array[middle:])\n",
        "    return merge(left, right)\n",
        "\n",
        "\n",
        "print('Отсортированый масив\\n', merge_sort(lst))"
      ],
      "execution_count": 0,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "Исходный массив\n",
            " [15.146431693432671, 47.33254575956689, 24.627504990074783, 39.869875625701276, 2.1821924413015727, 32.73142338536517, 16.336910106843956, 30.119200288329097, 16.066430343592174, 33.18474110518716, 41.78471678070812, 2.266130583586251, 20.354689752846372, 8.453374895265647, 31.64181229824961, 41.588805906558456, 5.80180332303557, 39.52713803153251, 1.3393264060402033, 34.360376606582605, 40.753010715769975, 22.700225911503946, 22.580934241259275, 26.373438742373033, 42.98009219232561, 22.3588128425764, 10.951213270468962, 41.35813253937287, 17.224016016119414, 11.342775417858597]\n",
            "Отсортированый масив\n",
            " [1.3393264060402033, 2.1821924413015727, 2.266130583586251, 5.80180332303557, 8.453374895265647, 10.951213270468962, 11.342775417858597, 15.146431693432671, 16.066430343592174, 16.336910106843956, 17.224016016119414, 20.354689752846372, 22.3588128425764, 22.580934241259275, 22.700225911503946, 24.627504990074783, 26.373438742373033, 30.119200288329097, 31.64181229824961, 32.73142338536517, 33.18474110518716, 34.360376606582605, 39.52713803153251, 39.869875625701276, 40.753010715769975, 41.35813253937287, 41.588805906558456, 41.78471678070812, 42.98009219232561, 47.33254575956689]\n"
          ],
          "name": "stdout"
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "VgsF44R6tEVc",
        "colab_type": "text"
      },
      "source": [
        "3. Массив размером 2m + 1, где m – натуральное число, заполнен случайным образом. Найти в массиве медиану. \n",
        "Медианой называется элемент ряда, делящий его на две равные части: в одной находятся элементы, которые не меньше \n",
        "медианы, в другой – не больше ее."
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "NxoPrEN_tKWR",
        "colab_type": "code",
        "outputId": "2959a207-5c99-464f-bba3-6e2824a8b32d",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 68
        }
      },
      "source": [
        "import random\n",
        "lst = [random.randrange(0, 100, 1) for _i in range(15)]\n",
        "\n",
        "def gnome_sort(lst):\n",
        "    array = lst.copy()\n",
        "    def _gnome_rec(array, i=0, j=None):\n",
        "        if j is None:\n",
        "            j = len(array) - 1\n",
        "        if array[j] < array[i]:\n",
        "            array[i], array[j] = array[j], array[i]\n",
        "        if j - i > 1:\n",
        "            t = (j - i + 1) // 3\n",
        "            _gnome_rec(array, i, j - t)\n",
        "            _gnome_rec(array, i + t, j)\n",
        "            _gnome_rec(array, i, j - t)\n",
        "        return array\n",
        "\n",
        "    return _gnome_rec(array, 0, len(array) - 1)\n",
        "\n",
        "def median(ns_array):\n",
        "    lenght = len(ns_array)\n",
        "    if lenght % 2 == 0:\n",
        "        return 'Нет медианы для четного массива'\n",
        "    s_array = gnome_sort(ns_array)\n",
        "    middle = (lenght - 1) // 2\n",
        "\n",
        "    index = ns_array.index(s_array[middle])\n",
        "    return f'median is index: {index} value: {s_array[middle]}'\n",
        "\n",
        "print(median(lst))\n",
        "print('origin list', lst)\n",
        "print('sorted list', gnome_sort(lst))"
      ],
      "execution_count": 1,
      "outputs": [
        {
          "output_type": "stream",
          "text": [
            "median is index: 12 value: 48\n",
            "origin list [0, 34, 47, 69, 87, 21, 41, 22, 54, 82, 94, 84, 48, 48, 65]\n",
            "sorted list [0, 21, 22, 34, 41, 47, 48, 48, 54, 65, 69, 82, 84, 87, 94]\n"
          ],
          "name": "stdout"
        }
      ]
    }
  ]
}