[2] OUTPUT FOR SHIN SORT WITH 16 KEYS
<---------------
Shin sort starts from here ----------------->
Program reads key strings, stores them
into Shin tree, and
performs preorder traversal to print
every node value out.
Preorder after
key #1, "LEE" is inserted.
L E E
-----------------------------------------------------------------
Preorder after
key #2, "KIM" is inserted.
K I M L E E
-----------------------------------------------------------------
Preorder after
key #3, "KING" is inserted.
K I M N G L E E
-----------------------------------------------------------------
Preorder after
key #4, "KITE" is inserted.
K I M N G T E L
E E
-----------------------------------------------------------------
Preorder after
key #5, "KENT" is inserted.
K E N T I M N G
T E L E E
-----------------------------------------------------------------
Preorder after
key #6, "KIN" is inserted.
K E N T I M N:1
G T E L E E
-----------------------------------------------------------------
Preorder after
key #7, "KANT" is inserted.
K A N T E N T I
M N:1 G T E L E E
-----------------------------------------------------------------
Preorder after
key #8, "KILE" is inserted.
K A N T E N T I
L E M N:1 G T E L E E
-----------------------------------------------------------------
Preorder after
key #9, "KIMMY" is inserted.
K A N T E N T I
L E M:1 M Y N:1 G T E L E E
-----------------------------------------------------------------
Preorder after
key #10, "KIMBERLY" is inserted.
K A N T E N T I
L E M:1 B E R L Y M Y N:1 G T E L E E
-----------------------------------------------------------------
Preorder after
key #11, "KITE" is inserted.
K A N T E N T I
L E M:1 B E R L Y M Y N:1 G T E:1 L E E
-----------------------------------------------------------------
Preorder after
key #12, "KID" is inserted.
K A N T E N T I
D L E M:1 B E R L Y M Y N:1 G T E:1 L E E
-----------------------------------------------------------------
Preorder after
key #13, "KINS" is inserted.
K A N T E N T I
D L E M:1 B E R L Y M Y N:1 G S T E:1 L E E
-----------------------------------------------------------------
Preorder after
key #14, "JACOB" is inserted.
J A C O B K A N
T E N T I D L E M:1 B E R L Y M Y N:1 G S T E:1
L E E
-----------------------------------------------------------------
Preorder after
key #15, "KANG" is inserted.
J A C O B K A N
G T E N T I D L E M:1 B E R L Y M Y N:1 G S T E:1
L E E
-----------------------------------------------------------------
Preorder after
key #16, "KITE" is inserted.
J A C O B K A N
G T E N T I D L E M:1 B E R L Y M Y N:1 G S T E:2
L E E
-----------------------------------------------------------------
----------------<Input
List for the 16 Keys>----------------
LEE; KIM; KING; KITE; KENT; KIN; KANT;
KILE; KIMMY; KIMBERLY; KITE; KID; KINS;
JACOB; KANG; KITE;
________________________________________________________________
Preorder
traversal after 16 keys are inserted into the tree.
J A C O B K A N
G T E N T I D L E M:1 B E R L Y M Y N:1 G S T E:2
L E E
________________________________________________________________
Inorder
traversal after 16 keys are inserted into the tree.
B O C A J G T N
A T N E D E L Y L R E B Y M M:1 G S N:1 E:2 T I
K E E L
________________________________________________________________
Postorder
traversal after 16 keys are inserted into the tree.
B O C A T G N T
N E Y L R E Y M B S G E:2 T N:1 M:1 L D I E A E
E L K J
________________________________________________________________
<-----------
Printing Shin tree starts from here ----------->
Traversing the tree in preorder, it will
print out keys and
show how stack is changed. It will push a node character
into the stack and pop one from the
stack. The following
shows how a key character is inserted
into and deleted from
the stack. A key will be printed out whenever
collected
stack items make a full key.
'J' pushed
--> 'A' pushed --> 'C' pushed --> 'O' pushed -->
'B' pushed
-->
The stored key,
"JACOB", is printed out here.
'B' popped
--> 'O' popped --> 'C' popped --> 'A' popped -->
'J' popped
--> 'K' pushed --> 'A' pushed --> 'N' pushed -->
'G' pushed
-->
The stored key,
"KANG", is printed out here.
'G' popped
--> 'T' pushed -->
The stored key,
"KANT", is printed out here.
'T' popped
--> 'N' popped --> 'A' popped --> 'E' pushed -->
'N' pushed
--> 'T' pushed -->
The stored key,
"KENT", is printed out here.
'T' popped
--> 'N' popped --> 'E' popped --> 'I' pushed -->
'D' pushed
-->
The stored key,
"KID", is printed out here.
'D' popped
--> 'L' pushed --> 'E' pushed -->
The stored key,
"KILE", is printed out here.
'E' popped
--> 'L' popped --> 'M' pushed -->
The stored key,
"KIM", is printed out here.
'B' pushed
--> 'E' pushed --> 'R' pushed --> 'L' pushed -->
'Y' pushed
-->
The stored key,
"KIMBERLY", is printed out here.
'Y' popped
--> 'L' popped --> 'R' popped --> 'E' popped -->
'B' popped
--> 'M' pushed --> 'Y' pushed -->
The stored key,
"KIMMY", is printed out here.
'Y' popped
--> 'M' popped --> 'M' popped --> 'N' pushed -->
The stored key,
"KIN", is printed out here.
'G' pushed
-->
The stored key,
"KING", is printed out here.
'G' popped
--> 'S' pushed -->
The stored key,
"KINS", is printed out here.
'S' popped
--> 'N' popped --> 'T' pushed --> 'E' pushed -->
The stored key,
"KITE", is printed out here.
The stored key,
"KITE", is printed out here.
The stored key,
"KITE", is printed out here.
'E' popped
--> 'T' popped --> 'I' popped --> 'K' popped -->
'L' pushed
--> 'E' pushed --> 'E' pushed -->
The stored key,
"LEE", is printed out here.
'E' popped
--> 'E' popped --> 'L' popped -->
----------------<Input
List for the 16 Keys>----------------
LEE; KIM; KING; KITE; KENT; KIN; KANT;
KILE; KIMMY; KIMBERLY; KITE; KID; KINS;
JACOB; KANG; KITE;
----------------<Sorted
List for the 16 Keys>----------------
JACOB; KANG; KANT; KENT; KID; KILE; KIM;
KIMBERLY; KIMMY; KIN; KING; KINS; KITE;
KITE; KITE; LEE;
<----------------
Shin search starts from here ---------------->
The following output will show what keys
are looked for and
how characters in a key are searched one
after another in the
tree. The search result, found or not found,
will be printed
after all.
1. Search the Key: KANT Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
A Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 0
Character of the Node:
T Counter Value of the
Node: 0
The key,
"KANT", is found in the Shin tree.
2. Search the Key: KIM Size: 3
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node: M Counter Value of the Node: 1
The key,
"KIM", is found in the Shin tree.
3. Search the Key: KI Size: 2
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
The key,
"KI", is not found.
4. Search the Key: KIMM Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
M Counter Value of the
Node: 1
Character of the Node:
M Counter Value of the
Node: 0
The key,
"KIMM", is not found.
5. Search the Key: SMITH Size: 5
The key,
"SMITH", is not found.
6. Search the Key: KIND Size: 4
Character of the Node:
K Counter Value of the Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
N Counter Value of the
Node: 1
The key,
"KIND", is not found.
7. Search the Key: KITE Size: 4
Character of the Node:
K Counter Value of the
Node: 0
Character of the Node:
I Counter Value of the
Node: 0
Character of the Node:
T Counter Value of the
Node: 0
Character of the Node:
E Counter Value of the
Node: 2
The key,
"KITE", is found in the Shin tree.
8. Search the Key: J Size: 1
Character of the Node:
J Counter Value of the
Node: 0
The key,
"J", is not found.
9. Search the Key: LEED Size: 4
Character of the Node:
L Counter Value of the
Node: 0
Character of the Node:
E Counter Value of the
Node: 0
Character of the Node:
E Counter Value of the
Node: 0
The key,
"LEED", is not found.