User:Teenly/Sort

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Bubble sort so it works the same as the example that is in the article.

There are two stacks of cards. Stack 1 has the cards so the faces are up. Stack 2 has the cards so the faces are down. When you start all the cards are in stack 1 and there are no cards in stack 2.

1. If stack 1 has no cards or only one card, it is sorted, you are done.
2. Look at the first card (the top) of stack 1.
3. The card you are looking at is card A.
4. If there are no more cards in stack 1 after card A, put card A on stack B with its face down and go to step 8.
5. The next (second) card in the stack is card B.
6. If card B has a lower number than card A, swap the positions of cards A and B; remember you did this.
7. Take the top card off stack 1 and put it on stack 2 with its face down and go to step 2.
8. Take stack 2 and turn the whole stack over all together so the faces are up. Now it is stack 1 and there are no cards in stack 2.
9. If you did not swap the position of any cards in the last run, you are done; stack 1 is sorted. If you did swap the position of any cards go to step 2.

Example

First Pass:

 Start     After step 6  After step 7
(51428)() -> (15428)() -> (5428)(1)
(5428)(1) -> (4528)(1) -> (528)(14) 
(528)(14) -> (258)(14) -> (58)(142) 
(58)(142) -> (58)(142) -> (8)(1425)
                       -> ()(14258) (step 4) 

Second Pass:

(14258)() -> (14258)() -> (4258)(1)
(4258)(1) -> (2458)(1) -> (458)(12) 
(458)(12) -> (458)(12) -> (58)(124) 
(58)(124) -> (58)(124) -> (8)(1245)
                       -> ()(12458) (step 4)

You go through one more time and there are no more changes so you are done.


Here is the whole thing with all the steps

1. If stack 1 has no cards or only one card, it is sorted, you are done.

    1. (51428)()  Stack 1 has more than one card. I am not done.  

2. Look at the first card (the top) of stack 1.

    1. (51428)()  The top card is the 5.  
    2. (5428)(1)R The top card is the 5. 
    3. (528)(14)R The top card is the 5.
    4. (58)(142)R The top card is the 5.
    5. (8)(1425)R The top card is the 8.
    6. (14258)()  The top card is the 1.
    7. (4258)(1)  The top card is the 4.
    8. (458)(12)R The top card is the 4.
    9. (58)(124)R The top card is the 5.
   10. (8)(1245)R The top card is the 8.
   11. (12458)()  The top card is the 1.
   12. (2458)(1)  The top card is the 2.
   13. (458)(12)  The top card is the 4.
   14. (58)(124)  The top card is the 5.
   15. (8)(1245)  The top card is the 8.

3. The card you are looking at is card A.

    1. (51428)()  The 5 is card A.  
    2. (5428)(1)R The 5 is card A.  
    3. (528)(14)R The 5 is card A.
    4. (58)(142)R The 5 is card A.
    5. (8)(1425)R The 8 is card A.
    6. (14258)()  The 1 is card A.
    7. (4258)(1)  The 4 is card A.
    8. (458)(12)R The 4 is card A.
    9. (58)(124)R The 5 is card A.
   10. (8)(1245)R The 8 is card A.
   11. (12458)()  The 1 is card A.
   12. (2458)(1)  The 2 is card A.
   13. (458)(12)  The 4 is card A.
   14. (58)(124)  The 5 is card A.
   15. (8)(1245)  The 8 is card A.

4. If there are no more cards in stack 1 after card A, put card A on stack B with its face down and go to step 8.

    1. (51428)()  There are four more cards after card A. I do not do this step.  
    2. (5428)(1)R There are three more cards after card A. I do not do this step.
    3. (528)(14)R There are two more cards after card A. I do not do this step.
    4. (58)(142)R There is one more card after card A. I do not do this step.  
    5. ()(14258)R There are no more cards after card A. I put the 8 on stack B and go to step 8.
    6. (14258)()  There are four more cards after card A. I do not do this step.
    7. (4258)(1)  There are three more cards after card A. I do not do this step.
    8. (458)(12)R There are two more cards after card A. I do not do this step.
    9. (58)(124)R There is one more card after card A. I do not do this step.
   10. ()(12458)R There are no more cards after card A. I put the 8 on stack B and go to step 8.
   11. (12458)()  There are four more cards after card A. I do not do this step.
   12. (2458)(1)  There are three more cards after card A. I do not do this step.
   13. (458)(12)  There are two more cards after card A. I do not do this step.
   14. (58)(124)  There is one more card after card A. I do not do this step.
   15. ()(12458)  There are no more cards after card A. I put the 8 on stack B and go to step 8.

5. The next card in the stack is card B.

    1. (51428)()  The 1 is card B. 
    2. (5428)(1)R The 4 is card B.
    3. (528)(14)R The 5 is card A.
    4. (58)(142)R The 8 is card B.
    6. (14258)()  The 4 is card B.
    7. (4258)(1)  The 2 is card B.
    8. (458)(12)R The 5 is card B.
    9. (58)(124)R The 8 is card B.
   11. (12458)()  The 2 is card B.
   12. (2458)(1)  The 4 is card B.
   13. (458)(12)  The 5 is card B.
   14. (58)(124)  The 8 is card B.

6. If card B has a lower number than card A, swap the positions of cards A and B; remember you did this.

    1. (15428)()R  Card B is 1. Card A is 5. Card B is lower than card A so I swap the cards. The R means remember. 
    2. (4528)(1)R  Card B is 4. Card A is 5. Card B is lower than card A so I swap the cards.
    3. (258)(14)R  Card B is 2. Card A is 5. Card B is lower than card A so I swap the cards.
    4. (58)(142)R  Card B is 8. Card A is 5. Card B is not lower than card A so I do not swap the cards.
    6. (14258)()  Card B is 4. Card A is 1. Card B is not lower than card A so I do not swap the cards.
    7. (2458)(1)R Card B is 2. Card A is 4. Card B is lower than card A so I swap the cards.
    8. (458)(12)R Card B is 5. Card A is 4. Card B is not lower than card A so I do not swap the cards.
    9. (58)(124)R Card B is 8. Card A is 5. Card B is not lower than card A so I do not swap the cards.
   11. (12458)()  Card B is 2. Card A is 1. Card B is not lower than card A so I do not swap the cards.
   12. (2458)(1)  Card B is 4. Card A is 2. Card B is not lower than card A so I do not swap the cards.
   13. (458)(12)  Card B is 5. Card A is 4. Card B is not lower than card A so I do not swap the cards.
   14. (58)(124)  Card B is 8. Card A is 5. Card B is not lower than card A so I do not swap the cards.

7. Take the top card off stack 1 and put it on stack 2 with its face down and go to step 2.

    1. (5428)(1)R I put the 1 on stack 2 and go to step 2. 
    2. (528)(14)R I put the 4 on stack 2 and go to step 2. 
    3. (58)(142)R I put the 2 on stack 2 and go to step 2. 
    4. (8)(1425)R I put the 5 on stack 2 and go to step 2. 
    6. (4258)(1)  I put the 1 on stack 2 and go to step 2.
    7. (458)(12)R I put the 2 on stack 2 and go to step 2.
    8. (58)(124)R I put the 4 on stack 2 and go to step 2.
    9. (8)(1245)R I put the 5 on stack 2 and go to step 2.
   11. (2458)(1)  I put the 1 on stack 2 and go to step 2.
   12. (458)(12)  I put the 2 on stack 2 and go to step 2.
   13. (58)(124)  I put the 4 on stack 2 and go to step 2.
   14. (8)(1245)  I put the 5 on stack 2 and go to step 2.

8. Take stack 2 and turn the whole stack over all together so the faces are up. Now it is stack 1 and there are no cards in stack 2.

    5. (14258)()R I make stack B into stack A.
   10. (12458)()R I make stack B into stack A.
   15. (12458)()  I make stack B into stack A.

9. If you did not swap the position of any cards in the last run, you are done; stack 1 is sorted. If you did swap the position of any cards go to step 2.

    5. (14258)()R I did swap some cards. I go to step 2.
   10. (12458)()R I did swap some cards. I go to step 2.
   15. (12458)()  I did not swap any cards. Stack 1 is sorted.

Teenly 23:12, 13 March 2009 (UTC)