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
0 Comments