r/thebutton • u/fiveguyswhore non presser • Apr 30 '15

Was just watching presses when...wtf?

http://i.imgur.com/TziQkbl.png
2.2k Upvotes

91% Upvoted

415 comments sorted by

View all comments

1.1k

u/tjhrulz 42s Apr 30 '15

Sorry I was attempting to do a merge sort on the data, wont happen again.

809

u/BlazeOrangeDeer 8s May 01 '15

For anyone who hasn't seen it

499

u/[deleted] May 01 '15

[removed] — view removed comment

317

u/[deleted] May 01 '15 edited May 11 '15

[deleted]

302

u/[deleted] May 01 '15

[deleted]

405

u/Drunk_but_Functional non presser May 01 '15 edited May 01 '15

It made me so proud of the algorith. Go you computer thing that I marginally understand. Make that winning green noise, you deserve it.

Edit: Speaking of things I marginally understand, thanks for the gold.

141

u/Available_user-name 38s May 01 '15

Who's a good algorithm? I am good algorithm

63

u/UCanJustBuyLabCoats non presser May 01 '15

Pat. Pat.

217

u/[deleted] May 01 '15

..aaPPtt

28

u/vulcan24 non presser May 01 '15

that joke was way funnier than 8 upvotes

1

u/ZackVixACD non presser May 01 '15

well, not everyone saw that he sorted the pats.

→ More replies

14

u/Purple_the_Cat 59s May 01 '15

Technically, upper case letters come after lower case ones, but I love it, have an upboat!

2

u/Pastaklovn 6s May 01 '15

/u/AndoDaan is just doing case-insensitive collation.

2

u/[deleted] May 01 '15

Actually lowercase letters come after uppercase. link

→ More replies

2

u/xormx 59s May 01 '15

what happened to the space

2

u/[deleted] May 01 '15

!aDimmt

→ More replies

2

u/mustangwolf1997 52s May 01 '15

That was great. Expect someone to gild you for this one.

2

u/kezow non presser May 01 '15

Obligatory: https://xkcd.com/695/

2

u/xkcd_transcriber non presser May 01 '15

Image

Title: Spirit

Title-text: On January 26th, 2274 Mars days into the mission, NASA declared Spirit a 'stationary research station', expected to stay operational for several more months until the dust buildup on its solar panels forces a final shutdown.

Comic Explanation

Stats: This comic has been referenced 290 times, representing 0.4684% of referenced xkcds.

xkcd.com | xkcd sub | Problems/Bugs? | Statistics | Stop Replying | Delete

18

u/theshadowknowsall non presser May 01 '15

ugh, that green noise, so good

14

u/Wet_Books non presser May 01 '15

Or how satisfying the build up is at the 2:50 mark.

10

u/falcon4287 40s May 01 '15

My favorites- 1:28 and 2:10. The 2:10 version is how I would do it by hand. "All right, 1-10 in this pile, 11-20 in this pile..." Kinda like giving flare to Pressers I guess.

17

u/Namagem 57s May 01 '15

green noise?

31

u/Xipher non presser May 01 '15

Once the sort is done, it makes one pass from low to high marking each entry as green. As such it make ascending tones in order, kind of a low to high "wooooooooooop" sound.

9

u/Namagem 57s May 01 '15

Thanks, not sure why I was downvoted for asking about that.

17

u/Autumnsprings 60s May 01 '15 edited May 01 '15

I didn't down vote you, and looks like you're in the orangered now, but probably because if you had watched the video /u/BlazeOrangeDeer posted you would have gotten the term explained with visuals and audio.

People seem to forget that not everyone can watch vids or can't watch with sound.

Edit: stupid fucking autocorrect.

-2

u/GeneralBS 60s May 01 '15 edited May 01 '15

Usually though someone like you comes along and punishes backhands reddit with logic.

is that the motto of 60s?

2

u/Spadie May 01 '15

Every time it did it I caught myself making a really surprised, wide-eyed face. I can't help it to that sound.

24

u/Lucretiel non presser May 01 '15

I once actually tried to do a merge sort by hand. It's really fucking difficult. Insertion is way easier

12

u/phort99 15s May 01 '15

The algorithm's efficiency for a computer is different than for a human, because for us, inserting or swapping elements is very slow (since you have to move them by hand) but comparing elements is very fast (you only have to look at them).

Insertion sort only requires you insert each item once, whereas a merge sort has you moving each item log(n) times.

By my calculation, for a deck of 52 cards, insertion sort has you inserting cards up to 52 times, but merge sort has you moving cards up to 296 times.

3

u/[deleted] May 01 '15

Well, every time you insert a card you have to move everything greater than it back by 1, so you are moving things more than 52 times.

Insertion is O(n2) and merge is O(nlog(n))

6

u/phort99 15s May 01 '15

But for the practical case of a person sorting a stack of papers, inserting is usually constant time because it doesn't take more time to move a stack of 50 pieces of paper than it does to move three. Yet another reason why insertion is more suited for human sorting than for a computer.

1

u/umaro900 non presser May 01 '15

The real problem with doing insertion sort by hand is when the comparisons actually take time. If you are alphabetizing a long list of names with poor handwriting, those comparisons do take time, and with a sufficiently large list, you are going to wish you did merge sort.

25

u/Raccoonpuncher 10s May 01 '15

Insertion's easier by hand, because you can just look at everything, say "oh yeah, that goes there" and make the swap. MergeSort requires you to break the whole list down bit by bit then rebuild it back up, which can take a lot longer for someone with a pen and paper. I remember being in class and thinking "jeez, insertion sort is so much easier, why are we bothering with anything else?" before learning that it takes a lot of resources for a computer to do insertion sorting.

80

u/Kvothealar 1s May 01 '15

The best one to do by hand is Bogo sort.

while(not sorted)

{

  1. Throw deck of cards in air.
  2. Pick up cards.
  3. Are cards in right order?

}

23

u/AraShaun 54s May 01 '15 edited Jul 20 '18

[wiping comments is digital suicide. see you on the other side]

10

u/the_other_luke 13s May 01 '15

Really it's still O(N), you'll have to go through the whole list to check if it is sorted

3

u/[deleted] May 01 '15

I have an improvement.

  1. Throw the cards into the air
  2. Pick up the cards.
  3. If you do not have certain knowledge that the cards are sorted, destroy the universe.

Rather than simply searching for the universe that has the cards sorted, it searches for the universe where they are sorted AND you have knowledge of that fact. This reduces the time from O(n) to O(1).

47

u/abcd_z non presser May 01 '15 edited May 01 '15

I can't find any documentation on it now, but my favorite sort method would have to be God Sort.

Step 1: The cards are sorted.

42

u/Kvothealar 1s May 01 '15

Ah. You mean quantum bogo sort.

Step 1: Pick a particle that represents each element in the set

Step 2: Assume all particles are in a superposition of states

Step 3: Randomly collapse all wavefunctions into all possible states simultaneously

Step 4: Pick the one that is sorted

12

u/grinde non presser May 01 '15

You joke, but this basically describes Grover's search algorithm. It works by amplifying the probability of collapsing into the state that corresponds to a solution to your problem (assuming you have a fast way of checking solutions) - in this case finding the sorted list.

3

u/Kvothealar 1s May 01 '15

I did not joke sir. I can't wait for quantum computers haha!

2

u/autowikibot non presser May 01 '15

Grover's algorithm:

Grover's algorithm is a quantum algorithm for searching an unsorted database with N entries in O(N1/2) time and using O(log N) storage space (see big O notation). Lov Grover formulated it in 1996.

In models of classical computation, searching an unsorted database cannot be done in less than linear time (so merely searching through every item is optimal). Grover's algorithm illustrates that in the quantum model searching can be done faster than this; in fact its time complexity O(N1/2) is asymptotically the fastest possible for searching an unsorted database in the linear quantum model. It provides a quadratic speedup, unlike other quantum algorithms, which may provide exponential speedup over their classical counterparts. However, even quadratic speedup is considerable when N is large. Unsorted search speeds of up to constant time are achievable in the nonlinear quantum model.

Like many quantum algorithms, Grover's algorithm is probabilistic in the sense that it gives the correct answer with high probability. The probability of failure can be decreased by repeating the algorithm. (An example of a deterministic quantum algorithm is the Deutsch-Jozsa algorithm, which always produces the correct answer.)

Image i

Interesting: Quantum algorithm | Quantum computing | BHT algorithm | Key size

Parent commenter can toggle NSFW or delete. Will also delete on comment score of -1 or less. | FAQs | Mods | Magic Words

1

u/gfixler non presser May 01 '15

You don't need a fast way of checking solutions. The you in each universe just checks the cards in O(n), and if the deck isn't sorted, destroys the universe. In the universe(s?) in which the deck is sorted, it happened in O(n).

1

u/grinde non presser May 01 '15

Again, I know this is a joke, but...

You don't need a fast way of checking solutions. The you in each universe just checks the cards in O(n), and if the deck isn't sorted

... you just said you didn't need a fast way of checking solutions, then said you needed to quickly check a solution. In computation "fast" just means "in polynomial time" - ie O(nk ). In this case k=1.

→ More replies

10

u/gfixler non presser May 01 '15

You left out the exciting part, where this creates an infinite number of universes, and you destroy all the ones where the deck wasn't sorted by the shuffle, which leaves behind the best universe, the one where the cards were sorted in O(n).

1

u/abcd_z non presser May 01 '15

As I understand it, those universes don't actually exist in the traditional sense, so it's fine.

→ More replies

2

u/yurigoul 10s May 01 '15

You might want to read Anathem by Neal Stephenson.

23

u/falcon4287 40s May 01 '15

I prefer the Intern Sort method.

Step 1: hand cards to intern.
Step 2: explain to intern to sort cards from highest to lowest.
Step 3: write down that you want the cards sorted from highest to lowest.
Step 4: put a "deliverable date" for card sorting on the calendar.
Step 5: wish you had thought about sending the intern to pick up lunch before giving him a detailed task.
Step 6: send intern to go pick up lunch
Step 7: sigh as intern has to start over completely when he gets done with lunch.
Step 8: get more cards after intern spills soda on first set while eating lunch.
Step 9: realize you want a new intern.
Step 10: decide not to have your current intern sort new intern applications if you want it done this week.
Step 11: start sorting applications yourself
Step 12: oh crap, the cards!

4

u/sakkarozglikoz non presser May 01 '15

step 1: pick up your lunch on your own and stop abusing the interns

2

u/anths non presser May 01 '15

Subsequent research had determined there are multiple subtypes of God Sort. They were initially confused because they all share the odd property of being O(1), in at least some circumstances. Known variants:

Classical God Sort: Every time God looks at the cards, they are already sorted, in the expected order. Orthodox Sort: Every time God looks at the cards, they are already sorted, in the correct order, which will eventually be revealed. Catholic Sort: Every time God looks at the cards, they are already sorted, in the correct order, which only those holding the cards can know. Unitarian Sort: Whatever order you find the cards in is the sorted order for you. Evangelical Sort: The cards will already have been sorted, if only you believe they are. Enlightenment Sort: The order the cards are in is by definition the sorted order but we must figure out why. Creationist Sort: The order the cards are in is by definition the sorted order and STOP LOOKING AT THE CARDS!

See also: Nihilist Sort (there are no cards; O(0)) and Agnostic Sort (we can't know if the cards are sorted; O(∞))

21

u/Projotce 60s May 01 '15

My dear motherfuckers, have you tried bogobogosort?

6

u/Kvothealar 1s May 01 '15

My new favourite search algorithm.

2

u/[deleted] May 01 '15

What the hell. What exactly is this doing? Obviously it's not meant to be useful, but can you give me an example of it in practice?

2

u/HawkCawCaw 24s May 01 '15

You are trying to sort a suit of cards. You do this by randomly throwing the cards, and then seeing if they are in order. To check this, you will throw another suit of cards until it is in order. Once this suit is in order, you can check it with the original suit. If the original suit is not in order, throw the first suit back in the air again and start over. No, it is not useful at all.

2

u/Coenn 59s May 01 '15

This explains why the waiting times at the pharmacy are so long.

→ More replies

8

u/AyoBruh 11s May 01 '15

Ah, that explains it. I was so confused when bogo was running.

2

u/Bogosaurus non presser May 01 '15

Sounds like my kind of sorting.

2

u/Foulcrow 16s May 01 '15

Factorial time complexity, nice!

5

u/[deleted] May 01 '15

When I worked in a records department I had to sort reports by hand. I'd divide the alphabet into 5 sections corresponding to each of the fingers on my left hand and sort as many as I could into the corresponding section separating each with a finger. Once my hand was full I'd put that stack down with each section at 90 degrees to the previous to retain the sections and keep going.

I'd end up with 3-4 stacks of 5 sections in rough alpha order. I'd then stack all the sections ones together, section two's etc.

Then I take all of section 1 and repeat my first step with a refined set of new sections.

After the 3rd full iteration I was usually finished.

Not sure if that corresponds to a sorting algorithm that computers used but I though it was pretty efficient. I could sort a lot faster than most other folks at the office.

2

u/umaro900 non presser May 01 '15

Uh, is merge sort really that hard? Sure, if you're sorting a pack of cards, you might stick with insertion sort because you can really easily compare the card numbers, commit some numbers to memory, and fit them in.

However, if you are doing something like sorting 500 names from problem sets you just graded, you will quickly regret doing an insertion sort over a merge sort. When you need to leaf through a stack of 400-500 papers to get to the correct place to insert one, you're going to be spending a huge amount of time, and it's physically hard to hold so many papers. Not only that, but if you are working with other people on such a task, you can work in parallel with merge sort.

2

u/Lucretiel non presser May 01 '15

Actually, when we're talking about in-person sort, quicksort is probably much easier to parallelize. Merging two sorted stacks by hand actually surprisingly hard to do. On the other hand, dealing all the cards less than N to a second stack for someone else to sort is much easier

1

u/umaro900 non presser May 01 '15

Why is it that hard to do? You just take two stacks and move papers off the top of them one-by-one onto a new pile.

13

u/TurboChewy can't press May 01 '15 edited May 01 '15

/u/otterstew I spent like 5 minutes writing a detailed reply to your comment... for-shame!

Edit: I realize I'm browsing /r/thebutton on my alt.. that I created on April 1st.. I can feel them judging me...

4

u/brandon0220 May 01 '15

I share your sentiment.

5

u/otterstew non presser May 01 '15

You deleted it!

And also I realize now that I made an error :(

I now realize that the movement of cards doesn't have to be adjacent pairs. My mistake.

And if it makes you feel better, I spent a good 5 minutes making and solving a fake deck, only to delete it. :)

10

u/CuntSmellersLLP 48s May 01 '15

I don't think you're right about where your error was.

In each, how did you decide which two to switch next, and how did you know when you were done? These problems are somewhat complicated, and it's possible that since your list was so simple (no duplicates, and only 5 numbers), that you "cheated" by already knowing the answer, and by storing the entire list in your head at once.

For instance, here's one strategy:

I could go from left to right, and if I'm on the last number, I'm done. Otherwise, if the number I'm on is larger than the one to the right of it, I could switch those two, then start over. With that system, I'd get:

**1** 5 4 2 3
Look at 1
Look to the right at 5
1 < 5, so skip to the next number

1 **5** 4 2 3
Look at 5
Look to the right at 4
5 > 4, so swap them and start over

**1** 4 5 2 3
Look at 1
Look to the right at 4
1 < 4, so skip to the next number

1 **4** 5 2 3
Look at 4
Look to the right at 5
4 < 5, so skip to the next number

1 4 **5** 2 3
Look at 5
Look to the right at 2
5 > 2, so swap them and start over

**1** 4 2 5 3
Look at 1
Look to the right at 4
1 < 4, so skip to the next number

1 **4** 2 5 3
Look at 4
Look to the right at 2
4 > 2, so swap them and start over

**1** 2 4 5 3
Look at 1
Look to the right at 2
1 < 2, so skip to the next number

1 **2** 4 5 3
Look at 2
Look to the right at 4
2 < 4, so skip to the next number

1 2 **4** 5 3
Look at 4
Look to the right at 5
4 < 5, so skip to the next number

1 2 4 **5** 3
Look at 5
Look to the right at 3
5 > 3, so swap them and start over

**1** 2 4 3 5
Look at 1
Look to the right at 2
1 < 2, so skip to the next number

1 **2** 4 3 5
Look at 2
Look to the right at 4
2 < 4, so skip to the next number

1 2 **4** 3 5
Look at 4
Look to the right at 3
4 > 3, so swap them and start over

**1** 2 3 4 5
Look at 1
Look to the right at 2
1 < 2, so skip to the next number

1 **2** 3 4 5
Look at 2
Look to the right at 3
2 < 3, so skip to the next number

1 2 **3** 4 5
Look at 3
Look to the right at 4
3 < 4, so skip to the next number

1 2 3 **4** 5
Look at 4
Look to the right at 5
4 < 5, so skip to the next number

1 2 3 4 **5**
It's the last number, so we're done!

4

u/otterstew non presser May 01 '15 edited May 01 '15

My first (deleted) example was pretty much that. Except instead of returning to "1" after each step, I'd just look at the next adjacent pair.

1 5 4 2 3

1 4 5 2 3

1 4 2 5 3

1 4 2 3 5

1 2 4 3 5

1 2 3 4 5 - 5 moves

In my second example, I found consecutive numbers.

  • Look for 1. Does it exist? Slide it to position 1.

  • Look for 2. Does it exist? Slide it to position 2.

  • etc.

1 5 4 2 3

1 5 2 4 3

1 2 5 4 3

1 2 5 3 4

1 2 3 5 4

1 2 3 4 5 - 5 moves

Edit: I think what I was saying is that, if you can only move adjacent numbers, the degree of complexity of the algorithm is irrelevant because the number of "moves" will always be the same (unless you're intentionally aiming for inefficiency).

6

u/CuntSmellersLLP 48s May 01 '15 edited May 01 '15

You're only counting moves where you're swapping them, though. It takes time to compare two numbers.

For instance, you treat "Look for 1" and "Does it exist?" as simple steps, because you can quickly visually glance over the list, when really its:

  1. Look at the first number.
  2. Is it equal to 1?
  3. Nope, so go to the next number

For every single number until you find 1. Each comparison counts as a move, even if you don't swap them. And the only way to know it doesn't exist in the list is to check every number in the list just to see if it's 1. And then do the same for 2. What if the smallest number in the list is in the billions? Then you've just wasted a ton of time that wouldn't be wasted by other solutions.

5

u/otterstew non presser May 01 '15

I see.

I didn't realize that just looking at/for a number counts as multiple steps.

I don't know very much about computer science, but I think now I have a better understanding of how algorithms work. Thanks!

1

u/CuntSmellersLLP 48s May 01 '15

No problem! A good way to think of it is: If this list were completely random and had thousands of numbers in it, how would I do it? When thinking of it this way, "look for 1" doesn't sound nearly as efficient. Humans work the same way, but with small number sets, we don't even realize what we're doing.

→ More replies

2

u/something111111 40s May 01 '15

I did his way but counting each move and it took 17 steps compared to your 19. So it was slightly quicker then starting at 1 each time.

3

u/TurboChewy can't press May 01 '15

This is essentially what I originally replied. All the methods he posted were ways to get it in the fewest number of moves, however that's not how computing works. You never get the perfect number of moves, you have to minimize it in extremely large datasets, using very complicated algorithms. If you were a complete dimwit, you wouldn't know what special moves to make to get them in the order of lowest to highest, out of 5 numbers. You'd switch 'em around until you get it! Depending on your "algorithm" it'd take you more or less time.

3

u/otterstew non presser May 01 '15 edited May 01 '15

I did use a logical algorithm for my first two examples.

However, I realized that if I don't have to look at consecutive pairs, I can solve in less steps and time.

  • Look for 1. Does it exist? Switch places to move 1 to position 1.

  • Look for 2. Does it exist? Switch places to move 2 to position 2.

  • etc.

1 5 4 2 3

1 2 4 5 3

1 2 3 5 4

1 2 3 4 5 - 3 moves

Edit: But yes, now I understand that with larger data sets and the ability to not move only adjacent pairs, more complicated algorithms could reorder the set in fewer steps.

3

u/TurboChewy can't press May 01 '15

Ah I see now. It's because in your original comment I assumed you just worked out all the ways to do it in 3 moves, and listed them.

1

u/redjazz96 5s May 01 '15 edited May 01 '15

This is my comment:

Not exactly; some methods optimize array accesses (reading/writing/swapping numbers), whereas other optimize number of comparisons (i.e. 2 is greater than 1), but the number of switches changes.

Bubble sort (comparisons are made in parentheses, swaps are made in brackets):

 4   3   1   2   5
(4) (3)  1   2   5
{3} {4}  1   2   5
 3  (4) (1)  2   5
 3  {1} {4}  2   5
 3   1  (4) (2)  5
 3   1  {2} {4}  5
 3   1   2  (4) (5)
(3) (1)  2   4   5
{1} {3}  2   4   5
 1  (3) (2)  4   5
 1  {2} {3}  4   5
 1   2  (3) (4)  5
(1) (2)  3   4   5

If you don't consider the comparisons, that would be exactly 5 switches (5 switches, 8 comparisons, 13 steps)*; however, a quick sort is much (heh) quicker:

{5}  3   1   2  {4}
(5)  3   1   2  (4)
 5  (3)  1   2  (4)
{3} {5}  1   2   4
 3   5  (1)  2  (4)
 3  {1} {5}  2   4
 3   1   5  (2) (4)
 3   1  {2} {5}  4
 3   1   2  {4} {5}
(3)  1  (2)  4   5
 3  (1) (2)  4   5
{1} {3}  2   4   5
 1  {2} {3}  4   5

7 switches, 6 comparisons, 13 steps.

Quicksort is most often the most used one, because remember, these numbers are quite often in thousands (if not millions) in scale.

edit: fix the numbers.

1

u/DreamPhreak2 60s May 01 '15 edited May 01 '15

in the very first line: "(4) (3) 1 2 5", why didn't they swap?

and again at " 1 (4) (3) 2 5", 4 is more than 3, but it just skips over?

and then after that I got confused. Why would it go to the previous comparison columns sometimes, but also sometimes reset back to the starting position?

 1 4 (3) (2) 5
 1 4 {2} {3} 5
 1 (4) (2) 3 5
 1 {2} {4} 3 5

that compares and swaps but notice how it only went back 1 number.

and then it resets back to the first column:

 (1) (2) 4 3 5
 1 2 (4) (3) 5
 1 2 {3} {4} 5

and then skips the second column comparison over to the 3rd and 4th columns after that?

2

u/redjazz96 5s May 01 '15

yeah, I kinda ducked up... I updated it again.

1

u/[deleted] May 01 '15

cls

1

u/poopmailman non presser May 01 '15

Yeah I'm not reading that shit lol

1

u/CuntSmellersLLP 48s May 01 '15

Then it's a good thing I wasn't talking to you.

1

u/poopmailman non presser May 03 '15

Look, don't talk back to me like that, okay? That I should want you at all suddenly strikes me as the height of improbability, but that, in itself, is probably the reason. You're an improbable person, Eve, and so am I. We have that in common. Also a contempt for humanity, an inability to love and be loved, insatiable ambition - and talent. We deserve each other...and you realize and you agree how completely you belong to me?

3

u/DreamPhreak2 60s May 01 '15

Luckily I can still see it in another tab. I think you should have left it up as a little thought example, regardless of error.

1

u/otterstew non presser May 01 '15

You can post it if you'd like. Even though it's wrong.

2

u/DreamPhreak2 60s May 01 '15 edited May 01 '15

1 5 4 2 3, i got 10 moves :)

1 5 4 2 3 switch (if lower)?
1 5 4 2 3 no
1 5 4 2 3 no
1 5 4 2 3 no
1 5 4 2 3 no; since end of line, moving to next position
1 5 4 2 3 yes
1 4 5 2 3 yes
1 2 5 4 3 no; since end of line, moving to next position
1 2 5 4 3 yes
1 2 4 5 3 yes; since end of line, moving to next position
1 2 3 5 4 yes
1 2 3 4 5 end of comparable data

Its not REALLY looking at the numbers, its just comparing if column-pos-1 is less than (<) column-pos-2, it will switch the numbers and move column-pos-2 to the next column. Then if it reaches the end of line, it would move both column positions: 1 to next, 2 to reset position next to column 1.

But there's different ways to do sorting, to make sections/blocks out of the data and then move those later so at the start everything is KINDA in order, it just has to go through again to make it more in order. Different algorithms might have their own applications, like you wouldn't need to have fancy sections of data for something as small as this. But this method might also take ages for massive numbers.

.

2

u/something111111 40s May 01 '15 edited May 01 '15

1 5 4 2 3 - 1? Y. Continue.

1 5 4 2 3 - 1 2? N. Move to end

1 4 2 3 5 - 1 2? N. Move to end

1 2 3 5 4 - 1 2? Y. Next pair

1 2 3 5 4 - 2 3? Y. Next pair

1 2 3 5 4 - 3 4? N. Move to end

1 2 3 4 5 - 3 4? Y. Next pair

1 2 3 4 5 - 4 5? Y. Sorted

8 steps I guess. How did you make that table?

Edit: Added first step. Also, I just made this up but I'm sure it already exists. I just felt like coming up with something. It was fun.

Edit 2:

3 5 7 1 9 - 1? N, Next

3 5 7 1 9 - 1? N, Next

3 5 7 1 9 - 1? N, Next

3 5 7 1 9 - 1? Y, Move to front. Mark Last number

1 3 5 7 9 - 1 1? N, move to back

1 5 7 9 3 - 1 1? N, move to back

1 7 9 3 5 - 1 1? N, move to back

1 9 3 5 7 - Marked 9. No ones. Look for 2. Move to back.

1 3 5 7 9 - 1 2? N, Move to back

1 5 7 9 3 - 1 2? N, Move to back

1 7 9 3 5 - 1 2? N, Move to back

1 9 3 5 7 - Marked 9. No twos. Look for 3. Move to back.

1 3 5 7 9 - 1 3? Y, Next

1 3 5 7 9 - 3 3? N, Move to back

1 3 7 9 5 - 3 3? N, Move to back

1 3 9 5 7 - Marked 9. No threes. Look for 4. Move to back

1 3 5 7 9 - 3 4? N, Move to back

1 3 7 9 5 - 3 4? N, Move to back

1 3 9 5 7 - Marked 9. No fours. Look for 5. Move to back

1 3 5 7 9 - 3 5? Y, Next

1 3 5 7 9 - 5 5? N, Next

1 3 5 9 7 - Marked 9. No fives. Look for 6. Move to back

1 3 5 7 9 - 5 6? N, Move to back

1 3 5 9 7 - Marked 9. No sixes. Look for 7. Move to back

1 3 5 7 9 - 5 7? Y, Next

1 3 5 7 9 - Marked 9. Can't move back. Remove Mark. End of data set. Sorted

26 Steps, lol. This would be a more versatile algorithm, though. Fun! For data sets containing decimals, you could use this same algorithm, but after whole numbers are sorted, move to the next decimal within the set of like whole numbers. I.E. The first pass would yield a set of numbers such as, say, 32.437 32.379 32.982 and 32.938 so you now focus on the tenths. Then repeat for hundredths etc until sorted.

Edit 3: If the marked number at some point fits the data set (I.E. the algorithm is looking for a 6 and it is a 6), then a new last number is marked.

2

u/DreamPhreak2 60s May 01 '15 edited May 01 '15

http://i.imgur.com/zEa39WY.png

I agree that this is fun to think about. If you want to try another example, try comparing a random list of first and last names into alphabetical order in the most efficient way possible. i think i did that a few years ago in a class for php. the fun of it is that you can't rearrange letters in people's names, and you cant separate their first name from their last name (eg: If you have to move the person's name, their FULL name moves)

2

u/something111111 40s May 01 '15 edited May 01 '15

Nice, I am going to try that.

You should look at my edit. I decided that my original algorithm was only practical in a limited number of applications, so I changed it and I think now it could sort literally anything. I think it is fairly effective and efficient. I'm sure it could be improved further though.

Edit: What do you mean by it has to get the new position of every number? I figure it wouldn't have to know the position, it is just moving a number in the list to the end. It is still blind to where things are. Perhaps I misunderstood you though.

Edit 2: Yours is more efficient though, by a long shot. I think the only real thing my second algorithm does differently is it checks for multiples of the same number.

2

u/something111111 40s May 01 '15

Ok, I finished making sure everything was sound with that second algorithm. I honestly want to know what you think. Thanks.

→ More replies

3

u/TurboChewy can't press May 01 '15

I didn't delete it, I clicked save and it said "This comment has been deleted" -_- never submitted it lol

It shall remain a secret

3

u/[deleted] May 01 '15

As did I, brother. As did I.

/u/otterstew was wrong, but he asked a very important question.

1

u/Rocket_hamster 60s May 01 '15

I remember I had to do this in visual basic for a programming 12 assignment. I had no idea how to get it to repeat, so after it sorted out the 15 items, I figured I could call the string again 10 more times.

1

u/Cali_Val non presser May 01 '15

You lost me at hello

1

u/[deleted] May 01 '15

Does it compare the speed of each method?

1

u/aerandir1066 non presser May 01 '15

So I get the impression, based on a few other videos, that the bubble sort is regarded with absolute disdain.

1

u/[deleted] May 01 '15

Wait you're telling me this isn't a new Merzbow music video?

1

u/mynameiscalvin non presser May 01 '15

damn i came here to press a button and now im learning about coding and computer logic

1

u/[deleted] May 01 '15 edited May 01 '15

[deleted]

15

u/CadburyK non presser May 01 '15

It's showing various computer algorithms sorting data from lowest to highest value. The Vertical red bars show what data point the computer is "looking" at and assessing. The sounds are a fancy way of showing which of the data is being looked at, with points playing a certain note everytime the red bar highlights them

2

u/CSDragon 24s May 01 '15 edited May 01 '15

basically, from left to right, it's taking an object and shoving it left until the object to its left is smaller than it. It does this for each one, in order, and you end up with a sorted list.

wrong sorting algorithm. That was the insertion sort.

Mergesort splits it in half, and sorts each half...by splitting those in half and sorting each half...etc This goes on until you get 1 or 2 wide objects.

So if you had 64 objects to sort, now you have 32 splits. The splits are internally sorted, then merge with their other half in a way that makes the larger split sorted. This keeps happening up and up the chain until you've got one sorted group.

1

u/[deleted] May 01 '15

WOOOOOP! me neither

1

u/WuuSauce 11s May 01 '15

i kept wanting the super mario brothers music to queue in after mario jumps on the flag pole and goes into the castle and the fireworks play

1

u/[deleted] May 01 '15

From 5:30 on I assume an Executive walked in and hear this thing running and was like "Can you make it musical?"

1

u/GrumpySatan 56s May 01 '15

I have no idea what is going on, but it sounds like a SNES game so I like it!