PRACTICE PROBLEMS

* Indicate which sorting algorithm (Bubble, Insertion, Selection, Merge, Quick, or Heap) 
is demonstrated in each of the following traces.

The two columns are identical except for the |s that mark which area of the array
is currently being considered.  Some people claim the |s are confusing.  If you
feel that way, you can work with the left column instead.


[J U M B L E]	     [J U M B L E]
 U J M B L E	      U J M B L E
 U L M B J E	      U L M B J E
 E L M B J U	      E L M B J|U
 M L E B J U	      M L E B J|U
 J L E B M U	      J L E B|M U
 L J E B M U	      L J E B|M U
 B J E L M U	      B J E|L M U
 J B E L M U	      J B E|L M U
 E B J L M U	      E B|J L M U
 B E J L M U	      B|E J L M U
[B E J L M U]	     [B E J L M U]

Sort: __________   



[F A N T A S Y]	    [F A N T A S Y]
 A F N T A S Y	     A|F N T A S Y
 A A N T F S Y	     A A|N T F S Y
 A A F T N S Y	     A A F|T N S Y
 A A F N T S Y	     A A F N|T S Y
 A A F N S T Y	     A A F N S|T Y
 A A F N S T Y	     A A F N S T|Y
[A A F N S T Y]	    [A A F N S T Y]

Sort: __________   



[A L L I G A T O R]  [A L L I G A T O R]
 A L L I G A T O R   |A|L L I G A T O R
 A L L I G A T O R    A|L L|I G A T O R
 A L L I G A T O R   |A L L|I G A T O R
 A L L G I A T O R    A L L|G I|A T O R
 A G I L L A T O R   |A G I L L|A T O R
 A G I L L A T O R    A G I L L|A T|O R
 A G I L L A T O R    A G I L L A T|O R|
 A G I L L A O R T    A G I L L|A O R T|
 A A G I L L O R T   |A A G I L L O R T|
[A A G I L L O R T]  [A A G I L L O R T]


Sort: __________    



[C R O C O D I L E]  [C R O C O D I L E]
 C C D E O O I L R    C C D|E|O O I L R
 C C D E O O I L R    C C|D|E|O O I L R
 C C D E O O I L R    C|C|D|E|O O I L R
 C C D E O O I L R    C C D|E|O O I L R
 C C D E O O I L R    C C D|E|O O I L|R|
 C C D E I L O O R    C C D|E|I|L|O O|R|
 C C D E I L O O R    C C D|E|I|L|O O|R|
 C C D E I L O O R|   C C D|E|I|L|O|O|R|
[C C D E I L O O R]  [C C D E I L O O R]

Sort: __________    



[Q U I R K]	     [Q U I R K]
 Q U I R K	     |Q U|I R K
 Q I U R K	      Q|I U|R K
 Q I R U K	      Q I|R U|K
 Q I R K U 	      Q I R|K U|
 I Q R K U	     |I Q|R K U
 I Q R K U	      I|Q R|K U
 I Q K R U	      I Q|K R|U
 I Q K R U	     |I Q|K R U
 I K Q R U	      I|K Q|R U
 I K Q R U	     |I K|Q R U
[I K Q R U]	     [I K Q R U]

Sort: __________     



[D W A R V E N]	     [D W A R V E N]
 D W A R V E N	      D|W A R V E N
 D W A R V E N	      D W|A R V E N
 A D W R V E N	      A D W|R V E N
 A D R W V E N	      A D R W|V E N
 A D R V W E N	      A D R V W|E N
 A D E R V W N	      A D E R V W|N
 A D E N R V W|	      A D E N R V W|
[A D E N R V W]	     [A D E N R V W]

Sort: __________    



* Pick one of these sorts: Bubble, Insertion, Selection.
Show the effects of using that sort on the following array.
Show at least 4 (or more) intermediate steps.

  [D I S C O V E R]  
  
  
* Pick one of these sorts: Merge, Quick, Heap.
Show the effects of using that sort on the following array.
Show at least 3 (or more) intermediate steps.

  [F O U N D E R]