WEB-проекты

Система бронирования.

Предметная область может быть абсолютно любой. Карта с недвижимостью и арендой/покупкой. Системы бронирования билетов на самолет, кино. Бронирование столиков в ресторане. Запись куда-либо на определенное время. В общем, полет фантазии тут безграничен, и задача встречается часто и в реальной жизни.

Социальная сеть.

Хоть некоторые и говорят: «Только не делайте очередную социальную сеть». А почему бы и нет ? Это вполне хорошая практика. Главное подходить к этому разумно и не представлять после каждой строчки написанного кода дрожащего Цукерберга) Если вас интересует бэкенд, можете легко найти готовый шаблон чтобы не отвлекаться на это и реализовать базовый функционал. Заодно попрактикуетесь в проектировании базы данных. Развивать функционал тут можно бесконечно долго, но это уже не будет оправдано, банально не хватит ресурсов. Ни технических ни финансовых. Не говоря о том, что пытаясь вывести такой проект в массы нужно с первых дней особое внимание уделять безопасности, что для пет-проекта не так принципиально.

Онлайн-магазин.

Есть масса готовых движков для создания интернет-магазинов, однако и по сей день многие компании пишут функционал с нуля. Это очень хороший для практики проект, особенно если вы попытаетесь добавить в проект различные платежные инструменты.

Поисковик.

Собственно да, поисковая система а-ля Google или Yahoo. На этом проекте можно сполна и до тошноты наиграться в классические алгоритмы, чего на других проектах не всегда можно увидеть. После того как за несколько часов мы запилим более крутой дизайн чем у Ларри Пейджа, начинается самое интересное. Итак, у нас есть титульник поисковика, есть гараж, он даже чуть больше чем был у Google в начале пути, нужно лишь выкатить из него дедов москвич.

Для начала нам нужен поисковый робот который будет обходить сайты, причем заходя не только на титульную страницу, но и обходить вглубь. И вот одна только эта задача уже требует принять массу решений, как обходить, какие данные вытаскивать, как определять веса и значимости страниц, как определять что мы тут уже были по другой ссылке. Как определять что страница с описанием конкретного автомобиля при поиске важнее чем страница с общим каталогом автомобилей где также описана эта модель. Нужно подсчитывать внешние ссылки, входящие ссылки, строить деревья и как-то ранжировать сайты и между собой.

В общем, лучше всего здесь будет выбрать какую-то определенную категорию, например авто-тематики и сделать поисковик исключительно тематическим и по заранее определенной группе сайтов. А то у вас просто не хватит ресурсов и вычислительных мощностей чтобы обойти все сайты интернета и взять с них какую-то информацию. Я даже не говорю о том что это ещё надо как-то ранжировать и регулярно переобходить и перестраивать эти самые деревья и связи. В конце концов в Google работает около 90 тысяч человек и в их распоряжении более миллиона серверов, нужно реально оценивать свои возможности.

Чат-бот / бот в мессенджерах.

А также боты для социальных сетей. Вы сталкивались с ними везде и они сейчас довольно популярны. Функционал может быть любой, от регистрации где-то в чем-то, до консультаций с переводом управления на человека. В общем, вещь на сегодня довольно востребованная.

Спам фильтр.

Ох уж этот спам, он повсюду, начиная от кучи мусора в вашем почтовом ящике и заканчивая сообщениями в социальных сетях. Этот проект может стать частью некоторых других описанных в этом же разделе. Либо как самостоятельная единица. Нужно определиться с тем, что такое спам, как именно отличить нормальное письмо от спама. На самом деле, тема не такая и простая и даже самые крутые спам-фильтры время от времени ошибаются. Можете реализовать простое приложение которое получает письма с какого-то почтового ящика и уже на этих письмах тренироваться.

Движок форума.

Форумы были невероятно популярны до появления социальных сетей. Собственно они людям и заменяли эти самые социальные сети и люди там неплохо общались. Из популярных на тот момент движков могу вспомнить флагманский vBulletin, чуть более простой Invision Power Board и бесплатный phpBB. Если взять статистику по миллиону самых популярных сайтов, но последние лет 10-12 форумы стабильно теряли своию аудиторию. Тем не менее, форумы живее всех живых, а при попытке нагуглить что-то по программированию, в топе наверняка окажутся именно те самые форумы.

Собственно, сложность задачки лежит на том уровне до которого вы решите копать. Минимальный функционал форума это возможность создавать темы, заходить в эти темы, отвечать на определенные сообщения с цитироваинем или без. Как минимум должно быть 2 пользовательские группы, админы и пользователи, можете добавить ещё модераторов или супер-меодераторов. Если ранее делали свой спам-фильтр, то он тут будет очень даже к месту. Только не пытайтесь сделать сразу все возможные кнопки и фишки форумов. Не забывайте что ваш проект должен иметь законченный вид. И всё что вы там «визуально заявите» должно работать.

Движок блога

Вы можете попробовать написать свой простенький движок блога, по типу WordPress или Joomla. На каком-то базовом уровне проект не особо сложный, но здесь также можно копать очень глубоко. Начиная от создания простых записей и возможности регистрации авторизации. И двигаться в сторону прав доступа, возможности загрузки файлов, созданию плагинов, системы загрузки тем и шаблонов.

Свой инстаграмм.

Автопостинг в социальных сетях

FTP-клиент

Система контент менеджента (CMS)

В современном мире почти не осталось сайтов которые редактируются путем непосредственного изменения кода страниц. Этим управляет CMS. Система управления контентом — это система, позволяющая любому количеству людей управлять различным контентом на сайте, обычно это статьи, макет, реклама и т.д. В принципе, по своей сути это не особо отличается от движка блога и даже википедия в качестве примеров выдает wordpress и joomla. Но CMS это не только блоги, это может быть вообще что угодно. Это именно система управления контентом, а уж в какой области эту систему реализовывать, решать вам.

Доска объявлений

Все вы конечно же знаете Авито и Юлу, помимо них есть и множество других. Современные доски объявлений продвинулись довольно далеко от того на что они были похожи в середине нулевых. Но вот тот базовый функционал простых объявления разложенных по разным категориям вам вполне доступен для реализации на старте. А при особом желании, имея базовый функционал уже можно замахнуться и на грандов.

Собственная капча

Вряд ли эта капча будет интересна ещё кому-то кроме вас, всё же на сегодняшний день популярно мучать пользователей рекапчей от гугла. Но как практика вполне сойдет, тем более что реализовывается это довольно просто.

Rss ридер

Проект исключительно попрактиковаться в плане парсинга данных и представлении этих данных в каком-то более удобном виде. RSS-ленты сегодня уже мало где применяются.

Почта

Чат

Игры

1. Крестики-нолики.

2. Тетрис

3. Змейка

4. Морской бой

5. Клон Марио

6. Тамагочи

7. Флоппи берд

8. Ангри берд

Arduino/Raspberry

Умный дом

Сообщение 50+ идей Pet-проектов для программиста часть 2 появились сначала на Blogee.

50+ идей Pet-проектов для резюме и прокачки навыков

Всем привет ! Как известно, научиться чему-либо без практики невозможно и программирование не исключение. Но что именно реализовывать и какие проекты брать ? На самом деле довольно популярный вопрос и единого мнения на этот счет нет. Одни говорят — «Только не создавайте очередную социальную сеть/движок блога или приложение ToDo» или «Создайте какое-то приложение которое нужно именно вам в данный момент времени.» Другие им отвечают — «А какая разница что делать ? Если создавая очередной facebook вы прокачаете нужные вам скиллы, то это именно то что вам и нужно делать !».

Что и до какого состояния доводить.

Самое главное, ваше приложение должно иметь какой-то законченный вид, это очень важно. Приложение должно решать какую-то пусть небольшую проблему и что-то уметь делать. На этом этапе не стоит особо переживать за качество кода. В конце концов, это ведь ваше начало пути как разработчика. Второе, начав реализовывать свой «facebook» не пытайтесь объять необъятное. Если в начале всё кажется вполне простым, «Ну что там, регистрация, авторизация, несколько полей в базе с личной информацией, аватарка». То впоследствии всегда начинают всплывать определенные нюансы и можно уйти в долгострой. Визуально вы может даже получите точную копию «фейсбука», а на деле абсолютно нерабочее приложение. При этом затратите месяцы, не забывайте что в фейсбуке работает более 40 тысяч человек, а вы всего один. Делайте самую простую, самую малую часть, но чтобы всё работало и постепенно можно обрастать функционалом. Очень важно видеть свой прогресс.

Pet-проекты

Перелопатив множество сайтов, ютуб-каналов в российском и зарубежном сегменте интернета, собрал небольшой список возможных проектов. Если у вас есть какие-то идеи что можно реализовать, можете написать в комментариях, добавлю в общий список.

Приложения:

Калькулятор.

Здесь всё понятно. Наверно каждый делал свой калькулятор. Считаете что это слишком просто ? Попробуйте добавить сюда функции инженерного калькулятора. Добавьте логарифмы, факториал, перевод в системы счисления, округления. Попутно решите вопрос как и в каких типах хранить данные, как сделать проверку чтобы в запись дроби нельзя было ввести более 1 точки и прочее. Возможно наткнетесь на случаи когда сложив два числа с плавающей точкой результат вас неприятно удивит. В общем мелкие, не совсем очевидные сначала вещи.

Текстовый редактор.

Здесь вы можете взять за основу любой текстовый редактор, хотя бы стандартный блокнот. Что здесь именно делать ? Набор текста, сохранение, открытие, создание нового файла. Поиск по тексту. Поиск снизу, сверху, с учетом и без учета регистра. Особым шиком будет написать редактор где, например, будет подсвечиваться синтаксис. В общем возьмите любой текстовый редактор и подсмотрите какой функционал вы бы хотели реализовать у себя.

Системы счисления.

А также перевод между системами. На самом деле, это можно реализовать и внутри обычного калькулятора. Но и в качестве отдельного приложения вполне имеет право на жизнь. Особенно если помимо двоичной, восьмеричной и шестнадцатеричной системы счисления вы добавите ещё и троичную, которая в свою очередь может быть симметричной или несимметричной. А можете и вовсе добавить произвольный выбор системы счисления. Только не используйте готовые библиотеки для перевода между системами.

Шифраторы с помощью различных алгоритмов.

А вот это вообще довольно интересная вещь. Возможностей зашифровать сообщение довольно много, начиная от примитивного шифра Цезаря которая шифруемые символы сдвигаются по алфавиту на какое-то постоянное значение. И до вполне серьезных алгоритмов шифрования. Тема на самом деле довольно глубокая и копать в ней можно бесконечно далеко. Можно также реализовать свой примитивный мессенджер используя данные алгоритмы.

Почтовый клиент.

Попробуйте сделать свой почтовый клиент. Прием почты, отправка, небольшой редактор для написания текста письма. Особый шик — возможность форматировать текст и отправлять его со всем форматированием. Возможность добавлять вложения.

Сканер портов.

Довольно интересный проект. Сканировать все порты на компьютере, определять какие на них висят приложения, номер порта, статус.

Каталогизатор.

Тут на самом деле можно расшоркаться в любую сторону и на столько глубоко, на сколько будет желание. Что именно каталогизировать ? Да что угодно, можете взять музыку, фильмы. Сделать возможность скачивания обложек, получение данных по длине проигрывания файла. Год выпуска произведения, имя артиста или режиссера, акторов, получение рейтинга в случае если это фильм. Где всё это брать ? Например на IMDB, в случае с музыкой думаю тоже есть несколько вариантов. Далее можно создать функции поиска, сортировки, выборки нужных данных на основе каких-то запросов. Заодно прокачаете свои навыки в работе с базами данных.

Банковское приложение.

Думаю многие из вас знают как они выглядят. На мой взгляд, тут можно пойти двумя путями.

Вариант 1: пишем свое небольшое веб приложение, а-ля банк Bank of Petroff. Пробуем спроектировать под это дело базу данных, продумываем как и какие данные нужно хранить. Можно реализовать двухфакторную аутентификацию, разлог через 10-15 минут неактивности и прочее. Далее можно написать свое десктопное или мобильное приложение, которое будет подключаться к вашему веб-приложения через API или ещё каким образом и после аутентификации отображать определенную информацию.

Вариант 2: на сегодня довольна популярна тема с фондовым рынком и акциями. Вы можете написать приложение, веб, десктоп или мобильное. Суть которого заключается в том, что у пользователя создается виртуальный счет, но играет он по реальным котировкам. Это будет довольно таки серьезное приложение. Где брать данные о котировках ? Можно нагуглить несколько сервисов где данные о ценах можно получать через API. Любите крипту ? Сделайте тоже самое с учебным счетом но с криптой на API от coinmarketcap.

Галерея изображений.

Также может быть как desktop, так и мобильное приложение или веб-приложение. Можно сделать какой-нибудь сильно облегченный аналогв ACDSee или irfanview. Просмотр изображений, данные об изображении, изменение имени файла и удаление прямо из приложения. Можно сделать галерею под Android, если она при этом не будет тормозить, будет вообще замечательно.

To-Do лист.

Список каких-то дел или задач. Особо тут даже добавить нечего.

Веб-браузер.

Здесь есть несколько вариантов для реализации:

Во-первых, во многих IDE-шках есть свой готовый веб-браузер который одной командой в коде можно заставить перейти на какую-то страницу. Далее читаем документацию по этой библиотеке/классам и постепенно наращиваем какой-то функционал. Просмотр кода, поиск по странице, сохранение страницы, закладки, да много чего.

Второй вариант, вы можете взять за основу движок хрома или файрфокса и далее аналогично допиливать что-то свое. По скольку вы используете их готовый движок, самое сложное уже реализовано, это касается и первого варианта.

Третий вариант, можно попробовать сделать классический текстовый браузер, многие из вас их в глаза не видели, но всё начиналось именно с них. Просто парсите страницу, и выдаете информацию в каком-то упорядоченном виде, в каком, решать вам. Здесь вы сможете отлично попрактиковаться с веб-запросами. Намного лучше чем в первых двух вариантах.

Четвертый вариант, реализовывать всё самому, на самом деле это утопия. Опять же, в качестве учебного проекта вам это надоест уже на этапе парсинга HTML кода. Я даже не говорю по CSS/JS и мультимедиа и про то что это ещё надо как-то выводить, причем корректно. Как пишут при выполнении опасных трюков, «Не пытайтесь повторить это дома». Даже Microsoft годами безуспешно мучился с IE, про который говорили что он нужен только для скачивания другого браузера. А вот первые три варианта вам вполне по силам.

Файловый проводник.

Аналог стандартного проводника Windows или что-то в стиле классического Far manager. С полным набором функций для работы с папками и файлами. Создание, удаление, переименование, копирование. Примерный функционал и меню можете подглядеть у любого файлового менеджера. Впоследствии, на базе этого проекта можно сделать ещё и архиватор.

Архиватор

Архиватор можно попробовать сделать уже на базе своего файлового менеджера. Так получится вдвойне интересно и у вас уже будет готовый интерфейс. Для начала хватит двух базовых функций, запаковка и распаковка в zip формат. Либо объединить несколько файлов в один архив вообще без сжатия. При желании сделать что-то более крутое появляется огромное поле для маневра. Вы можете добавить возможность запаролить архив, зашифровать имена файлов, разбить архив на тома. Можете изучить различные алгоритмы сжатия данных, а их не так уж и мало и добавить поддержку других форматов. Можете реализовать возможность самораспаковывающихся архивов. Ну и прямо самая вишенка на торте, возможно вы придумаете какой-то свой алгоритм сжатия данных. Пусть он будет самый медленный и не оптимальный, вообще не имеет значения.

Клавиатурный тренажер.

Идея приложения заключается в том, чтобы научить человека быстрому набору/вводу данных с клавиатуры. Человек нажимает какую-то клавишу, вы это перехватываете и как-то обрабатываете. Или наоборот, вы поочередно отображаете какие-то символы, а пользователь должен их вводить. Постепенно повышаете сложность добавляете другие буквы/цифры. В нулевых годах в этой области была популярна программа «Соло на клавиатуре», благодаря которой я довольно быстро освоил 10 пальцевый набор текста. А через некоторое время и вовсе начал печатать не глядя на клавиатуру. Кто знает, может и ваше приложение кому-то очень сильно поможет. Как минимум можете протестировать его на своих близких, кто печатает одним пальцем пристально рассматривая клавиатуру.

Календарь.

Здесь тоже на первый взгляд всё понятно и особых сложностей нет. Но помимо календаря, на его базе можно сделать записную книжку с уведомлениями куда угодно. Через месяц у вас намечено что-то не особо нужное, но проигнорировать это будет не вежливо ? Добавьте уведомление о нём за пару дней до события с отправкой по разным каналам.

Учет калорий и физической активности.

Простенькое фитнес приложение. Заносите данные по различным видам физической активности, калорийности продуктов. Пользователь вводит данные, например, творог 200 грамм 9% жирности. А программа сразу подставляет данные сколько это калорий. Можно сделать индикатор на сколько этот продукт полезен. Можно сделать уведомление сколько человек ещё можно съесть сегодня. Само собой человек при регистрации должен как минимум указать свой вес и цель. Можно выдавать в конце дня или на следующее утро отчет.

Например, «За вчерашний день у вас недобор {x} грамм белка».  Или «За последние {x} суток вы не потребляли сложные углеводы». Также дать возможность пользователю вводить активности и сколько калорий он за это время сжег. Можете даже сделать какую-то красивую инфографику или анимацию. Что-то в духе сегодня вы потратили на 90 калорий больше чем потребили и потеряли 10 грамм жира. Вроде смешно, но в плане психологии всегда приятно видеть положительную динамику. А если удастся через API получать данные с фитнес-браслетов, то приложение и вовсе может перейти в разряд коммерческих.

Мессенджер.

На рубеже середины/начала нулевых была огромная масса различных мессенджеров, существенная часть которых крутилась вокруг icq который тогда ещё принадлежал компании AOL. Вы можете сделать простенький мессенджер для обмена сообщениями между двумя приложениями. В плане практики вещь довольно интересная, можно натаскаться в плане работы с сокетами, асинхронными методами, исключениями, запросами. Как реализовывать ? Можно упростить и задавать IP адрес собеседника напрямую. Можно сделать веб-сервис который будет транзитом в передаче сообщений. А можно сделать чтобы при входе в сеть вашего мессенджера вы получали адреса всех своих контактов и далее вели переписку напрямую. По сути используя сервер только для регистрации (вот кстати ещё одна вещь которую можно реализовать) и/или получения IP-адресов по их номером/псевдонимам в сети. Далее можете усложнить проект и добавив какой-то вид шифрования, начиная от шифра Цезаря и вплоть до самых стойких современных алгоритмов.

Эквалайзер.

Визуализация звукового сигнала. Проект не на столько легкий как может показаться, однако тема раньше была очень популярна и информации должно быть много.

Агрегатор курсов криптовалют.

По сути, это тренировка работы с API. Ключ, а вместе с ним и все данные можно получить на CoinMarketCap.Что с этим делать ? Можете завести базу данных, с определенной переодичностью делать запросы, вести какую-то статистику. Возможно даже какое-то прогнозирование. А уж в плане инфографики и отчетов тут поле непаханное, а заодно  и с базами данных попрактикуетесь.

Сервис сокращения ссылок.

Довольно простой проект даже для новичка. Итак, на вход к нам приходит ссылка любой допустимой для веб-адреса длины. Мы независимо от её длины всегда выдаем что-то типо https://site.rr/dHr81Ja или https://site.rr/link.php?id=dHr81Ja. Второй случай на том же php новичку реализовать на порядок проще. Как пример, приходит ссылка, мы её хешируем, оставляем от хеша первые 7 символов, остальное вырезаем и выкидываем. Записываем в базу данных исходную ссылку и 7 символьный хеш. Далее вместо длинной ссылки выдаем пользователю ссылку вида https://site.rr/link.php?id=dHr81Ja. При клике по ней отрабатывает скрипт link.php который лезет в базу данных и забирает полную ссылку для записи у которой краткая ссылка равна dHr81Ja. Вот собственно и вся реализация. Делать можно на любом языке и в идеале выдавать в таком виде https://site.rr/dHr81Ja. В качестве усложнения задания, можно считать количество переходов или сохранять дату последнего перехода. Может ещё что-то придумаете.

Генератор QR кодов.

Опять же довольно простой проект. С чаем и печенками отвлекаясь на поглажку кота можно сделать за несколько часов. Есть готовые библиотеки которые генерируют QR / Bar коды при передаче строкой данных которые собственно и нужно закодировать. Чтобы хоть немного усложнить задачку, можно задать уровень коррекции ошибок. Опять же, всё это реализовано в готовых классах, нужно лишь реализовать передачу различных аргументов в зависимости от выбора пользователя. Всего есть 4 уровня коррекции. Можно также задать опцию выбора размера кода, можно добавить ненавистную дизайнерам фразу «поиграться с цветами». Можно добавить возможность пакетного создания Bar/Qr кодов, например считывая построчно текстовый файл. И сохранять готовые файлы в какую-то папку.

Аудио/Видео плеер.

Приложение такого плана можно реализовать где угодно, на любой платформе. Самое популярное, безусловно это в веб. На базовом уровне достаточно стандартных элементов проигрывания. Плей, пауза, стоп, вперед, назад и возможности загрузить какой-то список, например все аудиофайлы из папки. Или сделать возможность добавления файлов в плейлист. Главное чтобы условный аудиофайл в плейлисте был не один, это повысит уровень сложности самой программы. Вам нужно будет сопоставлять названия музыкальных композиций в соответствие с их адресами на сайте или компьютере. Также можно добавить функцию шаффл, когда плейлист перетряхивается в рандомном порядке. И добавить возможность создания, сохранения и загрузки плейлистов.

Антикапча.

Добро пожаловать в мир нейронных сетей. Капчу наверное ненавидят все, но в борьбе со спамом ничего принципиально нового не могут придуть годами. Вы можете попробовать написать простую нейронную сеть которая будет разгадывать какие-то определенные виды капчи. Вы можете написать свой вариант геренации капчи, это довольно простая задача если особо не заморачиваться с фильтрами и прочим. Ну и затем на своей капче можете натренировать нейронную сеть на её разгадывание. Можно также выводить веротяности уверенности в верном распознавании символов.

Определение модели компьютера и возможность апгрейда.

Можно по примеру open source программы Open Hardware Monitor или Aida собирать информацию о компьютере/комплектующих и выдавать общую информацию о системе. Далее на основе эти данных можно получать информацию из открытых источников о возможности апгрейда компьютера. Например, программа определяет что в компьютере установлен двухъядерный процессор Core2Duo E8200 на 775 сокете. При этом материнская плата базируется на чипсете G41 который поддерживает 4-х ядерные процессоры вплоть до Q9550. Или в системе установлено 4 Гб оперативной памяти, но в материнской плате есть ещё 2 свободных слота поддерживающих по 2 Гб памяти.

Где брать эту информацию ? Парсить сайты nix.ru, cpu-upgrade.com и другие. Само собой ручаться за эту информацию нельзя, о чем было бы неплохо указать в самой программе. В целом проект был бы интересен множеству людей желающий провести апгрейд, но не имеющих элементарных знаний. Программа позволила бы дать им хотя бы первичную оценочную информацию об этой возможности и даже указать примерную стоимость комплектующих. Добавьте сюда монетизацию ссылок на подходящие комплектующие и вот вам коммерческий продукт.

Личные доходы/расходы.

Как следует из названия, программа позволит вести учет доходов  и расходов. Можно выводить какие-то отчеты по расходам, средний расход за год, наибольшие траты по секторам и/или каким-то отдельным вещам. Например — «За этот год вы потратили 5% вашего бюджета на сигареты». Собственно, обычная простенькая бухгалтерия для личного пользования. Для облегчения ведения можно помогать пользователю вводить названия покупок, предлагая по первым введенным буквам ранее использованные варианты. Также автоматическое подстановка стоимости, если человек весь год покупает пакет за 5 рублей, зачем ему целый год вводить в поле 5 рублей. Пусть вводится на автомате, если пакет подорожает, пользователь сам впишет туда новую цену.

Калькулятор финансовой независимости.

А вот это уже довольно интересный проект. Как много вы можете придумать вариантов получения пассивного дохода ? На сколько его можно прогнозировать ? Допустим, человек в возрасте 25 лет решает что к 45 годам он хочет выйти на пассивный доход 30 тысяч рублей. Для этого надо во что-то инвестировать, что-то сдавать, что-то развивать, получать деньги с условной рекламы в ютуб. Какие-то показатели считаются элементарно, какие-то можно брать лишь оценочно на основе средних значений. Пример, человек регистрируется, указывает что никаких доходов кроме зарплаты у него нет. Но он каждый месяц покупает акции и облигации. Здесь данные вполне точные, мы знаем сумму получаемого купона по облигациям с горизонтам до десятка лет. Мы примерно знаем сумму по дивидендам на акции. Пусть она и задается в процентах, но зачастую это фиксированная сумма.

Так вот, допустим человек каждый квартал покупает по 2 акции AT&T и по 2 акции Coca Cola. Первые раз в квартал платят 52 цента на акцию, вторые 42 цента на акцию. Итого ежеквартальных доход 1.88$ (налоги пока не считаем) или 45 рублей в месяц. Но в следующем квартале человек купит ещё по 2 акции и на следующий квартал его пассивный доход составит уже 3.76$ или 1.25$ в месяц или ~90 рублей. Так вот, программа может рассчитывать через какое время наш пассивный доход может достичь нужной нам цифры. Сюда же можно добавить реинвестирования прибыли в покупку новых акций. Помимо акций могут быть другие источники дохода, грубо говоря человек может добавить источник — сдача квартиры + 10к руб в месяц. В общем много расписывать не буду, думаю суть вы уловили.

Сообщение  50+ идей Pet-проектов для программиста часть 1 появились сначала на Blogee.

Сегодня мы разберем пожалуй самый популярный алгоритм сортировки. Алгоритм получил свое название благодаря тому, что в большинстве случаев это действительно наиболее быстрый способ сортировки данных. Алгоритм изначально встроен в виде функции/метода во множество языков программирования. Возникает логичный вопрос, если быстрая сортировка на столько хорошо, зачем нужны остальные ? На самом деле здесь не все так просто как может показаться на первый взгляд. Давайте разбираться.

Не будем лить воду и давайте сразу перейдем к массиву данных на котором мы будем разбирать алгоритм:

4 6 9 7 8 3 1 5 2

Алгоритм быстрой сортировки базируется на двух ключевых вещах, во-первых, рекурсия. Кто вдруг не знает что такое рекурсия, это функция которая вызывает саму себя определенное количество раз. Во-вторых, на выборе опорного элемента и вот от выбора этого самого опорного элемента очень сильно зависит быстродействие алгоритма. В худших случаях алгоритм может работать не особо быстрее пузырьковой сортировки. Об этом мы поговорим дальше.

Так вот, у нас есть массив и нам нужно его отсортировать. На первом шаге нам нужно выбрать какой-то из элементов массива опорным. Какой ? В первых версиях алгоритма в качестве опорного выбирался самый первый элемент массива. Но если наш массив уже отсортирован, то вы как раз и получите наихудший по времени вариант работы алгоритма быстрой сортировки. Более оптимальным вариантом считается выбор элемента из середины последовательности или вообще рандомный элемент. Идеальным вариантом является выбор медианного элемента, однако такой подход на практике не используется потому что это слишком трудоемкая задача которая съест всю выгоду от применения быстрой сортировки.

Мы знаем что наш массив не отсортирован, поэтому давайте пойдем по классическому варианту и выберем опорным элементом первый — цифру 4.

Теперь мы берем поочередно все элементы массива и сравниваем их с нашим опорным (четверкой), если элемент меньше, он уходит влево, если больше, уходит вправо.

Первый элемент(после того, который взят опорным) 6, он больше опорного элемента 4, кидаем его вправо. 9 больше и тоже вправо. 7 больше, вправо, 8 вправо, 3 и 1 меньше и уходят влево, 5 вправо, 2 влево. Получаем такую картину:

3 1 2 4 6 9 7 8 5

Элемент (цифра) 4 в нашей последовательности встала на свое конечное место. Теперь мы имеем 2 последовательности справа и слева от опорного элемента. Далее необходимо взять каждую из частей и проделать точно такие же манипуляции. В программном коде на этом моменте функция будет рекурсивно вызывать саму себя. Но с кодом мы разберемся чуть позже, смотрим дальше. Наши последовательности:

3 1 2 и 6 9 7 8 5

Теперь в каждой из них снова выбираем свой опорный элемент. Как вы помните, в качестве опорного мы берем тот что стоит первым:

3 1 2 и 6 9 7 8 5

И сравниваем каждую из последовательностей со своим опорным элементом. В первом случае оба элемента меньше опорного и становятся слева от него:

1 2 3

В последовательности 6 9 7 8 5 после сравнения с опорным получаем:

9 7 8 6 5

Мы только что закончили «вторую разбивку» нашей последовательности, надеюсь вы ещё не запутались, ниже я прикреплю всё единой схемой чтобы никто ничего не упустил. Давайте посмотрим что мы имеем сейчас. Опорные элементы с прошлой итерации опять же отсортировались далее в процессе не участвуют, сейчас мы имеем 4 подмассива данных:

1 2 и пустой и 9 7 8 и 5

Самое время сказать несколько слов про рекурсию. Её основная сложность или если хотите проблема, это не уйти в вечный цикл. Как было сказано выше, алгоритм быстрой сортировки основан на рекурсии, каждая разбивка это подмассива на более мелкие подмассивы это рекурсивный вызов функции. Но в какой-то момент нам нужно остановиться и завершить её. Так вот любая рекурсивная функция состоит из двух частей, первая часть называется базовым случаем, это условие когда нужно остановиться. В алгоритме быстрой сортировки базовый случай это когда подмассив состоит из 1 элемента или вообще их не имеет. Такие массивы не имеет смысла дальше сортировать и нужно просто возвращать данные. Вторая часть рекурсивной функции описывает рекурсивный случай, когда функция снова должна вызывать саму себя пока не доберется до базового случая. Давайте посмотрим на примере наших 4 подмассивов:

1 2 — выбираем опорным первый элемент и продолжаем сортировать, это рекурсивный случай

пустой (справа от тройки ничего не было) — а тут нам попросту нечего сортировать, это базовый случай, закончили

9 7 8 — выбираем опорным первый элемент и продолжаем сортировать, это рекурсивный случай

5 — один элемент сортировать не имеет смысла, это базовый случай, закончили

На очередной итерации рекурсивной функции, в которую попадают подмассивы не достигшие базового случая, мы получаем снова 4 подмассива:

пустой (слева от единицы ничего не было) — базовый случай, закончили

2 — базовый случай, закончили

пустой (слева от десятки ничего не было) — базовый случай, закончили

7 8 — более одного элемента, это рекурсивный случай, выбираем первый элемент опорным и продолжаем

Три из четырех массивов на предыдущей итерации попали в базовый случай и завершились, последний подмассив снова рекурсивно вызывается на сортировку, теперь получаем следующее:

пусто (слева от семерки ничего не было)

8

Оба этих случая базовые, а значит рекурсивные вызовы закончились. Теперь нам нужно собрать или склеить результаты всех вызовов функции быстрой сортировки. Собирается это всё по принципу левый подмассив + опорный элемент + правый подмассив.

Попробуем немного изобразить что мы сделали в виде картинки.

Каждый раз мы рекурсивно делили массив на 2 части относительно опорного элемента. Затем достигнув базового случая в каждом из подмассивов завершаем рекурсивный вызов.

Сложность алгоритма

В большинстве случаев алгоритм быстрой сортировки является наиболее быстрым вариантом сортировки массива данных. Однако не забывайте что очень многое зависит от выбора опорного элемента.

Практическое применение:

Алгоритм быстрой сортировки имеет очень широкое применение и встроен в качестве функции/метода в большинство языков программирования.

Сообщение Быстрая сортировка появились сначала на Blogee.

Сортировка простыми обменами, она же пузырьковая сортировка, крайне популярный алгоритм используемый в процессе обучения студентов. Популярность алгоритма заключается в простоте объяснения и реализации данного алгоритма в программном коде.

Начинаем разбираться. Допустим у нас есть массив целых чисел, возьмем к примеру вот такую последовательность:

4 8 1 9 2 6

И нам нужно её отсортировать с помощью алгоритма пузырьковой сортировки. Алгоритм заключается в том, что мы последовательно попарно сверяем по 2 соседних элемента массива и если элемент справа меньше чем элемент слева, то они меняются местами. Более легкий элемент будто всплывает, отсюда и название алгоритма. После первого прохода по всему массиву самый тяжелый элемент осядет в конце списка. Давайте рассмотрим это на нашем примере:

4 8 1 9 2 6

Берем первые 2 элемента(выделены оранжевым цветом) и сверяем их, если первый элемент из пары больше чем второй элемент в паре, то они меняются местами. В нашем же случае первый элемент меньше второго, а значит в этой паре всё остается как есть. Теперь сравниваем следующую пару чисел.

4 8 1 9 2 6

Сравниваем по тому же принципу новую пару, 8 и 1. Первое число больше второго, а значит их нужно поменять местами. Напоминаю, более легкий элемент всплывает, более тяжелый тонет. Меняем местами и берем следующую пару чисел:

4 1 8 9 2 6

Как вы можете заметить, восьмерка опустилась ниже, единица всплыла. Берем следующую пару, это 8 и 9. Первое число меньше, значит оба остаются на своих позициях. Берем следующие:

4 1 8 9 2 6

Первое число больше второго, меняем местами и берем следующую пару:

4 1 8 2 9 6

И вот мы добрались до последней пары в нашем массиве. И снова первое число больше второго, значит меняем местами. По итогу полного прохода получаем вот такую картину:

4 1 8 2 6 9

Самый тяжелый элемент «ушел на дно». Теперь нам нужно повторить все наши действия с самого начала, но не трогать последний элемент, мы его выделили красным цветом. На втором круге делается всё тоже самое, поэтому не буду расписывать. После всей цепочки перестановок на 2 круге получим следующую картину:

4 1 8 2 6 9 — 1 4 8 2 6 9 — 1 4 8 2 6 9 — 1 4 2 8 6 9 — 1 4 2 6 8 9

Мы также сравнивали попарно и после второго круга у нас появился ещё один отсортированный элемент. Продолжаем все наши действия сначала и исключая уже отсортированные элементы до тех пор пока не отсортируется весь массив. Давайте реализуем всё это в программном коде:

//Создадим наш массив для сортировки
int[] arrayToSort = { 1, 3, 9, 5, 2, 6, 0, 4 };
//Получаем длину нашего массива
int len = arrayToSort.Length;
//Переменная для временного хранения значения при перестановке
int tmp;
//Цикл отвечает за количество проходов по массиву
for (int i = 0; i < len - 1; i++)
{
   //А в этом цикле мы перебираем элементы
   //условие j < len-1-i отвечает за то, чтобы на очередной итерации мы не брали уже отсортированные элементы
   //которые ушли на "дно" массива
   for (int j = 0; j < len-1-i; j++)
   {
       //Проверяем больше ли элемент в позиции j чем стоящий справа от него элемент в позиции j+1 
       if (arrayToSort[j] > arrayToSort[j+1])
       {
       //Если больше, тогда первый элемент из пары кладем во временную переменную tmp
       tmp = arrayToSort[j];
       //И ставим на позицию первого элемента, тот что стоит за ним
       arrayToSort[j] = arrayToSort[j+1];
       //И теперь на позицию второго элемента из пары помещаем значение из временной переменной
       arrayToSort[j+1] = tmp;
       }
       //Если первый элемент в паре оказался меньше, ничего не делаем и берем следующую пару
   }
}

#
Код на Python будет добавлен позже. 
#

Алгоритм пузырьковой сортировки имеет несколько улучшений и модификаций. Одно из них это использование флага проверки произошел ли обмен во время обхода элементов последовательности. Зачем это нужно ?

Массив ведь может прийти откуда угодно и не исключено что он уже отсортирован. Зачем нам в таком случае бегать по нему кругами ? Добавляем переменную-флажок и установим ему значение false, который будет переходить в значение true если на очередном переборе элементов массива была хоть одна перестановка. Если ни одной перестановки не произошло, значит массив полностью отсортирован и внешний (первый) цикл будет прерван. Модифицированный код будет выглядеть так:

int[] arrayToSort = { 1, 3, 9, 5, 2, 6, 0, 4 };
int len = arrayToSort.Length;
int tmp;
//Устанавливаем переменную флага в false
bool flag = false;

for (int i = 0; i < len - 1; i++)
{
//Перед началом внутреннего цикла нужно сбросить флаг в false
//иначе цикл завершится после первого обхода
   flag = false;
   for (int j = 0; j < len-1-i; j++)
   {
       if (arrayToSort[j] > arrayToSort[j+1])
       {
          tmp = arrayToSort[j];
          arrayToSort[j] = arrayToSort[j+1];
          arrayToSort[j+1] = tmp;
          //произошел обмен позициями, устанавливаем flag в true
          flag = true;
       }
   }
   //Проверяем флаг
   if (flag == false) break;
}

Новые строки подсвечены.

Сложность алгоритма

Алгоритм пузырьковой сортировки имеет сложность O (N²). Это значит что если мы сортируем массив из 10 элементов, то сложность алгоритма составит 10 в квадрате = 100. Не забываем, что сложность алгоритма O-большое оценивает алгоритм по наихудшему случаю когда мы достигаем конечного результата.

Практическое применение:

Алгоритм пузырьковой сортировки не имеет практического применения и практически не выходит за рамки учебной литературы.

Тем не менее, считается что алгоритм из-за его простоты вполне возможно использовать, но только на массивах малой длины или на простаивающих машинах. В остальных случаях применяются более совершенные алгоритмы сортировки, например — алгоритм быстрой сортировки, который на больших массивах данных значительно превосходит пузырьковую сортировку.

Сообщение Сортировка пузырьком появились сначала на Blogee.