7. CS50 на русском: Лекция #7 [Гарвард, Основы программирования, осень 2015 год]
Доп. материалы и задачи к лекции — javarush.ru/s/level_3
Весь курс CS50 — javarush.ru/s/course_cs50
Гарвардский курс по основам программирования CS50, седьмая лекция: поиск Майка Смита продолжается!
Помните разорванный телефонный справочник из самой первой лекции CS50? В седьмой лекции он возвращается! Возвращается, чтобы сделать фразу «эффективность алгоритмов» не пустым звуком, а пояснить на примере. Все программисты думают о скорости работы программы и о том, сколько памяти она при этом «съест». На учебных задачках это не так очевидно, но когда мы работаем с большими массивами данных (как почти везде в «Энтерпрайзе»), эти вопросы становятся первоочередными.
Представьте себе, что данные в телефонном справочнике не отсортированы по алфавиту. Представляете, сколько времени у нас бы ушло на то, чтобы его там найти? С учётом того, что в телефонном справочнике нет человека с таким именем, пришлось бы перебирать все строчки подряд — и всё впустую! Но есть выход: данные всегда можно отсортировать.
И в седьмой лекции Дэвид Малан расскажет об известных алгоритмах сортировки — пузырьковой, вставки и выбора. Эффективны ли они? Подсказка: не слишком, в чем это проявляется — узнаете из лекции. Но почему они в таком случае знамениты и зачем их изучать? Дело в том, что они довольно просты в реализации, а на их основе можно создавать уже более продвинутые алгоритмы сортировки.
А еще, вы услышите, как звучат алгоритмы сортировки. Незабываемая музыка программирования уже доступна в переводе седьмой лекции.