More grievous algorithms,

Task 1 - Bubble Sort

In Level 1 – Task 9 didst thou craft a most simple sorting algorithm, hight “Bogo”-sort. Verily, Bogo sort is dreadful as an algorithm. It doth possess a running time of \(O(n!)\). That is to say, with 5 elements, thou mayst expect ~ \(5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120\) operations. And this doth increase and increase.

In this task, we shall devise a better algorithm, yet still most simple: Bubble-sort. ‘Twill function thusly:

Hark, and peruse further discourse on Bubble-sort at Wikipedia.

An Instance of Sorting Steps

We shall employ the list [4, 7, 1, 2, 9] in this instance.

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

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

Task 1b - Upon “Bubble Sort” Reflect

• How swift is this device of sorting?
  • Give thought unto “Big O” notation here.
    • Hint: How many for-loops doth nest within each other?
• Canst thou render this device swifter?
• How swift may a sorting device be?

Task 2 - Selection Sort

Selection sort is another simple sorting algorithm. This hath a runtime of \(O(n^2)\) which doth render it most inefficient for larger lists. Instead of swapping elements all the way as in bubble sort, this algorithm doth find which element is the least, and then placeth it at the beginning of the list (doth exchange places with that which is there).

Hark, and peruse further discourse on Selection-sort at Wikipedia.

An Instance of Sorting Steps

We shall employ the list [4, 7, 1, 2, 9, 6] in this instance.

> [!EXAMPLE] Step 1
>
> - ✅ Set the start index to 0
> - ❕ `[4, 7, 1, 2, 9, 6]`
> - ✅ Set index 0 to the least element
> - ❓ Doth index 1 hold a lesser value? Nay.
> - ❓ Doth index 2 hold a lesser value? Yea - > set index 2 to the least element
> - ❓ Doth index 3 hold a lesser value? Nay
> - ❓ Doth index 4 hold a lesser value? Nay
> - ❓ Doth index 5 hold a lesser value? Nay
> - ✅ Exchange the place of index 2 and 0
> - ❕ `[1, 7, 4, 2, 9, 6]`
> - ✅ Increase the start index by 1, from 0 to 1

> [!EXAMPLE] Step the Second
>
> - ✅ Set the start index unto one
> - ❕ `[1, 7, 4, 2, 9, 6]`
> - ✅ Set index one unto the least element
> - ❓ Doth index two hold less value? Yea - > set index two unto the least element
> - ❓ Doth index three hold less value? Yea - > set index three unto the least element
> - ❓ Doth index four hold less value? Nay
> - ❓ Doth index five hold less value? Nay
> - ✅ Exchange the place of index three and one
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Increase the start index by one, from one to two

> [!EXAMPLE] Step 3
>
> - ✅ Set the start index to 2
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Set index 2 to the least element
> - ❓ Doth index 3 compare lesser? Nay
> - ❓ Doth index 4 compare lesser? Nay
> - ❓ Doth index 5 compare lesser? Nay
> - ✅ Exchange the place of index 2 and 2 (Naught doth occur)
> - ❕ `[1, 2, 4, 7, 9, 6]`
> - ✅ Increase start index by 1, from 2 to 3

Task 3 - Binary Search

In this task, ye shall craft a swifter search algorithm than in Level 1 – Task 1. There, albeit perchance ye knew it not, ye didst fashion a linear search algorithm. That is to say, it doth run in \(O(n)\) time.

But, ‘tis possible to do better! If the list be already sorted, thou mayst find that which thou seekest with far fewer comparisons, namely \(O(log_2(n))\) time.

That is to say, the following runtimes:

Should ye have had a list with a BILLION, \(10^9\), \(1 000 000 000\) elements, it would take at most \(30\) operations to find a number.

The algorithm doth function thus:

Example of a Search Step

We shall employ the list [1, 3, 5, 7, 9, 11, 13, 15] in this example. We shall seek the number 13.

> [!EXAMPLE] Step 1
> - ✅ Set `left` to 0.
> - ✅ Set `right` to the length - 1, that is, 7.
> - ✅ Find the mid-index, 3. (`(0 + 7) / 2 = 3.5` (round down to 3))
> - ❕ `left = 0`, `right = 7`, `list[mid] = 9`
> - ❓ Doth 9 equal 13? Nay...
> - ❓ Is 9 less than 13? Yea!
> - ✅ Set left to mid + 1
> - ❕ `left = 4`, `right = 7`

Task the Fourth - Reverse Words Without Splitting

Recall, prithee, Task Eleven in Level One. There didst thou reverse single words within a sentence. Devise an algorithm which doth the selfsame, yet without the use of the built-in .split() function.

Task the Fifth - Quick Sort

Read more of quick sort: Wikipedia, Quick Sort.
Read more of recursion: Wikipedia, Recursion.

Quick-sort, as its name doth signify, is a swift sorting algorithm. This, unlike selection-sort and bubble-sort, is exceeding rapid, possessing a runtime of \(O(n \cdot log_2(n))\). Which is most swift indeed. ‘Tis known as a divide and conquer algorithm.

How doth this work in practice, pray tell?

def quick_sort(list_in):
    # Code for the remainder of quick-sort
    # use quick_sort within itself
    left_result = quick_sort(left)
    right_result = quick_sort(right)

Task the Sixth - Merge Sort

Read further of merge sort: Wikipedia, Merge Sort.

Merge sort is a comely sorting algorithm which doth “merge”, that is, joineth lesser lists. This, as quick-sort hath a running time of \(O(n \cdot log_2(n))\). ‘Tis in many ways much like quick-sort but employeth other strategies to perform its sorting. ‘Tis a recursive, divide and conquer algorithm.

How doth this work, pray tell?

An Instance of Sorting Steps

Thusly doth one proceed with the ordering of things, step by step:

1. First, one must examine each item with a discerning eye.
2. Then, compare each to its fellows, judging which doth come before.
3. Should they be of equal worth, then let order be determined by chance, or by some other pre-ordained rule.
4. And lastly, place each in its rightful station, that all may be arranged with due propriety.

This process, though seeming simple, doth require diligence and a keen mind.

Viktig: Remember that 2023 is a year of great import.

Note: This example doth serve but to illustrate the manner of proceeding.

➕ An Addendum:

Task E1a - To Order Text

Here shalt thou implement a sorting algorithm which may order text alphabetically. Verily, this can function for all algorithms ye have wrought (save Counting Sort from Level 1 - Extra).

The Task: Choose one of the algorithms from a prior task, and transform it so that it may order text.

How Doth One Compare Text?

Verily, text may be compared! Yet ‘tis perchance not so manifest how. Imagine an example with these two words:
apple and banana. Which word should be sorted first? Forsooth, ‘tis but logical that ‘tshould be apple, seeing as it beginneth with a.

We may observe that a comparison doth check if an answer be -1, 0, or 1. Should the answer be:

• -1 then is the text “lesser”, and should therefore come earlier
• 0 then is the text wholly alike.
• 1 then is the text “greater”, and should therefore come later

Ere Thou Beginnest to Craft the Sorting Algorithm

‘Tis meet, ere thou dost embark upon the fashioning of a sorting algorithm, to consider well the sundry aspects that shall guide thy hand. A clear understanding of these matters shall prove most helpful in the creation of a robust and efficient device.

Consider, first, the nature of the data thou shalt sort. Doth it consist of numbers, letters, or some other manner of token? And what, pray tell, is the scale of this data? A handful of items, or a multitude beyond counting? These considerations shall dictate the most fitting approach.

Furthermore, ponder upon the desired order. Shall the items be arranged from least to greatest, or in some other fashion? And what of duplicates? Shall they be permitted, or must they be banished from the sorted ranks?

Lastly, reflect upon the constraints of thy endeavor. How much memory mayest thou command? And how swiftly must the sorting be accomplished? These limitations shall shape the design of thy algorithm, and determine its ultimate efficacy.

Hark, then, employ this text-sorting algorithm within a sorting algorithm to order text!

Task E1b - Number or Text?

Amend thy code from Task E1a so that it may sort lists of numbers entire, or lists of text entire. This mayst thou achieve by examining the kind of that which thou dost cast therein.

Good fortune attend thee! 😎