User:Teenly/Algorithm
1. If the stack of cards is empty, or it only contains one card, it is sorted, you are done.
- (51428) The stack of cards is not empty. I am not done.
2. Take the stack of cards. Look at the first card (the top) of the stack.
- (51428) It is a 5.
3. The card you are looking at is card A.
- (51428) Card A is the 5.
4. If there are no more cards in the stack, after card A, go to step 8.
- (51428) Card A is the 5. There are more cards in the stack after the 5. I do not go to step 8.
5. The next card in the stack is card B.
- (51428) Card B is the 1.
6. If card B has a lower number than card A, swap the positions of cards A and B; remember you did this.
- (51428) Card B is the 1. Card A is the 5. Card B has a lower number than card A so I swap the positions of cards A and B and I get (15428).
7. If there is another card in the stack, look at it; go back to step 3.
- (15428) This is where I get mixed up
8. If you did not swap the position of any cards in the last run, you are done; the stack of cards is sorted.
9. Otherwise go back to step 2.
It says in step 7 to look at a card and next I go back to step 3 and it says the card I am looking at is the next card A, so step 7 is where I find the next card A.
All it tells me how to find the right card is If there is another card in the stack, look at it. There are five cards in the stack. It does not tell which card to look at.
In step 6 I use card A and card B and next it says If there is another card in the stack so it sounds like it means a different card that is not card A or not card B but ANOTHER CARD. Maybe it is the next card that is not card A and not card B and that is the 4.
I can not ever come to step 7 if there is not a card A and a card B so when I am at step 7 there is always always a card A and a card B so why does it say If there is another card in the stack if another card does not mean another card that is not card A and not card B. That sounds like it means the 4 too.
If it means look at the 4 it is not the same as in the example because the next card A in the example is the 5 again.
What happens if the next card A is the next card that is not the old A and not the old B.
- (51428) -> (15428) card A is the 5 and card B is the 1
- (15428) -> (15248) card A is the 4 and card B is the 2
- (15248) -> (15248) card A is the 8 and there is no card B so start over
- (15248) -> (15248) card A is the 1 and card B is the 5
- (15248) -> (15248) card A is the 2 and card B is the 4
- (15248) -> (15248) card A is the 8 and there is no card B. The algorithm thinks it is done because it did not swap any cards but the cards are not sorted.
The algorithm does not work if the new card A is the next card that is not the old A and not the old B.
In step 7 I do not need to look if there is another card to see if I am running out of cards because after I go to step 3 and make a new card A it goes to step 4 and it looks if I am running out of cards there.
In step 7 it should not say If there is another card in the stack. I do not have to see if there is another card in the stack. I have to find out what card will be the next card A, but If there is another card in the stack, look at it is not how to find out. It has to say something else in step 7 how to find the next card A but it does not say anything.
Pretend step 7 jut says GO TO STEP 3.
This is what it says before the algorithm.
- This algorithm goes through the stack of cards, one card at a time; this card is compared to the next card in the stack. Please note that this position only changes in step 3.
It says THIS CARD is compared to the next card but it does not say what is THIS CARD. Maybe EACH CARD I think.
When I come to step 3 the next card to be the new card A is not the next card after the old card A. The first card A in the example is the 5. When I get to step 3 again the next card after the 5 is the 4 but that is not the right card. In the example the first card A is the 5 and the second card A is the 5 again and the third card A is the 5 again.
In the Step-by-step example the first time I do step 3 card A is the first card in the stack, and the second time I do step 3 card A is the second card in the stack, and like that. Maybe it is still the same card as before. So I have to remember how many times I did step 3 before and count down that many cards and one more and that is the next card A.
I have to use what it says before the algorithm to find out what to do next so if I have to use it, that part is part of the algorithm and it has to be in the algorithm where the steps are and not before it.
After step 6 what if I take the top card off the stack and put it on another stack. Then when I go to step 3 I do not have to remember how many times I did step 3 and count down that many cards and one more from the top of the stack and that is the new card A. Just the top card is card A.
If I put the top cards in a new stack I have to put them with the face down or else they will be in backwards order. — Preceding unsigned comment added by teenly (talk • contribs)
- At step 3 imagine you have a pointer/arrow. this will point to the current position of card A in the stack;At your first run this will be 5; In step 6 you swapped (51428)-> (15428). In step 7, the this card refers to the card at the arrow (you swapped the card, the arrow is still at the old position). Since you swapped, this is 1. You start over at step 3 with (15428), but you are done looking at the 1 at the top of the stack.--Eptalon (talk) 23:47, 11 March 2009 (UTC)
Algorithm article
- This algorithm goes through the stack of cards, one card at a time; this card is compared to the next card in the stack. Please note that this position only changes in step 3.
Algorithm talk page
- Your problem is that the first algorithm (bubble sort) needs to keep track of a position; this position is only changed in step 3; As you can see in the example below, you will travel with the card through the stack as long as the next card has a lower number
My talk page
- In Step 3, It says The card you are looking at is Card A; imagine a pointer/arrow pointing to the position where card A is now. If you swap cards in step 6, you swap the card, but you do not change the arrow (it will point to a new card if you swapped). In step 7 If there is another card on the stack, look at it; go back to step 3 really means If there is another card past the position of the arrow
- I just found out how to do this!
I wrote this before I saw you changed the Algorithm article so now it has an arrow in it like I wanted, but I think I am finished thinking about this now, so you can read what I was thinking if you want.
Thank you for helping me Eptalon. I think you are very busy so it is nice if you want to help me understand.
This algorithm is making me have a head ache. OK, I think I see how the bubble sort works but it is only because I can look at the example and you wrote some things to help me. It is not just about if I understand the bubble sort, it is about if anyone that reads the article can try it out to see how it works. I guess you can try out the colour sort one but it is too simple.
I think it should be so you can read step one and it tells you exactly what to do so you do what it says, then do step two and do every step. You should not have to know what a bubble sort is beause it tells you exactly what to do in each step, and when you get to the end the cards are sorted. I do not think anyone can sort cards with the algorithm the way it says in the article now. It has to have an arrow that points at the place where card A is, but it does not talk about an arrow any place except maybe on the talk page, so when you come to step 7 where it says IF THERE IS ANOTHER CARD IN THE STACK how do you know it means IF THERE IS ANOTHER CARD PAST THE POSITION OF THE ARROW if it does not even say there is an arrow. It is like if you have a software and maybe there is supposed to be a button to click on, but there is no button and the manual says imagine a button and here is what the button would do if there was a button. So I think the algorithm has to have the arrow in it so you know where the next card A is every time and not just say on the talk page what the arrow does but there is no arrow. Do you see what I mean, Eptalon?
I tried to make a way to do algorithm 1 that sorts the cards the same as the example, only with an arrow, but I could not think of an easy way to do the arrow. You have to count how many times you move the arrow down so you know where it is every time, so you have to keep writing it down or something. I thought of a different way that is easy to do. When you start the arrow starts on the top card place. When the arrow moves down to the second card place you just take the top card off the top because you are done looking at it, so then the arrow place is still at the top card place, and you keep doing that every time the arrow place moves down. That way you do not have to count or remember where the arrow is because it is always at the top card. You have to save the cards you take off the top in the same order so you can put them back when you have to use them again, so you make another stack. You have to put the cards with their face down or they will get in backwards order. Then you can just turn the whole new stack over when you have to start at the top again. I tried to keep the steps like the ones in the article, but you can put step 2 and step 3 together and just say The card on top of stack 1 is Card A. I tried out the whole algorithm all the way to the end and it works. Maybe it is not a better way but it is better for me because I can understand what I am supposed to do every time and the cards get sorted. I do not mind if you think the way in the article is better. I just wanted to understand and now I do. Teenly 23:07, 13 March 2009 (UTC)
Here is the algorithm I made. Teenly 23:16, 13 March 2009 (UTC)
- Should probably work, with the problem mentioned (when you add cards to the top of the second stack they will be in the reversed order). Now that you seem to understand how the first one works, do you want to look at the other two (third one probably easier to understand than second). - As I have already stated, this algorithm for sorting cards is usually not used (because it takes far too many steps). The second and third one are the ones that are used, in practice. If you try them, you will see how much faster they are. Second one is about splitting the stacks in half until this is no longer possible, and putting them back together; third one is about comparing all of them to a single card. What do you think, which of the three is easiest to understand? --Eptalon (talk) 23:45, 13 March 2009 (UTC)
- It works, and if you put the cards on the second stack with their faces down there is not any problem. I wrote every single step for the 51428 example on my Sort page to make sure. Teenly 12:49, 14 March 2009 (UTC)
Second Algorithm
The second algorithm is mostly not hard to understand except one thing.
This is what is in the diagram in the article. I put zero in front of the 3 and the 9 so it lines up better.
1. (38 27 43 03 09 82 10) 2. (38 27 43 03)(09 82 10) 3. (38 27)(43 03)(09 82)(10) 4. (38)(27)(43)(03)(09)(82)(10) <-- Just start here 5. (27 38)(03 43)(09 82)(10) 6. (03 27 38 43)(09 10 82) 7. (03 09 10 27 38 43 82)
Line 1 is one stack with seven cards and line 4 is seven stacks with one card in each stack. Why do you split the stack in two and then split the new stacks in two to get from line 1 to line 4? If you want to make one stack with seven cards into seven stacks with one card you can just put all the cards down next to each other.
If I have these cards (9 2 7 8 6 4 3 1 5), I just go
1. 9 2 7 8 6 4 3 1 5 merge the first two and the second two and like that 2. (2 9)(7 8)(4 6)(1 3)(5) merge the first two stacks and the second two and like that 3. (2 7 8 9)(1 3 4 6)(5) do it again 4. (1 2 3 4 6 7 8 9)(5) do it again 5. (1 2 3 4 5 6 7 8 9) finished
Maybe you don't need the part about splitting the stacks at all. Teenly 14:24, 14 March 2009 (UTC)
Third Algorithm
I think the third algorithm is harder to understand than the second one. The thing called recursion is maybe harder in this one for me, but I see how it works.
Something can mess up if you are not careful. Not if you pick the pivot card at random, but if you look at the animation it does not pick the pivot card at random and then you have to be careful.
Pretend I am using these cards.
(1 5 3 4 6 8 7 2 9) Stack A
If I use the top card for the pivot that is the 1 so I get
() Stack B smaller (1 5 3 4 6 8 7 2 9) Stack C equal or bigger
Then I sort Stack C with the same algorithm
() (1 5 3 4 6 8 7 2 9) Oops! I am trapped.
This is easy to see because it is right at the start but the first time I saw it was not at the start. If you use the top card it happens if the top card is ever the smallest card in the stack you are sorting, so you can not just use the top card or just use the bottom card.
I looked at the animation a lot to see what it does.
1. It picks the card on the farthest right for the pivot.
2. It starts from the next card to the left of the pivot. If the card is smaller than the pivot it moves it to the left end. It puts the first card that is smaller in the first spot and the second card that is smaller in the second spot and like that, and it moves all the cards that are left of the empty spot over to fill up the empty spot. If the card is bigger than the pivot it leaves it where it is. It makes the smaller cards go backwards from before but not the bigger cards except the pivot. I am not sure if that is important but I do not think so. The cards that are sorted are at the ends and the cards that are not sorted are in the middle. There is a red line like an arch that shows where the cards are that are not sorted.
3. It moves the pivot card to the other end of the bigger cards when it is finished sorting with it. That way it can not get trapped because there is a new pivot if no cards move. If you look at the animation, you can see first the red bar is at the very right. Then it moves to the middle and it is the same size but nothing else happens. Then it stops being red and the smaller one that is the next one to the left turns red. That is the pivot for the next sort of the small half cards.
4. Then it sorts all the small half cards the same way.
5. Then it sorts the big half cards the same way.
Most of what it does is in step 4 and 5. The hard thing for me to see at first was, there is a lot more to do than it looks like.
I made an example that does it like the animation. I used the same cards like in in the trap before, except I changed the cards backwards because the animation starts from the right and I started from the left before. I only did the start until it misses the trap.
1. (9 2 7 8 6 4 3 5 1*) The 1 is the pivot 2. () (9 2 7 8 6 4 3 5 1*) All the cards are bigger than the pivot so I do not move any. 3. () (1* 9 2 7 8 6 4 3 5) Move the pivot to the other end of the bigger cards. 4. () (1 9 2 7 8 6 4 3) There are no smaller cards. 5. Sort the bigger cards like in step 2. () (1 9 2 7 8 6 4 3 5*) The 5 is the pivot. (3) (1 9 2 7 8 6 4 5*) The 3 is smaller. I put it in the first spot. (3 4) (1 9 2 7 8 6 5*) The 4 is smaller. I put it in the second spot. (3 4) (1 9 2 7 8 6 5*) The 6 8 7 are bigger. I do not move them. (3 4 2) (1 9 7 8 6 5*) The 2 is smaller. I put it in the third spot. (3 4 2) (1 9 7 8 6 5*) The 9 is bigger. I do not move it. (3 4 2 1) (9 7 8 6 5*) The 1 is smaller. I put it in the fourth spot. 5.2. Move the pivot to the other end of the bigger cards. (3 4 2 1) (5* 9 7 8 6) 6. Do the rest.
Teenly 18:53, 14 March 2009 (UTC)