Data Structure Insertion Sort Trace Theory

void insertion_sort(int data[], int array_size)
{
   int round, insertion_point, current_value;
   
   for(round=1; round<array_size; round++)
   {
       cout << "For Loop - round: " << round <<  " start" << endl;
      
       current_value = data[round];
       insertion_point = round;
      
       //sort the left portion of the array from the IP until down (0)
       int i=0;
       while(insertion_point > 0 && data[insertion_point-1] > current_value)
       {
          i++;
          cout << "While Loop - round: " << i <<  " start" << endl;
          cout << "Insertion Point (IP): " << insertion_point << endl;
          
          cout << "Copying item [" << data[insertion_point-1] 
                    << "] from IP-1 [" << insertion_point - 1
                    << "] location to IP [" << insertion_point 
                    << "] location: " << endl;
               
         data[insertion_point]=data[insertion_point-1];         
          insertion_point--;
          print_array(data, array_size);
       }
      
       //put current_value its suppose location
       data[insertion_point] = current_value;
      
       cout << "For Loop - round: " << round << " finish" << endl;
   }
}

======================================================================

for loop >> 1st round

while loop >> 1st round:
------------------------
index: 0 1 2 3 4
array: 7 8 3 1 6
         IP

insertion_point (IP) = 1
current_value (CV) = value_at_IP = item[1] = 8 
value_below_IP = item[0] = 7


IP(1) > 0 && value_below_IP > current_value
true              7         >      8  
true                      false 
         false

while loop false
   exit loop
   put current_value(8) at IP (1) location >> item[1] = 8
         
index: 0 1 2 3 4
array: 7 8 3 1 6
  ^
array: 7 8 3 1 6  

DONE for loop 1st round (IP == 0) 
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------

for loop >> 2nd Round

while loop >> 1st round
-----------------------
index: 0 1 2 3 4
array: 7 8 3 1 6
   IP

insertion_point (IP) = 2
current_value (CV) = value_at_IP = item[2] = 3
value_below_IP = item[1] = 8

IP(2) > 0 && value_below_IP > current_value
true      &&        8       >      3
true      &&              true       

while loop true
   do Insertion Process
   put value_below_IP (item[1] = 8) at the IP location >> item[2] = 8


index: 0 1 2 3 4
array: 7 8 3 1 6
   ^
array: 7 8 8 1 6
 
---------------------------------------------------------

while loop >> 2nd round (for loop >> 2nd Round)
-----------------------
index: 0 1 2 3 4
array: 7 8 8 1 6
  IP  

insertion_point (IP) = 1
current_value (CV) = 3 (still no change, still at for loop >> 2nd Round)
value_below_IP = item[0] = 7

IP(1) > 0 && value_below_IP > current_value
true      &&        7       >      3
true      &&               true

while loop true
   do Insertion Process
   put value_below_IP (item[0] = 7) at the IP location >> item[1] = 7



index: 0 1 2 3 4
array: 7 8 8 1 6
  ^
array: 7 7 8 1 6

---------------------------------------------------------

while loop >> 3rd round (for loop >> 2nd Round)
-----------------------
index: 0 1 2 3 4
array: 7 7 8 1 6
 IP
 
insertion_point (IP) = 0
current_value = 3 (still no change, still at for loop >> 2nd Round)//simpan 3 kt sini...3tak                               hilang

value_below_IP = item[-1] = NOT EXIST! == false

IP(0) > 0
  0   > 0
    false (short circuit)

while loop false *****
   exit loop
   put current_value(3) at IP (0) location >> item[0] = 3

 
index: 0 1 2 3 4
array: 7 7 8 1 6
 ^
array: 3 7 8 1 6  

DONE for loop 2nd round
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------

for loop >> 3rd Round

while loop >> 1st round
---------------------
index: 0 1 2 3 4
array: 3 7 8 1 6
                                IP
insertion_point (IP) = 3
current_value (CV) = value_at_IP = item[3] = 1
value_below_IP = item[2] = 8

IP(3) > 0  && value_below_IP > current_value
    true   &&      8         >      1
    true   &&               true
          true  

while loop true
   do Insertion Process
   put value_below_IP (item[2] = 8) at the IP location >> item[3] = 8


index: 0 1 2 3 4
array: 3 7 8 1 6
    ^
array: 3 7 8 8 6
 
---------------------------------------------------------
                                
while loop >> 2nd round (for loop >> 3rd Round)
-----------------------
index: 0 1 2 3 4                                
array: 3 7 8 8 6
   IP
   
insertion_point (IP) = 2
current_value (CV) = 1  (still no change, still at for loop >> 3rd Round)
value_below_IP = item[1] = 7

IP(2) > 0  && value_below_IP > current_value
    true   &&      7         >      1
    true   &&               true
          true  

while loop true
   do Insertion Process
   put value_below_IP (item[1] = 7) at the IP location >> item[2] = 7
 
index: 0 1 2 3 4                                
array: 3 7 8 8 6
   ^
array: 3 7 7 8 6   

---------------------------------------------------------
                                
while loop >> 3rd round (for loop >> 3rd Round)
-----------------------

index: 0 1 2 3 4                       
array: 3 7 7 8 6   
  IP
  
insertion_point (IP) = 1
current_value (CV) = 1  (still no change, still at for loop >> 3rd Round)
value_below_IP = item[0] = 3

IP(2) > 0  && value_below_IP > current_value
    true   &&      3         >      1
    true   &&               true
          true  

while loop true
   do Insertion Process
   put value_below_IP (item[0] = 3) at the IP location >> item[1] = 3
 
index: 0 1 2 3 4                       
array: 3 7 7 8 6    
  ^
array: 3 3 7 8 6      

---------------------------------------------------------
                                
while loop >> 4th round (for loop >> 3rd Round)
-----------------------

index: 0 1 2 3 4                       
array: 3 3 7 8 6      
 IP
 
insertion_point (IP) = 0
current_value (CV) = 1 (still no change, still at for loop >> 3rd Round)
value_below_IP = item[-1] = NOT EXIST!

IP(0) > 0
  0   > 0
    false (short circuit)

while loop false
   exit loop
   put current_value(1) at IP (0) location >> item[0] = 1 

index: 0 1 2 3 4                       
array: 3 3 7 8 6      
 ^
array: 1 3 7 8 6       

DONE for loop 3rd round
---------------------------------------------------------------------------------
---------------------------------------------------------------------------------

for loop >> 4th Round

while loop >> 1st round
---------------------

index: 0 1 2 3 4                       
array: 1 3 7 8 6   
     IP
insertion_point (IP) = 4
current_value (CV) = value_at_IP = item[4] = 6
value_below_IP = item[3] = 8

IP(4) > 0  && value_below_IP > current_value
    true   &&      8         >      6
    true   &&               true
          true  

while loop true
   do Insertion Process
   put value_below_IP (item[3] = 8) at the IP location >> item[4] = 8
 
index: 0 1 2 3 4                       
array: 1 3 7 8 6   
     ^
array: 1 3 7 8 8

---------------------------------------------------------        

while loop >> 2nd round (for loop >> 4th Round)
-----------------------

index: 0 1 2 3 4                       
array: 1 3 7 8 8        
    IP

insertion_point (IP) = 3
current_value (CV) = 6 (still no change, still at for loop >> 4th Round)
value_below_IP = item[2] = 7

IP(3) > 0  && value_below_IP > current_value
    true   &&      7         >      6
    true   &&               true
          true  

while loop true
   do Insertion Process
   put value_below_IP (item[2] = 7) at the IP location >> item[3] = 7
 
index: 0 1 2 3 4                       
array: 1 3 7 8 8        
    ^
array: 1 3 7 7 8 
---------------------------------------------------------           

while loop >> 3rd round (for loop >> 4th Round)
-----------------------

index: 0 1 2 3 4                       
array: 1 3 7 7 8            
   IP

insertion_point (IP) = 2
current_value = 6 (still no change, still at for loop >> 4th Round)
value_below_IP = item[1] = 3

IP(2) > 0  && value_below_IP > current_value
    true   &&      3         >      6
    true   &&               false
          false  

while loop false
   exit loop
   put current_value(6) at IP (2) location >> item[2] = 1  

index: 0 1 2 3 4                       
array: 1 3 7 7 8            
   ^
array: 1 3 6 7 8               

DONE FINALLY!
----------------------------------------------------------

SHORT CUT 

round = 1
CV = 8
7 8 3 1 6
  ^

[7 > 8] == false
7 8 3 1 6

============
round = 2
CV = 3
7 8 3 1 6
    ^

[8 > 3] => true
7 8 8 1 6
  ^

[7 > 3] => true
7 7 8 1 6
^

IP=0 => false //so insert current value at the IP=0
3 7 8 1 6

===========
round = 3
CV=1
3 7 8 1 6
      ^

[8 > 1] => true
3 7 8 8 6
    ^

[7 > 1] => true
3 7 7 8 6
  ^

[3 > 1] => true
3 3 7 8 6
^

IP=0 => false //so insert current value at the IP=0

1 3 7 8 6

=============
round = 4
CV=6
1 3 7 8 6
        ^

[8 > 6] => true
1 3 7 8 8
      ^

[7 > 6] => true
1 3 7 7 8
    ^
[3 > 6] => false  //so insert current value at the IP=0

1 4 6 7 8

==============
round=5 (round<array_size => false)
DONE

===========================================

CV=8
7 8 3 1 6
  ^

[7 > 8]
7 8 3 1 6
-------------

CV=3
7 8 3 1 6
    ^

[8 > 3]
7 8 8 1 6
  ^

[7 > 3]
7 7 8 1 6
^

3 7 8 1 6
---------------

CV=1
3 7 8 1 6
      ^

[8>1]
3 7 8 8 6
    ^

[7>1]
3 7 7 8 6
  ^

[3>1]
3 3 7 8 6
^

1 3 7 8 6
-----------------

CV=6
1 3 7 8 6
        ^

[8>6]
1 3 7 8 8 
      ^

[7>6]
1 3 7 7 8
    ^

[3>6]
1 3 6 7 8
------------------

round=5 (round<array_size => false)
DONE

-----------------------------------------------------------------------------------

WORST CASE!

CV=3 
4 3 2 1
  ^

[4 > 3]
4 4 2 1

4 4 2 1
^

3 4 2 1
-------------

CV=2 
3 4 2 1
    ^

[4 > 2]
3 4 4 1

3 4 4 1
  ^

[3 > 2]
3 3 4 1

3 3 4 1
^

2 3 4 1
-------------

CV=1
2 3 4 1
      ^

[4 > 1]
2 3 4 4

2 3 4 4
    ^

[3 > 1]
2 3 3 4

2 3 3 4
  ^

[2 > 1]
2 2 3 4

2 2 3 4
^

1 2 3 4
-------------

DONE 

-----------------------------------------------------------------------------------

BEST CASE

CV=2
1 2 3 4
  ^
[1 > 2]
1 2 3 4

--------
CV=3
1 2 3 4
    ^

[2 > 3]
1 2 3 4

-------
CV=4
1 2 3 4
      ^

[3 > 4]
1 2 3 4

DONE

-----------------------------------------------------------------------------------
Another example: 7 8 3 1 6

CV=8
7 8 3 1 6
  ^

[7 > 8]
7 8 3 1 6
----------

CV=3
7 8 3 1 6
    ^

[8 > 3]
7 8 8 1 6
  ^

[7 > 3]
7 7 8 1 6
^

3 7 8 1 6
----------

CV=1
3 7 8 1 6
      ^

[8 > 1]
3 7 8 8 6
    ^

[7 > 1]
3 7 7 8 6
  ^

[3 > 1]
3 3 7 8 6
^

1 3 7 8 6
----------

CV=6
1 3 7 8 6
        ^
[8 > 6]
1 3 7 8 8
      ^

[7 > 6]
1 3 7 7 8
    ^

[3 > 6]
1 3 6 7 8

DONE