Merge sort question Computer Science

Merge sort question
I wrote an iterative method for calculating Fibonacci numbers using only one if-statement, is it possible to have zero?
Why is my own implementation of Bubble Sort so much slower than another one I found online?
Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve | Quanta Magazine

Posted: 24 Jun 2018 01:08 AM PDT

I'm a high school teacher currently marking some simple student work. One of the tasks I set is for them to demonstrate how a merge sort would sort a simple list of 16 numbers. I have always understood this (and taught) that it's a divide and conquer algorithm, where you first split the list in half and half again until you get lists of single values, then start merging these lists together until the whole list is sorted. So in terms of size of lists at each stage it would go 16, 8, 4, 2, 1, 2, 4, 8, 16. This seems to be backed up by YouTube videos and textbooks.

However, I'm now doubting myself. A lot of students (and I mean a LOT, in different classes that don't know each other) seem to be splitting down to the stage of the lists being size 2, then magically sorting this list, then continuing as normal to merge.

I would normally just mark it (or that part of it) as wrong and move on, but the fact that so many of them are doing the same thing makes me think there is some resource out there that does it this way. Is it wrong?

(Thanks!)

submitted by /u/Gavcradd
[link] [comments]

I wrote an iterative method for calculating Fibonacci numbers using only one if-statement, is it possible to have zero?

Posted: 23 Jun 2018 07:10 AM PDT

The following is my Java-code.

private static int iterativeFibonacci(int n) { if (n==0) return 0; int prevPrev = 1, prev = 0, result = 0; for (int i = 0; i < n; i++) { result = prev + prevPrev; prevPrev = prev; prev = result; } return result; }

Is it possible to have zero if-statements? Of course you could use a switch, but that doesn't count.

Edit: thanks, it does work without the first if-statement like so:

private static int iterativeFibonacci(int n) { int prevPrev = 1, prev = 0, result = 0; for (int i = 0; i < n; i++) { result = prev + prevPrev; prevPrev = prev; prev = result; } return result; }

Sometimes the answer is already there ;)

submitted by /u/a-random-nerd
[link] [comments]

Why is my own implementation of Bubble Sort so much slower than another one I found online?

Posted: 23 Jun 2018 11:02 AM PDT

I wrote my implementation of Bubble Sort according to my understanding of the general principle of how the algorithm works, and then compared it against another implementation I found online.

def my_bubble_sort(n): switched = True while switched: switched = False for i in range(1, len(n)): if n[i] < n[i - 1]: switched = True n[i - 1], n[i] = n[i], n[i - 1] return n def some_other_bubble_sort(n): for i in range(len(n) - 1): for j in range(len(n) - 1 - i): if n[j] > n[j + 1]: n[j], n[j + 1] = n[j + 1], n[j] return n

While my_bubble_sort() is much faster on processing lists that are already sorted, some_other_bubble_sort() is almost three times faster (= takes 35% of the time) compared to my_bubble_sort() on actually random, unsorted lists.

I'm not sure why that is. Can anyone help me understand?

It can't be the additional checks against switched that make my implementation that much slower, can it?

Pastebin link

submitted by /u/chris_offner
[link] [comments]

Finally, a Problem That Only Quantum Computers Will Ever Be Able to Solve | Quanta Magazine

Posted: 23 Jun 2018 11:45 AM PDT

submitted by /u/pastermil
[link] [comments]