Introduction to Algorithms

Posted on | In

An algorithm is a well-defined procedure for solving a problem. For example, imagine you just started a job at a city library. A tornado hit yesterday, and all the books fell off the shelves. Your employer asks you to put them back in order by book ID. Despite your meager pay, you have no choice but to sort them out. So you start thinking about the best way to do it.

Insertion Sort

You give up looking for a clever approach. Instead, you simply scan through the books, always picking the one with the smallest ID and placing it on the shelf.

Quick Sort

Meanwhile, your friend decides to do the following.

  1. If there is only one book, just put it in with the revered direction.
  2. If there is more than a book, select a book in random.
  3. Put all books that have smaller ID than the book that you selected at 1 into the shelf.
  4. Then add the book that you selected at 1 but in the reversed direction to identify this is the book which you used.
  5. If all books are in the self with inverse direction, flip all books.
  6. Otherwise, pick books between two reversed book and take books out of the shelf and do the same process from 1.

Note that the two ends of the shelf are treated as reversed-book sentinels for step 6.

This approach looks more complex, but it is usually much faster in practice. See the example below.

Example

There are books with IDs: 52, 33, 25, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90.

Your approach (insertion sort) proceeds like this. Notice that I marked [] as books that shelf has, {} as what you are memorizing and () as what you are looking. In this algorithm, you can see only one book at once because numbers are too complex to see it on glance. At the same time, you can memorize a number at most because of its long digits.

  1. (52), 33, 25, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  2. {52}, (33), 25, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  3. 52, {33}, (25), 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  4. 52, 33, {25}, (19), 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  5. 52, 33, 25, {19}, (28), 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  6. 52, 33, 25, {19}, 28, (38), 37, 45, 73, 68, 61, 69, 87, 78, 90
  7. 52, 33, 25, {19}, 28, 38, (37), 45, 73, 68, 61, 69, 87, 78, 90
  8. 52, 33, 25, {19}, 28, 38, 37, (45), 73, 68, 61, 69, 87, 78, 90
  9. 52, 33, 25, {19}, 28, 38, 37, 45, (73), 68, 61, 69, 87, 78, 90
  10. 52, 33, 25, {19}, 28, 38, 37, 45, 73, (68), 61, 69, 87, 78, 90
  11. 52, 33, 25, {19}, 28, 38, 37, 45, 73, 68, (61), 69, 87, 78, 90
  12. 52, 33, 25, {19}, 28, 38, 37, 45, 73, 68, 61, (69), 87, 78, 90
  13. 52, 33, 25, {19}, 28, 38, 37, 45, 73, 68, 61, 69, (87), 78, 90
  14. 52, 33, 25, {19}, 28, 38, 37, 45, 73, 68, 61, 69, 87, (78), 90
  15. 52, 33, 25, {19}, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, (90)
  16. [19], 52, 33, 25, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  17. [19], (52), 33, 25, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  18. [19], {52}, (33), 25, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  19. [19], 52, {33}, (25), 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  20. [19], 52, 33, {25}, (28), 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  21. [19], 52, 33, {25}, 28, (38), 37, 45, 73, 68, 61, 69, 87, 78, 90
  22. [19], 52, 33, {25}, 28, 38, (37), 45, 73, 68, 61, 69, 87, 78, 90
  23. [19], 52, 33, {25}, 28, 38, 37, (45), 73, 68, 61, 69, 87, 78, 90
  24. [19], 52, 33, {25}, 28, 38, 37, 45, (73), 68, 61, 69, 87, 78, 90
  25. [19], 52, 33, {25}, 28, 38, 37, 45, 73, (68), 61, 69, 87, 78, 90
  26. [19], 52, 33, {25}, 28, 38, 37, 45, 73, 68, (61), 69, 87, 78, 90
  27. [19], 52, 33, {25}, 28, 38, 37, 45, 73, 68, 61, (69), 87, 78, 90
  28. [19], 52, 33, {25}, 28, 38, 37, 45, 73, 68, 61, 69, (87), 78, 90
  29. [19], 52, 33, {25}, 28, 38, 37, 45, 73, 68, 61, 69, 87, (78), 90
  30. [19], 52, 33, {25}, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, (90)
  31. [19, 25], 52, 33, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  32. [19, 25], (52), 33, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  33. [19, 25], {52}, (33), 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  34. [19, 25], 52, {33}, (28), 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  35. [19, 25], 52, 33, {28}, (38), 37, 45, 73, 68, 61, 69, 87, 78, 90
  36. [19, 25], 52, 33, {28}, 38, (37), 45, 73, 68, 61, 69, 87, 78, 90
  37. [19, 25], 52, 33, {28}, 38, 37, (45), 73, 68, 61, 69, 87, 78, 90
  38. [19, 25], 52, 33, {28}, 38, 37, 45, (73), 68, 61, 69, 87, 78, 90
  39. [19, 25], 52, 33, {28}, 38, 37, 45, 73, (68), 61, 69, 87, 78, 90
  40. [19, 25], 52, 33, {28}, 38, 37, 45, 73, 68, (61), 69, 87, 78, 90
  41. [19, 25], 52, 33, {28}, 38, 37, 45, 73, 68, 61, (69), 87, 78, 90
  42. [19, 25], 52, 33, {28}, 38, 37, 45, 73, 68, 61, 69, (87), 78, 90
  43. [19, 25], 52, 33, {28}, 38, 37, 45, 73, 68, 61, 69, 87, (78), 90
  44. [19, 25], 52, 33, {28}, 38, 37, 45, 73, 68, 61, 69, 87, 78, (90)
  45. [19, 25, 28], 52, 33, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  46. [19, 25, 28], (52), 33, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  47. [19, 25, 28], {52}, (33), 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  48. [19, 25, 28], 52, {33}, (38), 37, 45, 73, 68, 61, 69, 87, 78, 90
  49. [19, 25, 28], 52, {33}, 38, (37), 45, 73, 68, 61, 69, 87, 78, 90
  50. [19, 25, 28], 52, {33}, 38, 37, (45), 73, 68, 61, 69, 87, 78, 90
  51. [19, 25, 28], 52, {33}, 38, 37, 45, (73), 68, 61, 69, 87, 78, 90
  52. [19, 25, 28], 52, {33}, 38, 37, 45, 73, (68), 61, 69, 87, 78, 90
  53. [19, 25, 28], 52, {33}, 38, 37, 45, 73, 68, (61), 69, 87, 78, 90
  54. [19, 25, 28], 52, {33}, 38, 37, 45, 73, 68, 61, (69), 87, 78, 90
  55. [19, 25, 28], 52, {33}, 38, 37, 45, 73, 68, 61, 69, (87), 78, 90
  56. [19, 25, 28], 52, {33}, 38, 37, 45, 73, 68, 61, 69, 87, (78), 90
  57. [19, 25, 28], 52, {33}, 38, 37, 45, 73, 68, 61, 69, 87, 78, (90)
  58. [19, 25, 28, 33], 52, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  59. [19, 25, 28, 33], (52), 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  60. [19, 25, 28, 33], {52}, (38), 37, 45, 73, 68, 61, 69, 87, 78, 90
  61. [19, 25, 28, 33], 52, {38}, (37), 45, 73, 68, 61, 69, 87, 78, 90
  62. [19, 25, 28, 33], 52, 38, {37}, (45), 73, 68, 61, 69, 87, 78, 90
  63. [19, 25, 28, 33], 52, 38, {37}, 45, (73), 68, 61, 69, 87, 78, 90
  64. [19, 25, 28, 33], 52, 38, {37}, 45, 73, (68), 61, 69, 87, 78, 90
  65. [19, 25, 28, 33], 52, 38, {37}, 45, 73, 68, (61), 69, 87, 78, 90
  66. [19, 25, 28, 33], 52, 38, {37}, 45, 73, 68, 61, (69), 87, 78, 90
  67. [19, 25, 28, 33], 52, 38, {37}, 45, 73, 68, 61, 69, (87), 78, 90
  68. [19, 25, 28, 33], 52, 38, {37}, 45, 73, 68, 61, 69, 87, (78), 90
  69. [19, 25, 28, 33], 52, 38, {37}, 45, 73, 68, 61, 69, 87, 78, (90)
  70. [19, 25, 28, 33, 37], 52, 38, 45, 73, 68, 61, 69, 87, 78, 90
  71. [19, 25, 28, 33, 37], (52), 38, 45, 73, 68, 61, 69, 87, 78, 90
  72. [19, 25, 28, 33, 37], {52}, (38), 45, 73, 68, 61, 69, 87, 78, 90
  73. [19, 25, 28, 33, 37], 52, {38}, (45), 73, 68, 61, 69, 87, 78, 90
  74. [19, 25, 28, 33, 37], 52, {38}, 45, (73), 68, 61, 69, 87, 78, 90
  75. [19, 25, 28, 33, 37], 52, {38}, 45, 73, (68), 61, 69, 87, 78, 90
  76. [19, 25, 28, 33, 37], 52, {38}, 45, 73, 68, (61), 69, 87, 78, 90
  77. [19, 25, 28, 33, 37], 52, {38}, 45, 73, 68, 61, (69), 87, 78, 90
  78. [19, 25, 28, 33, 37], 52, {38}, 45, 73, 68, 61, 69, (87), 78, 90
  79. [19, 25, 28, 33, 37], 52, {38}, 45, 73, 68, 61, 69, 87, (78), 90
  80. [19, 25, 28, 33, 37], 52, {38}, 45, 73, 68, 61, 69, 87, 78, (90)
  81. [19, 25, 28, 33, 37, 38], 52, 45, 73, 68, 61, 69, 87, 78, 90
  82. [19, 25, 28, 33, 37, 38], (52), 45, 73, 68, 61, 69, 87, 78, 90
  83. [19, 25, 28, 33, 37, 38], {52}, (45), 73, 68, 61, 69, 87, 78, 90
  84. [19, 25, 28, 33, 37, 38], 52, {45}, (73), 68, 61, 69, 87, 78, 90
  85. [19, 25, 28, 33, 37, 38], 52, {45}, 73, (68), 61, 69, 87, 78, 90
  86. [19, 25, 28, 33, 37, 38], 52, {45}, 73, 68, (61), 69, 87, 78, 90
  87. [19, 25, 28, 33, 37, 38], 52, {45}, 73, 68, 61, (69), 87, 78, 90
  88. [19, 25, 28, 33, 37, 38], 52, {45}, 73, 68, 61, 69, (87), 78, 90
  89. [19, 25, 28, 33, 37, 38], 52, {45}, 73, 68, 61, 69, 87, (78), 90
  90. [19, 25, 28, 33, 37, 38], 52, {45}, 73, 68, 61, 69, 87, 78, (90)
  91. [19, 25, 28, 33, 37, 38, 45], 52, 73, 68, 61, 69, 87, 78, 90
  92. [19, 25, 28, 33, 37, 38, 45], (52), 73, 68, 61, 69, 87, 78, 90
  93. [19, 25, 28, 33, 37, 38, 45], {52}, (73), 68, 61, 69, 87, 78, 90
  94. [19, 25, 28, 33, 37, 38, 45], {52}, 73, (68), 61, 69, 87, 78, 90
  95. [19, 25, 28, 33, 37, 38, 45], {52}, 73, 68, (61), 69, 87, 78, 90
  96. [19, 25, 28, 33, 37, 38, 45], {52}, 73, 68, 61, (69), 87, 78, 90
  97. [19, 25, 28, 33, 37, 38, 45], {52}, 73, 68, 61, 69, (87), 78, 90
  98. [19, 25, 28, 33, 37, 38, 45], {52}, 73, 68, 61, 69, 87, (78), 90
  99. [19, 25, 28, 33, 37, 38, 45], {52}, 73, 68, 61, 69, 87, 78, (90)
  100. [19, 25, 28, 33, 37, 38, 45, 52], 73, 68, 61, 69, 87, 78, 90
  101. [19, 25, 28, 33, 37, 38, 45, 52], (73), 68, 61, 69, 87, 78, 90
  102. [19, 25, 28, 33, 37, 38, 45, 52], {73}, (68), 61, 69, 87, 78, 90
  103. [19, 25, 28, 33, 37, 38, 45, 52], 73, {68}, (61), 69, 87, 78, 90
  104. [19, 25, 28, 33, 37, 38, 45, 52], 73, 68, {61}, (69), 87, 78, 90
  105. [19, 25, 28, 33, 37, 38, 45, 52], 73, 68, {61}, 69, (87), 78, 90
  106. [19, 25, 28, 33, 37, 38, 45, 52], 73, 68, {61}, 69, 87, (78), 90
  107. [19, 25, 28, 33, 37, 38, 45, 52], 73, 68, {61}, 69, 87, 78, (90)
  108. [19, 25, 28, 33, 37, 38, 45, 52, 61], 73, 68, 69, 87, 78, 90
  109. [19, 25, 28, 33, 37, 38, 45, 52, 61], (73), 68, 69, 87, 78, 90
  110. [19, 25, 28, 33, 37, 38, 45, 52, 61], {73}, (68), 69, 87, 78, 90
  111. [19, 25, 28, 33, 37, 38, 45, 52, 61], 73, {68}, (69), 87, 78, 90
  112. [19, 25, 28, 33, 37, 38, 45, 52, 61], 73, {68}, 69, (87), 78, 90
  113. [19, 25, 28, 33, 37, 38, 45, 52, 61], 73, {68}, 69, 87, (78), 90
  114. [19, 25, 28, 33, 37, 38, 45, 52, 61], 73, {68}, 69, 87, 78, (90)
  115. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68], 73, 69, 87, 78, 90
  116. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68], (73), 69, 87, 78, 90
  117. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68], {73}, (69), 87, 78, 90
  118. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68], 73, {69}, (87), 78, 90
  119. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68], 73, {69}, 87, (78), 90
  120. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68], 73, {69}, 87, 78, (90)
  121. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69], 73, 87, 78, 90
  122. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69], (73), 87, 78, 90
  123. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69], {73}, (87), 78, 90
  124. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69], {73}, 87, (78), 90
  125. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69], {73}, 87, 78, (90)
  126. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73], 87, 78, 90
  127. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73], (87), 78, 90
  128. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73], {87}, (78), 90
  129. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73], 87, {78}, (90)
  130. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78], 87, 90
  131. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78], (87), 90
  132. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78], {87}, (90)
  133. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78, 87], 90
  134. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78, 87], (90)
  135. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78, 87, 90]

As a result, it takes 135 steps. However, your friend can get a result like below. Notice that I marked revered book by !.

  1. (52), 33, 25, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  2. {52}, (33), 25, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  3. [33], {52}, 25, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  4. [33], {52}, (25), 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  5. [33, 25], {52}, 19, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  6. [33, 25], {52}, (19), 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  7. [33, 25, 19], {52}, 28, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  8. [33, 25, 19], {52}, (28), 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  9. [33, 25, 19, 28], {52}, 38, 37, 45, 73, 68, 61, 69, 87, 78, 90
  10. [33, 25, 19, 28], {52}, (38), 37, 45, 73, 68, 61, 69, 87, 78, 90
  11. [33, 25, 19, 28, 38], {52}, 37, 45, 73, 68, 61, 69, 87, 78, 90
  12. [33, 25, 19, 28, 38], {52}, (37), 45, 73, 68, 61, 69, 87, 78, 90
  13. [33, 25, 19, 28, 38, 37], {52}, 45, 73, 68, 61, 69, 87, 78, 90
  14. [33, 25, 19, 28, 38, 37], {52}, (45), 73, 68, 61, 69, 87, 78, 90
  15. [33, 25, 19, 28, 38, 37, 45], {52}, 73, 68, 61, 69, 87, 78, 90
  16. [33, 25, 19, 28, 38, 37, 45], {52}, (73), 68, 61, 69, 87, 78, 90
  17. [33, 25, 19, 28, 38, 37, 45], {52}, 73, (68), 61, 69, 87, 78, 90
  18. [33, 25, 19, 28, 38, 37, 45], {52}, 73, 68, (61), 69, 87, 78, 90
  19. [33, 25, 19, 28, 38, 37, 45], {52}, 73, 68, 61, (69), 87, 78, 90
  20. [33, 25, 19, 28, 38, 37, 45], {52}, 73, 68, 61, 69, (87), 78, 90
  21. [33, 25, 19, 28, 38, 37, 45], {52}, 73, 68, 61, 69, 87, (78), 90
  22. [33, 25, 19, 28, 38, 37, 45], {52}, 73, 68, 61, 69, 87, 78, (90)
  23. [33, 25, 19, 28, 38, 37, 45, !52!], 73, 68, 61, 69, 87, 78, 90
  24. [33, 25, 19, 28, 38, 37, 45, !52!], (73), 68, 61, 69, 87, 78, 90
  25. [33, 25, 19, 28, 38, 37, 45, !52!], {73}, (68), 61, 69, 87, 78, 90
  26. [33, 25, 19, 28, 38, 37, 45, !52!, 68], {73}, 61, 69, 87, 78, 90
  27. [33, 25, 19, 28, 38, 37, 45, !52!, 68], {73}, (61), 69, 87, 78, 90
  28. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61], {73}, 69, 87, 78, 90
  29. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61], {73}, (69), 87, 78, 90
  30. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69], {73}, 87, 78, 90
  31. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69], {73}, (87), 78, 90
  32. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69], {73}, 87, (78), 90
  33. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69], {73}, 87, 78, (90)
  34. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!], 87, 78, 90
  35. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!], (87), 78, 90
  36. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!], {87}, (78), 90
  37. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!, 78], {87}, 90
  38. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!, 78], {87}, (90)
  39. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!, 78, !87!], 90
  40. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!, 78, !87!], (90)
  41. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61, 69, !73!, 78, !87!, !90!]
  42. [33, 25, 19, 28, 38, 37, 45, !52!, 68, 61], 69, [!73!, 78, !87!, !90!]
  43. [33, 25, 19, 28, 38, 37, 45, !52!, 68], 61, 69, [!73!, 78, !87!, !90!]
  44. [33, 25, 19, 28, 38, 37, 45, !52!], 68, 61, 69, [!73!, 78, !87!, !90!]
  45. [33, 25, 19, 28, 38, 37, 45, !52!], (68), 61, 69, [!73!, 78, !87!, !90!]
  46. [33, 25, 19, 28, 38, 37, 45, !52!], {68}, (61), 69, [!73!, 78, !87!, !90!]
  47. [33, 25, 19, 28, 38, 37, 45, !52!, 61], {68}, 69, [!73!, 78, !87!, !90!]
  48. [33, 25, 19, 28, 38, 37, 45, !52!, 61], {68}, (69), [!73!, 78, !87!, !90!]
  49. [33, 25, 19, 28, 38, 37, 45, !52!, 61, !68!], 69, [!73!, 78, !87!, !90!]
  50. [33, 25, 19, 28, 38, 37, 45, !52!, 61, !68!], (69), [!73!, 78, !87!, !90!]
  51. [33, 25, 19, 28, 38, 37, 45, !52!, 61, !68!, !69!, !73!, 78, !87!, !90!]
  52. [33, 25, 19, 28, 38, 37, 45, !52!], 61, [!68!, !69!, !73!, 78, !87!, !90!]
  53. [33, 25, 19, 28, 38, 37, 45, !52!], (61), [!68!, !69!, !73!, 78, !87!, !90!]
  54. [33, 25, 19, 28, 38, 37, 45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  55. 33, [25, 19, 28, 38, 37, 45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  56. 33, 25, [19, 28, 38, 37, 45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  57. 33, 25, 19, [28, 38, 37, 45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  58. 33, 25, 19, 28, [38, 37, 45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  59. 33, 25, 19, 28, 38, [37, 45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  60. 33, 25, 19, 28, 38, 37, [45, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  61. 33, 25, 19, 28, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  62. (33), 25, 19, 28, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  63. {33}, (25), 19, 28, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  64. [25], {33}, 19, 28, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  65. [25], {33}, (19), 28, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  66. [25, 19], {33}, 28, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  67. [25, 19], {33}, (28), 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  68. [25, 19, 28], {33}, 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  69. [25, 19, 28], {33}, (38), 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  70. [25, 19, 28], {33}, 38, (37), 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  71. [25, 19, 28], {33}, 38, 37, (45), [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  72. [25, 19, 28, !33!], 38, 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  73. [25, 19, 28, !33!], (38), 37, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  74. [25, 19, 28, !33!], {38}, (37), 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  75. [25, 19, 28, !33!, 37], {38}, 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  76. [25, 19, 28, !33!, 37], {38}, (45), [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  77. [25, 19, 28, !33!, 37, !38!], 45, [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  78. [25, 19, 28, !33!, 37, !38!], (45), [!52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  79. [25, 19, 28, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  80. 25, [19, 28, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  81. 25, 19, [28, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  82. 25, 19, 28, [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  83. (25), 19, 28, [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  84. {25}, (19), 28, [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  85. [19], {25}, 28, [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  86. [19], {25}, (28), [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  87. [19, !25!], 28, [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  88. [19, !25!], (28), [!33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  89. [19, !25!, !28!, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  90. 19, [!25!, !28!, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  91. (19), [!25!, !28!, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  92. [!19!, !25!, !28!, !33!, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  93. [!19!, !25!, !28!, !33!], 37, [!38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  94. [!19!, !25!, !28!, !33!], (37), [!38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  95. [!19!, !25!, !28!, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!, 78, !87!, !90!]
  96. [!19!, !25!, !28!, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!], 78, [!87!, !90!]
  97. [!19!, !25!, !28!, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!], (78), [!87!, !90!]
  98. [!19!, !25!, !28!, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  99. [19, !25!, !28!, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  100. [19, 25, !28!, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  101. [19, 25, 28, !33!, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  102. [19, 25, 28, 33, !37!, !38!, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  103. [19, 25, 28, 33, 37, !38!, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  104. [19, 25, 28, 33, 37, 38, !45!, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  105. [19, 25, 28, 33, 37, 38, 45, !52!, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  106. [19, 25, 28, 33, 37, 38, 45, 52, !61!, !68!, !69!, !73!, !78!, !87!, !90!]
  107. [19, 25, 28, 33, 37, 38, 45, 52, 61, !68!, !69!, !73!, !78!, !87!, !90!]
  108. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, !69!, !73!, !78!, !87!, !90!]
  109. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, !73!, !78!, !87!, !90!]
  110. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, !78!, !87!, !90!]
  111. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78, !87!, !90!]
  112. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78, 87, !90!]
  113. [19, 25, 28, 33, 37, 38, 45, 52, 61, 68, 69, 73, 78, 87, 90]

As a result, your friend can get a result in 113 step. Which means 19% faster than you are.

Both methods are sorting algorithms, but they show very different performance characteristics. The next posts will analyze algorithm performance and compare different approaches.