Більш складні алгоритми

Завдання 1 - Bubble Sort

У Рівні 1 – Завдання 9 ви створили надзвичайно простий алгоритм сортування під назвою “Bogo”-сорт. Bogo sort – жахливий алгоритм. Він має час виконання \(O(n!)\). Тобто, з 5 елементами ви можете очікувати ~ \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\) операцій. І це тільки зростає.

У цьому завданні ми створимо кращий алгоритм, який все ще дуже простий: сортування бульбашкою. Він працює так:

Дізнайтеся більше про сортування бульбашкою на Wikipedia

Приклад кроків сортування

Ми будемо використовувати список [4, 7, 1, 2, 9] у цьому прикладі.

=== "Крок 2"

- ✅ Починаємо з індексу 0
- ❕ `[4, 1, 2, 7, 9]`
- ❓Чи 4 більше ніж 1? ✔️-> Поміняти місцями та збільшити індекс на 1
- ❕ `[1, 4, 2, 7, 9]`
- ❓Чи 4 більше ніж 2? ✔️-> Поміняти місцями та збільшити індекс на 1
- ❕ `[1, 2, 4, 7, 9]`
- ❓Чи 4 більше ніж 7? ❌-> Збільшити індекс на 1
- ❓Чи 7 більше ніж 9? ❌-> Збільшити індекс на 1
- ✅ Тепер ми досягли кінця. Почніть знову (наступний крок).

- Список вже відсортований, але у *найгіршому випадку* список не буде повністю відсортований лише після двох кроків. Сортування може зайняти до 4 кроків (довжина списку мінус 1).
- Або ви можете додати перевірку, яка перевіряє, чи список відсортований після кожної ітерації, або просто дозволити йому завершитися.

for i in len(list):
    for j in len(list):
        if list[j] > list [j + 1]
            swap(list[j], list[j + 1])
        else 
            break

Завдання 1b - Розмірковуємо про “Bubble sort”

• Наскільки швидкий цей алгоритм?
  • Подумайте трохи про нотацію “Big O” тут.
    • Підказка: Скільки for-циклів вкладено один в один?
• Чи можете ви зробити цей алгоритм швидшим?
• Наскільки швидким може бути алгоритм сортування?

Завдання 2 - Selection Sort

Selection sort – це ще один простий алгоритм сортування. Він має часову складність \(O(n^2)\), що робить його дуже неефективним для більших списків. Замість того, щоб переміщувати елементи по всьому списку, як у bubble sort, цей алгоритм знаходить найменший елемент і розміщує його на початку списку (міняє місцями з тим, що там є).

Дізнайтеся більше про Selection-sort на Wikipedia

Приклад кроків сортування

Ми будемо використовувати список [4, 7, 1, 2, 9, 6] у цьому прикладі.

> [!EXAMPLE] Крок 1
>
> - ✅ Встановити початковий індекс на 0
> - ❕ `[4, 7, 1, 2, 9, 6]`
> - ✅ Встановити індекс 0 на найменший елемент
> - ❓ Чи індекс 1 менший? Ні.
> - ❓ Чи індекс 2 менший? Так -> встановити індекс 2 на найменший елемент
> - ❓ Чи індекс 3 менший? Ні
> - ❓ Чи індекс 4 менший? Ні
> - ❓ Чи індекс 5 менший? Ні
> - ✅ Поміняти місцями індекс 2 та 0
> - ❕ `[1, 7, 4, 2, 9, 6]`
> - ✅ Збільшити початковий індекс на 1, з 0 до 1

=== "Крок 2"

> [!EXAMPLE] Крок 2
>
> - ✅ Встановіть початковий індекс на 1
> - ❕ `[1, 7, 4, 2, 9, 6]`
> - ✅ Встановіть індекс 1 на найменший елемент
> - ❓ Чи індекс 2 менший? Так -> встановіть індекс 2 на найменший елемент
> - ❓ Чи індекс 3 менший? Так -> встановіть індекс 3 на найменший елемент
> - ❓ Чи індекс 4 менший? Ні
> - ❓ Чи індекс 5 менший? Ні
> - ✅ Поміняйте місцями індекс 3 та 1
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Збільште початковий індекс з 1 до 2

> [!EXAMPLE] Крок 3
>
> - ✅ Встановіть початковий індекс на 2
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Встановіть індекс 2 на найменший елемент
> - ❓ Чи індекс 3 менший? Ні
> - ❓ Чи індекс 4 менший? Ні
> - ❓ Чи індекс 5 менший? Ні
> - ✅ Замініть індекс 2 та 2 (Нічого не відбувається)
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Збільште початковий індекс з 2 до 3

> [!EXAMPLE] Крок 4
>
> - ✅ Встановіть початковий індекс на 3
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Встановіть індекс 3 на найменший елемент
> - ❓ Чи індекс 4 менший? Ні
> - ❓ Чи індекс 5 менший? Так -> встановіть індекс 5 на найменший елемент
> - ✅ Поміняйте місцями індекс 5 та 3
> - ❕ `[1, 2, 4, 6, 9, 7]`
> - ✅ Збільште початковий індекс з 3 до 4
>```

</span>

<span class="turtletranslate-section" data-turtletranslate-type="wildcard" data-turtletranslate-index="27" data-turtletranslate-checksum="e50032f15af7ba2a">

=== "Крок 5"

</span>

<span class="turtletranslate-section" data-turtletranslate-type="wildcard" data-turtletranslate-index="28" data-turtletranslate-checksum="469b5c0a297fc9f0">

```markdown
> [!EXAMPLE] Крок 5
>
> - ✅ Встановіть початковий індекс на 4
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Встановіть індекс 4 на найменший елемент
> - ❓ Чи індекс 5 менший? Так -> встановіть індекс 5 на найменший елемент
> - ✅ Поміняйте місцями індекс 5 і 4
> - ❕ `[1, 2, 4, 6, 7, 9]`
> - ✅ Збільште початковий індекс з 4 до 5
> - ✅ Ми досягли кінця списку, тепер зупиняємося

[!INFO]- Viktige hint

• Вам потрібно два цикли.
• Перший може бути зручним, якщо це while-цикл, щоб початкове значення було легко збільшувати з кожної ітерації.
• Ви можете перевіряти, чи відсортовано цикл після кожної ітерації, але алгоритм працює лише до досягнення індексом кінця.

Завдання 3 - Бінарний пошук (Binærsøk)

У цьому завданні ви повинні створити швидший алгоритм пошуку, ніж у Level 1 – Завдання 1. Там, хоча ви, ймовірно, і не знали, що це називається, ви створили лінійний алгоритм пошуку. Це означає, що він працює за час \(O(n)\).

Але, можна зробити краще! Якщо список вже відсортований, ви можете знайти те, що шукаєте, з набагато меншою кількістю порівнянь, а саме за час \(O(log_2(n))\).

Це означає наступний час виконання:

Якби у вас був список з МІЛІАРДОМ, \(10^9\), \(1 000 000 000\) елементів, знайти число зайняло б максимум \(30\) операцій.

Алгоритм працює так:

[!EXAMPLE]+ Алгоритм

Передумови: Почніть з відсортованого списку!

1. Відстежуйте дві межі, left і right. left починається з 0, а right починається з довжини списку, мінус 1, len(the_list) - 1.
2. Використовуйте while-цикл або for-цикл, який виконується до \(\lfloor log_2(n) \rfloor\) разів. (Ці дужки означають floor, тобто округлення вниз). Він повинен зупинитися, коли left > right.

Основний крок:

1. Знайдіть середній індекс за допомогою \(\frac{left + right}{2}\) ((left + right) / 2).
2. Якщо the_list[mid] є тим, що ви шукаєте, поверніть True. Якщо ні:
3. Перевірте, чи число більше чи менше.
4. Якщо менше, ви знаєте, що ліва сторона списку не містить елемент (пам’ятайте, він відсортований!). Встановіть left = mid + 1
5. Якщо більше, ви знаєте, що права сторона списку не містить елемент. Встановіть right = mid - 1

Якщо цикл закінчується, не знайшовши елемент, його немає в списку. Поверніть False.

Приклад пошукового кроку

У цьому прикладі ми будемо використовувати список [1, 3, 5, 7, 9, 11, 13, 15]. Ми будемо шукати число 13.

> [!EXAMPLE] Крок 1
> - ✅ Встановіть `left` на 0.
> - ✅ Встановіть `right` на довжину - 1, тобто 7.
> - ✅ Знайдіть середній індекс, 3. (`(0 + 7) / 2 = 3.5` (округліть вниз до 3))
> - ❕ `left = 0`, `right = 7`, `list[mid] = 9`
> - ❓ Чи 9 дорівнює 13? Ні...
> - ❓ Чи 9 менше ніж 13? Так!
> - ✅ Встановіть left на mid + 1
> - ❕ `left = 4`, `right = 7`

=== "Крок 2"

[!EXAMPLE] Крок 2
- ✅ Знайдіть середній індекс, (4 + 7 / 2 = 5.5 (округліть вниз до 5)).
- ❕ left = 4, right = 7
- ❓ Чи 11 дорівнює 13? Ні…
- ❓ Чи 11 менше ніж 13? Так!
- ✅ Встановіть left на mid + 1
- ❕ left = 6, right = 7

[!EXAMPLE] Крок 3
- ✅ Знайдіть середній індекс, (6 + 7 / 2 = 6.5 (округліть вниз до 6)).
- ❕ left = 6, right = 7
- ❓ Чи 13 дорівнює 13? Так! Поверніть True.

Завдання 4 - Розвернути слова без розділення

Згадайте Завдання 11 у Рівні 1. Там ви мали розвернути окремі слова в реченні. Створіть алгоритм, який робить те саме, але без використання вбудованої функції .split().

[!INFO]- Tips til framgangsmåte

• Почніть з того ж вихідного пункту, що й у Level 1 Завдання 8
• Створіть власну функцію розбиття та використовуйте її в алгоритмі.
• Пройдіть по всьому реченню за допомогою for-циклу та з’ясуйте, де знаходиться символ розбиття, наприклад, пробіл ' '.
• Створіть список, який містить кожну частину розбиття.

Завдання 5 - Quick Sort

Дізнайтеся більше про quick sort: Wikipedia, Quick Sort.
Дізнайтеся більше про рекурсію: Wikipedia, Recursion.

Quick-sort, як випливає з назви, є швидким алгоритмом сортування. Цей, на відміну від selection-sort та bubble-sort, є надзвичайно швидким, він має час виконання \(O(n \cdot log_2(n))\). Що є надзвичайно швидко. Він відомий як алгоритм розділяй і володарюй.

Як це працює на практиці?

[!INFO]+ Hvordan Quick Sort fungerer

1. Це рекурсивний алгоритм, тобто він викликає сам себе кілька разів.
2. Замість того, щоб розділяти посередині, як це робить merge sort, quick sort вибирає випадковий індекс (або середній, якщо ви віддаєте перевагу), відомий як pivot елемент. Тут ви можете використовувати бібліотеку random. Або, якщо ви відчуваєте себе сміливим, створіть функцію для знаходження випадкових чисел самостійно.
3. Потім пройдіть по всьому списку та створіть ліву та праву частини, де ліва містить усі елементи менші за pivot, а права – усі більші за pivot (включно з pivot).
4. Повторюйте quick-sort рекурсивно на лівій та правій частинах.
5. Якщо розділений список має 1 елемент, то він відсортований, поверніть і з’єднайте.
6. Ці рекурсивні виклики “автоматично” закінчаться сортуванням списку.
7. Поверніть відсортований список.
   

[!INFO]- Tips til framgangsmåte

• Створіть функцію під назвою quick_sort
• return, якщо список має 1 елемент або менше.
• Оберіть випадковий опорний елемент за допомогою random.choice()
• Створіть порожні списки left та right.
• Використовуйте quick_sort знову для left та right:

def quick_sort(list_in):
    # Код для решти quick-sort
    # використовуйте quick_sort всередині себе
    left_result = quick_sort(left)
    right_result = quick_sort(right)

• Просто об’єднайте left та right за допомогою for-циклу
• return об’єднаний список

Завдання 6 - Merge Sort

Дізнайтеся більше про merge sort: Wikipedia, Merge Sort.

Merge sort – елегантний алгоритм сортування, який “зливає”, тобто об’єднує менші списки. Цей, як і quick-sort, має час виконання \(O(n \cdot log_2(n))\). Він у багатьох відношеннях досить схожий на quick-sort, але використовує інші стратегії для виконання сортування. Це рекурсивний, розділяй та володарюй алгоритм.

Як це працює?

[!INFO]+ Hvordan Merge-sort fungerer

1. Merge-sort є рекурсивним, тобто він запускає себе знову і знову.
2. Це так званий алгоритм “розділяй і володарюй” (який може бути корисним ключовим словом).
3. Прийміть список у функцію
4. Розділіть список на дві частини, ліву та праву, і знову запустіть його всередині себе (merge_sort функція).
5. Повторюйте, поки список не стане одним елементом.
6. Тепер з’єднайте ліву та праву частини.
7. З’єднання працює шляхом порівняння першого елемента в обох списках і вибору найменшого, і додавання його в новий список.
8. Потім порівнюється наступний елемент у кожній половині.
9. Наприклад, якщо лівий список мав найменше, ви збільшуєте порівняння на лівому списку, але не на правому, і навпаки.
10. Поверніть у кінці відсортований список.
    

[!INFO]- Tips til framgangsmåte

1. Тут слід використовувати функцію merge_sort, яка приймає список.
2. Спочатку перевірте, чи довжина списку менше 2 елементів. Якщо є лише один елемент, то він вже відсортований, тому просто return вхідний список.
3. Розділіть список на дві частини: ліву та праву.
4. Використовуйте середню точку len(list) // 2 для розділення на дві частини. (// є спеціальною функцією для цілочисельного ділення).
5. Запустіть функцію merge_sort на кожній частині. Це повторює кроки 2-4.
6. Після того, як merge_sort було запущено на обох частинах, запустіть їх в функцію merge, яка об’єднує списки.
7. У merge створіть порожній список.
8. Використовуйте while і порівнюйте перший елемент в обох списках.
9. Створіть дві лічильні змінні, i та j, обидві починаються з 0.
10. Цикл while повинен тривати до тих пір, поки i або j не будуть більшими за список, з яким вони порівнюються.
11. Якщо в лівому списку найменший елемент, додайте цей елемент до порожнього списку та збільште i на 1, інакше зробіть те саме з правим, але з j.
12. Після зупинки while це означає, що одна з двох половин списку “порожня”. Потім пройдіть через решту елементів у “непорожній” половині та додайте їх до порожнього списку.
13. Поверніть список, який було об’єднано.
14. У merge_sort поверніть цей список.

Приклад кроків сортування

[!EXAMPLE]- Bilde som viser steg

Тут використовується список [12, 8, 9, 3, 11, 5, 4]

[!EXAMPLE]+ Кроки у текстовому форматі

Ми будемо використовувати список [2, 7, 1, 6, 3, 8, 5, 4] у цьому прикладі.

• ✔️ Список: [2, 7, 1, 6, 3, 8, 5, 4]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [2, 7, 1, 6] - [3, 8, 5, 4]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ❕ [1, 2, 6, 7] - [3, 4, 5, 8]
• ✅ Комбінувати відсортовані списки -> [1, 2, 3, 4, 5, 6, 7, 8]
• ✅ Повернути список -> Готово! (Див. підкроки для більшої кількості деталей!)

[!EXAMPLE]- Крок L (Лівий)

• ✔️ Список: [2, 7, 1, 6]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [2, 7] - [1, 6]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ❕ [2, 7] - [1, 6]
• ✅ Комбінувати відсортовані списки -> [1, 2, 6, 7]
• ✅ Повернути список

[!EXAMPLE]- Крок L.L (Лівий, Лівий)

• ✔️ Список: [2, 7]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [2] - [7]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ✅ Комбінувати відсортовані списки -> [2, 7]
• ✅ Повернути список

[!EXAMPLE]- Крок L.L.L (Лівий, Лівий, Лівий)

• ✔️ Список: [2]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок L.L.R (Лівий, Лівий, Правий)

• ✔️ Список: [7]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок L.R (Лівий, Правий)

• ✔️ Список: [1, 6]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [1] - [6]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ✅ Комбінувати відсортовані списки -> [1, 6]
• ✅ Повернути список

[!EXAMPLE]- Крок L.R.L (Лівий, Правий, Лівий)

• ✔️ Список: [1]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок L.R.R (Лівий, Правий, Правий)

• ✔️ Список: [6]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R (Правий)

• ✔️ Список: [3, 8, 5, 4]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [3, 8] - [5, 4]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ❕ [3, 8] - [4, 5]
• ✅ Комбінувати відсортовані списки -> [3, 4, 5, 8]
• ✅ Повернути список

[!EXAMPLE]- Крок R.L (Правий, Лівий)

• ✔️ Список: [3, 8]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [3] - [8]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ✅ Комбінувати відсортовані списки -> [3, 8]
• ✅ Повернути список

[!EXAMPLE]- Крок R.L.L (Правий, Лівий, Лівий)

• ✔️ Список: [3]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R.L.R (Правий, Лівий, Правий)

• ✔️ Список: [8]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R.R (Правий, Правий)

• ✔️ Список: [5, 4]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [5] - [4]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ✅ Комбінувати відсортовані списки -> [4, 5]
• ✅ Повернути список

[!EXAMPLE]- Крок R.R.L (Правий, Правий, Лівий)

• ✔️ Список: [5]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R.R.R (Правий, Правий, Правий)

• ✔️ Список: [4]
• ❓ Чи коротший список ніж 2? Так -> Повернути

[!EXAMPLE]- Крок R (Правий)

• ✔️ Список: [3, 8, 5, 4]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [3, 8] - [5, 4]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ❕ [3, 8] - [4, 5]
• ✅ Комбінувати відсортовані списки -> [3, 4, 5, 8]
• ✅ Повернути список

[!EXAMPLE]- Крок R.L (Правий, Лівий)

• ✔️ Список: [3, 8]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [3] - [8]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ✅ Комбінувати відсортовані списки -> [3, 8]
• ✅ Повернути список

[!EXAMPLE]- Крок R.L.L (Правий, Лівий, Лівий)

• ✔️ Список: [3]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R.L.R (Правий, Лівий, Правий)

• ✔️ Список: [8]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R.R (Правий, Правий)

• ✔️ Список: [5, 4]
• ❓ Чи коротший список ніж 2? Ні -> Розділити
• ✅ Розділити список на два
• ❕ [5] - [4]
• ✅ Повторити merge-sort на лівій та правій сторонах
• ✅ Комбінувати відсортовані списки -> [4, 5]
• ✅ Повернути список

[!EXAMPLE]- Крок R.R.L (Правий, Правий, Лівий)

• ✔️ Список: [5]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

[!EXAMPLE]- Крок R.R.R (Правий, Правий, Правий)

• ✔️ Список: [4]
• ❓ Чи коротший список ніж 2? Так -> Повернути
  

➕Додатково:

Завдання E1a - Сортування Тексту

Тут вам потрібно реалізувати алгоритм сортування, який може сортувати текст в алфавітному порядку. Це фактично може працювати для всіх алгоритмів, які ви робили (окрім Counting Sort з Level 1 - Додаткове).

Завдання: Оберіть один з алгоритмів з попереднього завдання, змініть його, щоб він міг сортувати текст.

Як порівнюються тексти?

Текст насправді можна порівнювати! Але, можливо, не одразу очевидно, як саме. Уявіть собі приклад з цими двома словами:
apple та banana. Яке слово слід сортувати першим? Так, має сенс, що це має бути apple, оскільки воно починається на a.

Ми можемо розглядати порівняння як перевірку, чи відповідь є -1, 0 або 1. Якщо відповідь:

• -1 то текст “менший”, тобто повинен бути раніше
• 0 то текст абсолютно ідентичний.
• 1 то текст “більший”, тобто повинен бути пізніше

Перш ніж створити алгоритм сортування

Før du begynner å kode sorteringsalgoritmen, er det viktig å forstå hva sortering innebærer og hvilke krav som stilles til en effektiv algoritme. Sortering handler om å ordne elementer i en liste eller et array i en bestemt rekkefølge, enten stigende eller synkende.

En effektiv sorteringsalgoritme bør oppfylle følgende krav:

• Korrekthet: Algoritmen må sortere elementene riktig i alle tilfeller.
• Effektivitet: Algoritmen bør bruke minimalt med tid og minne.
• Stabilitet: En stabil sorteringsalgoritme bevarer den relative rekkefølgen av like elementer.

Det finnes mange forskjellige sorteringsalgoritmer, hver med sine egne fordeler og ulemper. Noen vanlige algoritmer inkluderer:

• Boblesortering
• Innsettingssortering
• Utvalgssortering
• Quicksort
• Mergesort

Valget av algoritme avhenger av faktorer som størrelsen på datasettet, typen data og kravene til ytelse.

Før du implementerer en sorteringsalgoritme, er det lurt å tenke gjennom følgende:

• Hvilken datastruktur skal du sortere? (f.eks. liste, array)
• Hvilken sorteringsrekkefølge ønsker du? (stigende eller synkende)
• Hvilke krav stilles til ytelsen?
• Er det viktig at algoritmen er stabil?

Ved å svare på disse spørsmålene kan du velge den mest passende sorteringsalgoritmen for ditt behov.

Før du begynner å kode, kan det også være lurt å teste algoritmen med noen enkle eksempler for å sikre at den fungerer som forventet. Dette kan spare deg for mye tid og frustrasjon senere.

[!SUCCESS]- Store і Малі літери?

Це залежить від вас, чи хочете ви ігнорувати великі чи малі літери.

• Якщо ви хочете, щоб B було те саме, що й b, можете використати .lower()
• За бажанням, ви можете реалізувати власну функцію lower(), якщо хочете ще більший виклик.
• Зверніться до таблиці ASCII, щоб дізнатися, як можна змінити значення за допомогою математичного обчислення.

[!INFO]- Tips til framgangsmåte for Tekst-sammenlignings Algoritme

1. Використовуйте лічильну змінну i = 0
2. Використовуйте while цикл для порівняння літера за літерою, збільшуйте i на 1 кожен раунд
3. Подбайте про вихід за межі індексу, перевіряючи, чи i менше за довжину тексту 1 або тексту 2.
4. Порівняйте, чи tekst1[i] дорівнює tekst2[i], якщо ні, перевірте, чи літера менша або більша. Поверніть -1 або 1.
5. Якщо while не повертає значення, перевірте, чи довжини однакові. Якщо вони однакові, поверніть 0, інакше поверніть -1

Використовуйте потім цей алгоритм сортування тексту в алгоритмі сортування, щоб відсортувати текст!

[!WARNING] Hint!

Пам’ятайте, що тепер порівняння має три значення: -1, 0, 1. Це означає, що вам потрібно змінити спосіб формування відповіді в деяких з алгоритмів сортування.

Приклад: У швидкому сортуванні вам потрібно додати частину middle.

Завдання E1b - Текст чи Число?

Змініть свій код у Завданні E1a, щоб він міг сортувати цілі списки чисел або цілі списки тексту. Це можна зробити, перевіряючи тип того, що ви вводите.

[!QUESTION]- Hva hvis listen består av både tall og tekst!?

Ні зараз ти задаєш слушне питання! Запитай себе, чи має сенс порівнювати, чи 2 більше за “яблуко”.

Удачі! 😎