Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Programmers can’t write algorithms without help

queworx.com

Post reply on HN
Print view View original

101–105 of 105 posts

Re: Programmers can’t write algorithms without help

#101

Post by eesmith »

dickeytk wrote: post #98
eesmith wrote: post #94

Earlier quoted context omitted.

Now I get to be that guy . Your i only needs to go to n-1, and your j can start with i+1 . More importantly, what you wrote is a selection sort, not a bubble sort! A bubble sort swaps neighboring terms. Eg, if I interpret the code in 2.1 of https://users.cs.duke.edu/~ola/bubble/bubble.html correctly, the 'definitive' version is: for i = n-1..0: for j = 0..i: if arr[j+1]

Fair point. Perhaps it is harder than I thought without looking anything up or testing? At least to get the canonical version written down.

I think it's that "bubble sort" has come to mean "a simple O(N²) sort implementation", of which there are many. But the selection sort just feels more natural than the actual bubble sort. At the very least, selection sort doesn't get my face to scrunch up in a scowl at all those memory movements.

Re: Programmers can’t write algorithms without help

#102

Post by dplgk »

Been a programmer for 20 years and doing the interview dog and pony show for the first time now. Tons of algo questions out there. Apparently memorizing algos is more important than actually knowing how to build an app front and back and knowing how a web browser, http, tcp works. And knowing dev ops and server admin and how to write maintable code. None of that matters as long as you can say which easter basket has the most eggs in O(1) time and constant space.

Re: Programmers can’t write algorithms without help

#104

Post by seba_dos1 »

jcranmer wrote: post #80
seba_dos1 wrote: post #50

Earlier quoted context omitted.

Do you learn algorithms by blindly memorizing their steps? There's nothing to remember in bubble sort, if you know that it "bubbles" by swaping the elements you're already done.

I learn algorithms by memorizing their general structure and filling in gaps using the invariants of the process. A selection sort is pulling the largest elements to the end of the list; an insertion sort sorts the first N elements and inserts the next element; a quick sort picks a pivot to divide the list for sorting; mergesort sorts half the list and then merges them; heap sort heapifies the input (this takes me so…

I don't buy it. Bubble sort is the simplest, the most naive one, you don't even have to remember anything about it.

  do
    sorted = true
    for i = 0 .. n-1:
      if A[i] > A[i+1]:
        A[i], A[i+1] = A[i+1], A[i]
        sorted = false
  while not sorted
That's already a perfectly valid bubble sort. You can then optimize it by noticing that after nth iterations nth elements will already be sorted, and you're done.

If you're trying to recall this algorithm from memory by comparing it with other sorting algorithms you've memorized, you're probably doing it wrong, because there's hardly a place for real world usage of bubble sort, so your memory of it is naturally going to fade away. The trick is - you don't even need to memorize it or recall any structure to fit it into. Just imagine an inefficiently bubbling array of numbers in your head and that's it.

Re: Programmers can’t write algorithms without help

#105

Post by seba_dos1 »

dragontamer wrote: post #77
seba_dos1 wrote: post #50

Earlier quoted context omitted.

Do you learn algorithms by blindly memorizing their steps? There's nothing to remember in bubble sort, if you know that it "bubbles" by swaping the elements you're already done.

The main "issue" I have is that if you write a "bubble" sort backwards, then its suddenly insertion sort instead and much more efficient. For people who know about knots out there... its like asking for somebody to tie a Granny Knot instead of a square-knot. Anyone who actually practiced knot-tying will "accidentally" tie a square-knot instead (because the square-knot is stronger for the same level of effort). Simila…

I'm pretty sure the original meaning of "I can't even write bubble sort on a whiteboard" wasn't "I would accidentally write a more efficient algorithm instead" ;)
Post reply on HN