The appeal of bubble sort for me is that is it the only one I understand well enough to implement myself without having to think much about it.

▲ somat 11 hours ago | parent | next [-]

For me it's lsb radix, Yeah I know it only works on numbers, but much younger me independently invented it when slinging 3480 mainframe tape as a grave shift operator. The company had invested in mainframes early and by the time I had got there was was slightly disfunctional, they still had mainframe operators and we would run the nightly batch jobs to process orders. While they had a hard drive(the ramac) they never liked to update their programs to use it, so every major step of the process would read a tape and write a new tape(they used the tapes sort of like a massively inefficient version control, so the process could be restarted at any point) at the end of the night we would have to file a couple hundred tapes back in the library. As I hated randomly seeking through the library and was bad at ad hock sorting I put together a manual sorting routine so the numbered tapes could go back in order. What ended up working best for me I found out later was the good ol' LSB radix sort and I have a soft spot for it to this day.

▲ bxparks 19 hours ago | parent | prev | next [-]

I read this all the time from other people, but for me, Selection sort is the easiest to remember and implement. My next easiest would be Insertion sort.

Bubble sort doesn't click for me easily. I think it's because the terminating condition seems uglier than Selection sort or Insertion sort. I always have a little voice in the back of my mind, "Is this outer loop guaranteed to terminate?"

▲ archargelod 18 hours ago | parent [-]

Terminating condition in Bubble sort is "did we swap any values during this loop"? Yes -> continue, No -> list is already sorted, exit the loop.

I don't believe that insertion/selection sort is easier to grasp. Can you type it from memory, without looking it up? Here's bubble sort:

    var swapped = true
    while swapped:
      swapped = false
      for i in 0 .. list.len-2:
        if list[i] > list[i+1]:
          swap(list[i], list[i+1])
          swapped = true

▲ bxparks 5 hours ago | parent | next [-]

Different strokes for different folks I guess.

Selection sort was the first sorting algorithm that I ever created: Find the smallest element for slot #1. Find the next smallest for slot #2. And so on. I've recreated it from scratch many times. The double for-loop means that it is guaranteed to finish, and it is obviously O(N^2).

I did not learn about Bubble sort until my university class, where I thought, this is a terrible algorithm: It's not completely obvious that it will finish, and it's not obvious what the runtime complexity is. For example, if the inner loop used ">=" instead of ">", it would work for test data sets with unique elements, then hang forever with a real data set that contained duplicates.

▲ jeltz 8 hours ago | parent | prev | next [-]

Let's see.

  for i in 1 .. list.len - 1:
    j = i - 1
    while j >= 0 and list[j] > list[j + 1]:
      swap(list[j], list[j + 1])
      j = j - 1

▲ minitech 18 hours ago | parent | prev [-]

> Can you type it from memory, without looking it up?

Well, yeah, but that’s not a very useful heuristic for people who are already aware of the algorithms in question. If you ask people to come up with a way from scratch – probably without explicitly asking, in order to get better success, like by watching how they sort cards – I bet they won’t tend to come up with bubble sort. Maybe that says something about the relative intuitiveness of the approaches? Or not.

▲

3eb7988a1663 17 hours ago | parent [-]

I recall "inventing" bubble sort during one of my first CS classes when the question was posed of how to sort a list. So, not that outlandish.

	▲	avmich 14 hours ago \| parent [-]
		Agree. I remember the names of many of these algorithms, but not the logic.

▲ hmng 11 hours ago | parent | prev | next [-]

As others have said, it is easy enough for a child in the 80s, with only a BASIC manual to come up with it. Been there, done that. Didn't even had a name for it. Later I read a magazine explaining several algorithms and found the name of what I had implemented.

For the curious, the ZX Spectrum microdrive listed files on the cartridges by order found on tape. I wanted to display it in alphabetical order like the "big" computers did.

	▲	JKCalhoun 4 hours ago \| parent [-]
		Ha ha, yeah, it was in high school, in BASIC, on an Apple II that I learned how to write a bubble sort.

▲ another_twist 11 hours ago | parent | prev | next [-]

Merge and Quicksort are good ones too. Quicksort esp since the idea has a flavour of "I could come up with that". Its a beautiful algorithm.

▲ ExtremisAndy 20 hours ago | parent | prev | next [-]

I felt this comment in my soul. I’ll never understand it: I’ve written thousands of lines of code (as a hobbyist) to solve all sorts of problems I’ve run into and yet always seem to struggle to wrap my mind around the core algorithms any real developer should be able to handle easily. This is why I’ve never pursued programming as a career.

▲

vbezhenar 19 hours ago | parent | next [-]

It took computer scientists of the past, a lot of effort to come up with these complicated algorithms. They are not easy or trivial. They are complicated and that's OK that you can't just quickly understand them. Your imaginary "real developer" at best memorised the algorithms, but that hardly differs from smart monkey, so probably not something to be very proud of.

It is your choice which career to pursue, but in my experience, absolute majority of programmers don't know algorithms and data structures outside of very shallow understanding required to pass some popular interview questions. May be you've put too high artificial barriers, which weren't necessary.

To be a professional software developer, you need to write code to solve real life tasks. These tasks mostly super-primitive in terms of algorithms. You just glue together libraries and write so-called "business-logic" in terms of incomprehensible tree of if-s which nobody truly understands. People love it and pay money for it.

▲

melagonster 19 hours ago | parent [-]

Thanks for your kind comment! I do not have any systematic leaning of computer science; I often feel confused when reading textbooks on algorithms hahaha.

Should I be familiar with every step of Dijkstra’s search algorithm and remember the pseudocode at all times? Why don’t the textbooks explain why the algorithm is correct?

▲

monadgonad 12 hours ago | parent | next [-]

> Should I be familiar with every step of Dijkstra’s search algorithm and remember the pseudocode at all times?

Somehow, I think you already know the answer to that is "no".

I've been working as a software engineer for over 8 years, with no computer science education. I don't know what Dijkstra's search algorithm is, let alone have memorised the pseudocode. I flicked through a book of data structures and algorithms once, but that was after I got my first software job. Unless you're only aiming for Google etc, you don't really need any of this.

	▲	chopin 9 hours ago \| parent [-]
		You should know the trade-offs of different algorithms, though. Many libraries let you choose the implementation for a spcific problem. For instance tree vs. hash map where you trade memory for speed.

▲

minitech 16 hours ago | parent | prev [-]

> Why don’t the textbooks explain why the algorithm is correct?

The good ones do!

> Should I be familiar with every step of Dijkstra’s search algorithm and remember the pseudocode at all times?

If it’s the kind of thing you care to be familiar with, then being able to rederive every step of the usual-suspect algorithms is well within reach, yes. You don’t need to remember things in terms of pseudocode as such, more just broad concepts.

▲

mamcx 17 hours ago | parent | prev [-]

Something that helps, I think, is to make something practical that demands it.

I used to think alike (I'm +30 year programing) until I decide to do https://tablam.org, and making a "database" is the kind of project where all this stuff suddenly is practical and worthwhile.

▲ tzs 19 hours ago | parent | prev | next [-]

That surprises me. Selection sort seems like it should be easier to understand than bubble sort.

	▲	JKCalhoun 4 hours ago \| parent [-]
		I haven't investigated selection sort. You have me curious though. Is that a step down from bubble sort? If so, maybe it's just as well I figured out bubble.

▲ strken 20 hours ago | parent | prev | next [-]

I understand merge sort enough to just jump in and write it. It does require a little more space and thought than bubble sort, though.

▲ vlovich123 20 hours ago | parent | prev | next [-]

Insertion sort and radix sort are also quite easy to understand, perhaps even more so.

▲ anothernewdude 19 hours ago | parent | prev [-]

Perhaps a sign of the trauma from university, but for me that's quicksort.