Язык программирования Python является одним из самых простых в освоении и популярных языков программирования. Целью курса является изучение основных конструкций языка Python, которые пригодятся при решении широкого круга задач – от анализа данных до разработки новых программных продуктов. В результате освоения курса слушатели научатся обрабатывать и хранить числа, тексты и их наборы, освоят стандартную библиотеку языка Python и смогут автоматизировать задачи по сбору и обработке данных. Курс дает необходимую базу для освоения более специализированных областей применения языка Python, таких как машинное обучение, статистическая обработка данных, визуализация данных и многих других. Также слушатели познакомятся с основами различных парадигм программирования: процедурным, функциональным и объектно-ориентированным программированием. Для качественного освоения курса достаточно знания математики на уровне средней школы, опыта программирования не требуется. В курсе предлагается большое количество задач по программированию, расположенных по нарастанию сложности, что позволяет закреплять на практике изучаемый материал. К каждому занятию прилагается полный конспект, это делает изучение курса удобнее. Курс проводился в оффлайн варианте для студентов бакалавриата факультета компьютерных наук НИУ ВШЭ.
Сортировка подсчетом
Loading...
Del curso dictado por National Research University Higher School of Economics
Основы программирования на Python
591 calificaciones
National Research University Higher School of Economics
591 calificaciones
De la lección
Сортировка
В этом модуле вы познакомитесь с применением сортировки данных, которая облегчает решение многих задач и широко используется на практике.
Conoce a los instructores
Густокашин Михаил СергеевичПриглашенный преподаватель
Департамент больших данных и информационного поиска, Факультет компьютерных наук
[МУЗЫКА] [МУЗЫКА]
Сейчас мы посмотрим не на новые конструкции языка Python,
а на некоторые, по сути, алгоритмы и приемы работы с данными.
Во многих задачах необходимо не просто отсортировать данные, а запомнить,
на каком месте они стояли в исходной последовательности.
Давайте, собственно, и решим такую задачу, а именно: сказать, на каких
позициях в исходной последовательности стояли элементы, так чтобы,
если мы их передставим так, как у нас будет вывод, они оказались упорядочены.
То есть отсортировать числа с их номерами.
Что мы для этого сделаем?
Считаем сначала список чисел.
[ЗВУК] Это мы делаем уже известным образом.
И теперь нам нужно каждому числу добавить его номер.
Для этого мы сделаем кортежи, то есть создадим новый список,
вначале он будет пустой, пройдемся по
всем элементам нашего списка и
добавим в новый список кортеж,
состоящий из элемента нашего списка и его номера.
Как узнать его номер?
Давайте переделаем всё, теперь будем перебирать номера.
Кажется, так будет проще.
Кстати, смотрите, я назвал список l — это очень плохо,
потому что l похожа на единичку.
Давайте назовем его как-нибудь по-другому.
Значит, l — плохое название переменной,
а L нельзя называть, потому что мы называем переменные большими буквами.
Поэтому переменную L мы не используем, и переменную I («ай»), «И» латинская,
большую мы тоже стараемся не использовать, потому что все они путаются между собой.
Итак, добавить в список.
Сначала сам элемент.
Почему?
Потому что у нас будет сортировка, мы хотели бы,
чтобы они сортировались по значению.
Значит, это у нас будет myList, исходный список, i-тый по счету элемент,
и, собственно, число i — какой он там у нас был по счету.
Теперь мы можем посортировать наш новый список, уже состоящий из кортежей.
Давайте для начала просто напечатаем его, а потом сделаем все красиво.
Итак, нам нужно вводить.
Вот они, наши числа.
Значит, что у нас напечаталось?
Во-первых, это список кортежей — в каждом
кортеже у нас сначала стоит число, какое было оно в списке,
а затем его позиция при нумерации с нуля в исходном списке.
И если нам нужно распечатать только позиции, мы можем,
опять же, это сделать очень похожим способом,
перебрав все элементы уже.
Перебрав все элементы нового списка с кортежей и
напечатав только их
первые индексы с кортежа, то есть как раз номера.
Что теперь у нас произойдет?
Вот, у нас напечаталось, что самый маленький
элемент стоял на первом месте в списке — да, это похоже на правду,
следующий по величине — на нулевом месте, затем на втором и на третьем.
Вот, такое сопоставление числа и его номера в исходной последовательности
пригодится вам при решении задач, и по жизни это тоже бывает нужно.
Теперь посмотрим на еще одну довольно специфическую задачу,
а именно — посортировать данные, которые могут принимать,
каждый элемент может принимать очень небольшое количество значений.
Например, оценки в «Вышке» бывают от нуля то десяти.
И человек получил какой-то список оценок, мы хотим их упорядочить.
Понятное дело, что мы можем просто взять и воспользоваться сортировкой.
Но иногда, и не только для задач сортировки, применим классный метод,
который называется «сортировка подсчетом».
А именно, мы будем считать, сколько и каких оценок человек получил.
Что мы для этого сделаем?
Сначала мы создадим список,
состоящий из 11 нулей — у нас числа от нуля до десяти, всего их 11 штук.
Как это делается — нолик в квадратных скобочках умножаем на 11.
Получаем список из 11 нулей.
То есть сначала у человека ноль оценок каждого типа.
Индекс в этом списке будет задавать оценку,
а значение будет обозначать количество таких оценок.
Что делаем?
Проходимся по всем полученным оценкам.
Мы теперь знаем, какая очередная
обрабатываемая оценка, и элемент с таким индексом мы
можем увеличить на единичку — человек получил на одну больше такую оценку.
Как теперь вывести отсортированные данные?
Это делается достаточно легко.
Мы перебираем всевозможные оценки, то есть всевозможные значения,
которые могут быть, и выводим это значение столько раз...
Как строку давайте, у нас там число же,
а мы будем умножением строк пользоваться, я надеюсь, вы это еще помните.
Причем с пробелом, чтобы все красиво было.
На самом деле, можно было сделать два вложенных цикла
и просто число выводить несколько раз, но мы же можем умножать строки!
Значит, оценку умножаем на количество оценок.
[ЗВУК] В
конце ставим пробел, чтобы у нас ничего не слиплось.
Давайте попробуем!
Итак, вводить в таком решении можно числа строго числа от
нуля до десяти включительно.
Если мы введем что-то другое, все сломается,
потому что мы выйдем за пределы нашего списка.
Итак, пусть человек не очень хорошо учился, потом взялся за ум,
но потом опять стал не очень хорошо учиться.
Всё.
Ну вот, оно вывело примерно то,
что нужно, за исключением того, что у нас какая-то беда с пробелами.
Ну ладно.
Можно разобраться на отладке, можно сделать рабоче-крестьянским методом,
как это делается на других языках программирования
— перебрать все числа [ЗВУК]
до количества полученных оценок
и печатать оценку, индекс в исходном массиве.
И больше ничего не делать.
В конце печатать пробел, чтобы они не слипались и печатались все в одну строку.
Вот так это выглядело бы на других языках, ну а как у нас было раньше — там нужно
просто разобраться, почему там лишние пробелы появляются, и исправить это.
Итак, вводим какие-нибудь оценки, давайте поменьше уже.
Вот, теперь они красиво напечатались.
И вот эта штука называется «сортировка подсчетом».
Она используется не только для сортировки, для многих других задач.
И, наверное, когда вы увидите какую-то задачу,
где очень небольшое количество возможных значений, вспомните о таком методе.
Ну, например, посчитать количество букв,
которые встречаются в тексте или еще что-нибудь в этом духе.
И еще одна вещь об использовании сортировок.
В принципе сортировка может быть применена для поиска минимума
или максимума последовательности или более сложной задачи второго минимума,
но делать этого не стоит.
Давайте я покажу, что, во-первых, так можно сделать, а потом расскажу,
почему так не нужно делать.
Итак, например, мы хотим узнать минимум последовательности.
Что мы делаем?
Упорядочиваем, берем нулевой элемент из нее.
Это будет, естественно, минимальный элемент.
Давайте посмотрим, что так можно делать.
Ну да, вот она единичка, а если бы мы хотели максимум,
мы бы там поставили –1, последний элемент нашего списка.
Почему так делать не нужно?
Потому что сортировка — это достаточно медленная операция,
она работает за n * log(n) действий, где n — это длина сортируемого списка.
В то же время просто пройти по списку, сделать линейный поиск мы можем
за n операций, то есть просто посмотрев один раз на каждый элемент.
Это намного лучше, и когда вы, например, придете на собеседование и вас спросят
«а как вы будете искать минимум?», то если вы скажете «я посортирую,
возьму нулевой элемент», вряд ли те, кто проводят интервью, это оценят.
Но в Python, тем не менее, все сделано для ленивых людей,
и в частности функции поиска минимума и максимума есть.
То есть мы можем воспользоваться функцией минимума,
которая получает на вход список и сообщает его минимальный элемент.
Все, отлично, работает.
Аналогично, есть функция поиска максимума, в списке называется max.
Тем не менее, если у вас какая-то более сложная задача, например,
второй по величине элемент нужно найти, то стандартной функции для этого нет,
и пользоваться или не пользоваться сортировкой уже вопрос достаточно тонкий.
Почему? Потому что понятное дело, когда вы ищете
второй минимум, вы тоже можете это сделать за один проход по массиву,
просто воспользовавшись циклом for.
Если же вы воспользуетесь сортировкой, то вы потратите n * log(n) действий,
что несколько больше, но вся ирония заключается в том,
что в Python стандартные функции работают намного быстрее,
чем что бы то ни было, написанное непосредственно на Python.
Поэтому может оказаться так, что вы, конечно, написали очень эффективный
линейный алгоритм поиска, но сортировка в реальности будет работать лучше.
Поэтому вопрос это сложный, но знать о том,
что необязательно использовать сортировку для таких вещей, конечно же, нужно.
[МУЗЫКА]
[МУЗЫКА]
Explora nuestro catálogo
Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.
Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.
© 2018 Coursera Inc. Todos los derechos reservados.
