Порівняльна характеристика методів сортування: метод обміну і метод вставки
Сортування простими обмінами, сортування бульбашкою — простій алгоритм сортування. Для розуміння і реалізації цей алгоритм — простий, але|та| ефективний він лише для невеликих масивів. Складність алгоритму: O(n?).
Алгоритм полягає в проходах, що повторюються, по сортованому масиву. За кожен прохід елементи послідовно порівнюються попарно і, якщо порядок|лад| в парі невірний, виконується обмін елементів. Проходи по масиву повторюються до тих пір, поки на черговому проході не виявиться, що обміни більше не потрібні, що означає — масив відсортований. При проході алгоритму, елемент, що стоїть не на своєму місці|місце-милі|, «спливає» до потрібної позиції як бульбашка у воді, звідси і назва алгоритму.
Приклад на Java
for(int i = 0; i < a.length - 1; i++)
for(int j = 0; j < a.length - i - 1; j++)
if(a[j] > a[j + 1])
swap(a[j], a[j + 1]);
Сортування вставками — простий алгоритм сортування. Хоча цей метод сортування набагато менш ефективний, ніж складніші алгоритми, у нього є ряд|лава,низка| переваг:
- простий в реалізації;
- ефективний на невеликих наборах даних, на наборах даних до десятків елементів можуть виявитися кращими;
- ефективний на наборах даних, які вже частково відсортовані;
- це стійкий алгоритм сортування (не міняє|змінює,замінює| порядок|лад| елементів, які вже відсортовані);
- може сортувати список у міру його отримання|здобуття|;
- не вимагає тимчасової пам'яті, навіть під стек.
Сортування вставкою є|з'являється,являється| останнім з|із| класу простих алгоритмів сортування. При сортуванні вставкою спочатку упорядковуються два елементи масиву. Потім робиться|чинить| вставка третього елементу у відповідне місце|місце-милю| відносно перших двох елементів. Потім робиться|чинить| вставка четвертого елементу в список з|із| трьох елементів. Цей процес повторюється до тих пір, поки всі елементи не будуть впорядковані. Наприклад, для масиву "dcab|" сортування вставкою проходитиме|минатиме,спливатиме| таким чином:
- Початковий|вихідний| стан|достаток|: d с|із| а b;
- Перший прохід: с|із| d а b;
- Другий прохід: а с|із| d b;
- Третій прохід: а b с|із| d.
Метод вибору чергового елементу з|із| початкового|вихідного| масиву довільний; може використовуватися практично будь-який алгоритм вибору. Зазвичай|звично| (і з метою отримання|здобуття| стійкого алгоритму сортування), елементи вставляються по порядку їх появи у вхідному масиві.
Приклад
for j = 2 to A.length
key = A[j]
i = j - 1
while i > 0 and A[i] > key
A[i+1] = A[i]
i = i - 1
A[i+1] = key
Принципи об'єктно-орієнтованого програмування: інкапсуляція, наслідування та поліморфізм
Об'єктно-орієнтоване, або об'єктне, програмування (надалі ООП) — парадигма програмування, в якій основними концепціями є|з'являються,являються| поняття об'єктів і класів. У разі|в разі| мов|язиків| з|із| прототипіруванням| замість класів використовуються об'єкти-прототипи.
По Бьєрну Страуструпу, авторові C++|, мова|язик| може називатися об'єктно-орієнтованою, якщо в неї реалізовано три концепції: об'єкти, класи і Наслідування. Проте|однак| тепер прийнято вважати|лічити|, що такі мови|язики| повинні триматися на інших трьох китах: інкапсуляції, спадкоємстві і поліморфізмі. Це філософське зрушення|зсув| відбулося через те, що з часом|згодом| ми почали|стали| розуміти: побудувати|спорудити| об'єктно-орієнтовані системи без інкапсуляції і поліморфізму так само неможливо, як без класів і спадкоємства.
Інкапсуляція
Інкапсуляція, або приховування інформації (information| hiding|), — це можливість|спроможність| приховати внутрішній устрій об'єкту від його користувачів, надавши через інтерфейс доступ тільки|лише| до тих членів об'єкту, з|із| якими клієнтові дозволяється працювати безпосередньо|прямо|. Інкапсуляція має на увазі наявність межі|кордону| між зовнішнім інтерфейсом класу (відкритими|відчиняти| членами, видимими користувачам класу) і деталями його внутрішньої реалізації. Перевага інкапсуляції для розробника в тому, що він може відкрити|відчиняти| ті члени класу, які залишатимуться статичними, або незмінними, приховавши внутрішню організацію класу, динамічнішу і більшою мірою схильну до змін. У програмуванні інкапсуляція досягається шляхом призначення кожному членові класу свого модифікатора доступу — public|, private| або protected|.
Наслідування
Наслідуванням називають можливість|спроможність| при описі класу указувати|вказувати| на його походження(kind-of| relationship|) від іншого класу. Наслідування дозволяє створити новий клас, в основу якого покладений той, що існує|наявний|. У отриманий|одержувати| таким чином клас можна внести свої зміни, а потім створити нові об'єкти даного типу|типа|. Цей механізм лежить в основі створення|створіння| ієрархії класів. Похідним (derived| class|) називається створюваний клас, похідний від базового (base| class|). Похідний клас успадковує|наслідує| всі методи базового, дозволяючи задіяти результати колишньої праці.
Поліморфізм
Поліморфізм - це функціональна можливість|спроможність|, що дозволяє старому коду викликати|спричиняти| новий. Це властивість ООП, мабуть, найцінніше|коштовний|, оскільки дає вам можливість|спроможність| розширювати і удосконалювати|вдосконалювати| свою систему, не зачіпаючи існуючий код.
Припустимо|передбачатимемо|, вам потрібно написати метод, в якому для кожного об'єкту з|із| набору Employee| викликається|спричиняє| метод CakulatePay|. Все просто, якщо зарплата розраховується одним способом: ви можете відразу вставити в набір тип|типа| потрібного об'єкту. Проблеми починаються|розпочинають,зачинають| з|із| появою інших форм оплати. Допустимо, у вас вже є клас Employee|, що реалізує розрахунок зарплати по фіксованому окладу. А що робити|чинити|, щоб|аби| розрахувати зарплату контрактников| — адже це вже інший спосіб розрахунку. У випадку з процедурною мовою|язиком| вам довелося|припало| б переробити функцію, включивши в неї новий тип|типа| обробки, оскільки|тому що| в колишньому коді такої обробки немає. А об'єктно-орієнтована мова|язик| завдяки поліморфізму дозволяє робити|чинити| різну обробку.
Поліморфізм має явних два плюси. По-перше, він дозволяє групувати об'єкти, що мають загальний|спільний| базовий клас, і послідовно (наприклад, в циклі) їх обробляти. По-друге, старий код може використовувати новий код.
14. Об'єктно-орієнтовані мови програмування Delphi і Java|
Java|
З 1995 року почала|стала| широко розповсюджуватися|поширюватися| нова об'єктно-орієнтована мова|язик| програмування Java|, орієнтована на мережі|сіті| комп'ютерів і, перш за все|передусім|, на Internet|. Синтаксис цієї мови|язика| нагадує синтаксис мови|язика| C++|, проте|однак| ці мови| мають мало спільного|спільного|. Java -| мова|язик|, що інтерпретується: для неї визначено внутрішнє уявлення|виставу, подання, представлення| (bytecode|) і інтерпретатор цього уявлення|вистави, подання, представлення|, які вже зараз реалізовані на більшості платформ. Інтерпретатор спрощує налагодження програм, написаних на мові|язиці| Java|, забезпечує їх переносимість|переносимий| на нові платформи і адаптується|пристосував| до нових оточень. Він дозволяє виключити вплив програм, написаних на мові|язиці| Java|, на інші програми і файли, що є|наявний| на новій платформі, і тим самим забезпечити безпеку при виконанні цих програм. Ці властивості мови|язика| Java| дозволяють використовувати її як основну мову|язик| програмування для програм, поширюваних по мережах|сітях| (зокрема, по мережі|сіті| Internet|).
Delphi| (Дельфі) - середовище|середа| програмування, що використовує мову|язик| Object| Pascal|, розроблену фірмою|фірма-виготовлювачем| Borland| і спочатку реалізовану в її пакеті Borland| Delphi|, від якого і отримала|одержував| в 2003 році свою нинішню назву. По суті є|з'являється,являється| спадкоємцем мови|язика| Pascal| з|із| об'єктно-орієнтованими розширеннями. Object| Pascal| створювалася співробітниками компанії Apple| Computer| (деякі з яких були учасниками проекту Smalltalk|) спільно з|із| Никлаусом Віртом (Niklaus| Wirth|), творцем мови|язика| Pascal|. Object| Pascal| відома з 1986 року і є|з'являється,являється| першою об'єктно-орієнтованою мовою|язиком| програмування, яка була включена в Macintosh| Programmer's| Workshop| (MPW|), середовище|середу| розробки для комп'ютерів Macintosh| фірми|фірма-виготовлювача| Apple|. В цій мові|язиці| немає методів класу, змінних класу, множинного|численного| спадкоємства і метакласів|. Ці механізми виключені спеціально, щоб|аби| зробити мову|язик| простою для вивчення початкуючими "об'єктними" програмістами. Останніми роками ця мова|язик| стала дуже популярна завдяки системі Delphi| фірми|фірма-виготовлювача| Borland|.