3.8.05
today
i was thinking about good ways to sort into order a bunch of pieces of paper that are already almost in order, with nowhere to put down a stack of paper except on my knee.
a good way is probably Insertion Sort. everybody knows this, it's what you usually do if you sort some cards in your hand. you start at the left, going through the cards to the right, each time taking one and putting it in the correct position among the ordered cards to the left of it. so you constantly have a pile of cards on the left which are in the right order, and a bunch to the right which are in the order they started in, and you just keep moving individual cards from the right side to the left.
the weird thing is, lots of people when they first start learning to program, instead of using this pretty simple, pretty fast algorithm which they know already, instead use something a little bit more boneheaded: Bubble Sort.
Bubble Sort involves repeatedly going through your cards from left to right, swapping around any pair that are in the wrong order. it's really not a very good way to sort, for aesthetic and practical reasons. it's not quite the same as, but involves the exact same number of operations as if you used Insertion Sort, but moved a card from the right of your hand to the left by swapping pairs of cards all the way along until it got to the right place, instead of just pulling it out and putting it back where you want it. it doesn't use any less space then Insertion Sort. it's not really any easier to understand. it's easy to see that its not a very good method of sorting if you try it for 7, let alone 13 playing cards.
i think people think quickly about sorting, and associate it straight away with swapping pairs of elements.
this is why it's good to try out algorithms by hand. also why it's good to think about the way we do things in real life. those traditional wisdom methods are usually pretty good.
a good way is probably Insertion Sort. everybody knows this, it's what you usually do if you sort some cards in your hand. you start at the left, going through the cards to the right, each time taking one and putting it in the correct position among the ordered cards to the left of it. so you constantly have a pile of cards on the left which are in the right order, and a bunch to the right which are in the order they started in, and you just keep moving individual cards from the right side to the left.
the weird thing is, lots of people when they first start learning to program, instead of using this pretty simple, pretty fast algorithm which they know already, instead use something a little bit more boneheaded: Bubble Sort.
Bubble Sort involves repeatedly going through your cards from left to right, swapping around any pair that are in the wrong order. it's really not a very good way to sort, for aesthetic and practical reasons. it's not quite the same as, but involves the exact same number of operations as if you used Insertion Sort, but moved a card from the right of your hand to the left by swapping pairs of cards all the way along until it got to the right place, instead of just pulling it out and putting it back where you want it. it doesn't use any less space then Insertion Sort. it's not really any easier to understand. it's easy to see that its not a very good method of sorting if you try it for 7, let alone 13 playing cards.
i think people think quickly about sorting, and associate it straight away with swapping pairs of elements.
this is why it's good to try out algorithms by hand. also why it's good to think about the way we do things in real life. those traditional wisdom methods are usually pretty good.
# posted by weierstrass @ 16:09 
