DEV Community: Jason Mishike

Recommitting to this blog

Jason Mishike — Thu, 14 Sep 2023 17:19:03 +0000

I am going to attempt to write more in this blog. I'm not sure what I'll write about but I think writing more is beneficial.

Writing helps me refine my thoughts. It's easy to jump from thought to thought in your head. You can't jump away from words on a page, or a screen, the same way; they provide a anchor that shows you what you were last thinking about. Without that anchor its easy to get swept away and never return to the actual point of your initial thought.

Whatever I do decide to write on I want to keep as human as possible. Generative AI is interesting and I would never have expected it to come as far as it has, but I'm writing to better understand my thoughts, not to understand how an AI model processes prompts. That being said, I might use some phrasing or interesting structure from the AI, but I will always absorb it and write it down myself. However I find that I don't like the writing style of AI, it seems to generate a lot of fluff with little substance.

I used to be scared of writing and publishing articles as I felt that there is a chance of being dreadfully wrong, this is a natural feeling to have. However, I have realized, that being wrong is an opportunity to better myself. (I would say I'm only human, but I've been lied to by GPT-4 and copilot so many times I'm not going to). So here is to this post, hopefully the first of many.

P.S. I learnt today that the 12th of September was Programmer's day, so happy programmers day! Fun Fact: Programmer's day can alternate between the 12th and 13th depending on whether it is a leap year or not.

Bubble Sort vs Insertion Sort vs Selection Sort: When and why to use what?

Jason Mishike — Wed, 21 Sep 2022 15:06:57 +0000

(This might seem like a simple topic that is unimportant (most of us probably just use .sort()) but relearning and diving into the nitty-gritty in university was some food for thought and I decided to share that meal.)

On one corner a master of the shuffle, a fighter who keeps things simple but gets the job done, BUBBLE SORT! On the other corner a fighter who is often compared to the Recursives, if he smells weakness he will end it quickly, hailing from stable town here's INSERTION SORT! And on the other(other) corner a fighter who likes to take his time and throw the same punches no matter who he faces, with an battle tested formula and a simple plan here is SELECTION SORT! Let the battle (that one of my lecturers asked for) begin! DING! DING! DING!
This post will mainly deal with when to use what and how they compare against each other. There will be a quick refresher on how they work but if you want implementation details you'll have to look somewhere else.

Quick Refresher

Bubble Sort

The easiest to remember in my opinion, compare values next to each other, if they are not in order, swap, repeat until sorted.

Insertion Sort

In this algorithm there is a sorted sub-array(or section) and an unsorted one, elements of the unsorted sub-array are inserted into their proper place in the sorted side one by one (by comparing from highest to lowest in the sorted sub-array).

Selection Sort

In selection sort you find the lowest value and swap it with the value in the first spot, find the second-lowest and swap it with the value in the second spot, third-lowest to third spot so on until the last element.

The Head to Head

Stability

A sorting algorithm is stable if equal values do not lose their original order when sorted. Illustrated for clarity in the diagram below:

Both Bubble Sort and Insertion Sort are stable, but Selection is not. This is because the order might be jumbled when swapping, as such:

Whether or not you need stability depends on your use-case.

Complexity - The Main Event

This is where the winners and losers are decided. If stability is not a constraint who do you hedge your bets on? There are 2 main measures that determine which is the most (theoretically?) efficient algorithm, comparison and writing complexity.

Comparisons

All the contending algorithms have a worst and average-case comparison complexity of O(n²). Bubble and Insertion Sort has a best-case comparison complexity of O(n) while Selection Sort's best-case is the same as it's worst case at O(n²).
Why is this? If the elements are already or nearly sorted Bubble Sort and Insertion Sort will require less comparisons (Might be helpful to dry run the algorithms with sorted or nearly sorted arrays). This is not the case for Selection Sort where the algorithm doesn't(or can't) care whether elements are already in order, and will treat all elements as unordered.

Writes

Selection sort has a best, average and worst case complexity of O(n) for writes(or swaps), again this is because the algorithm doesn't(or can't) care if elements are in their proper place already. Insertion and Bubble sort have a best case complexity of O(1), average case of O(n²) and a worst case of O(n²) but due to the nature of the algorithm, bubble sort needs around twice the amount of writes as insertion sort in practice (multipliers are not counted in complexity).

Summary (worst case, average case, best case)

Comparisons
Bubble Sort: O(n²), O(n²), O(n)
Selection Sort: O(n²), O(n²), O(n²),
Insertion Sort: O(n²), O(n²), O(n)
Writes
Bubble Sort: O(n²), O(n²), O(1)
Selection Sort: O(n), O(n), O(n)
Insertion Sort: O(n²), O(n²), O(1)

Where to use what

Insertion sort is to be used in most places because it is likely the list will be partially sorted and depending on the situation stability might be required.
But you can use Selection sort if you want to reduce the amount of writes and you don't need the algorithm to be stable.
But what about Bubble sort?

Is it time for Bubble Sort to retire? :(

It is a very popular sorting algorithm and the first one I learnt in school. This is because it is easy to teach and somewhat more "interesting" that selection sort in my opinion. However people have started to advocate to stop teaching this as Insertion sort works better in nearly all cases. Donald Knuth wrote in The Art of Computer Programming, that "the bubble sort seems to have nothing to recommend it, except a catchy name and the fact that it leads to some interesting theoretical problems". Oof. I don't see any disagreement but I did like learning about it even though that might be my nostalgia glasses blurring my mind's eye.

What do you think about bubble sort? Should it be retired, or does it serve a purpose?

Entanglement isn't thaaat spooky - The shoe-box analogy

Jason Mishike — Sun, 17 Jul 2022 10:36:14 +0000

I had to do a bit of research in basic Quantum Computing, when reading about "spooky action at a distance" or entanglement I was intrigued, I though this could be used to transfer information over distances, this seems to be a common misconception, you can read this Forbes article by a Ph.D. astrophysicist to understand why it doesn't work in detail, but I found a helpful analogy. It goes like this.

The Entanglement shoe-box analogy

Assume you have a shoe-box, one of the shoes has been taken and placed at the end of the universe. When you open the shoe-box you observe you have the right shoe, that means the shoe at the other end of the universe is the left one(assuming a normal shoe box). This is how entanglement works. Changing the shoe in the shoe-box in any way has no effect on the shoe that's on the end of the universe, you see the shoe you get the information and that is it. In the article it's said that forcing a state (changing the shoe) would break the entanglement. It is also stated on entanglement that "You know something important about the sum of both states together", or in the shoe-box you know that it should contain both a left and right shoe(normally). :)