Порівняльна характеристика методів сортування: метод обміну і метод вставки

Сортування простими обмінами, сортування бульбашкою — простій алгоритм сортування. Для розуміння і реалізації цей алгоритм — простий, але|та| ефективний він лише для невеликих масивів. Складність алгоритму: 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|.

Наши рекомендации