Coding Sample
if (first<last)
{
cut = partition(T, first,last);
quickSort(T, first,cut);
quickSort (T, cut+1, last);
}
int partition(int T[], int first,int last)
{
int pivot, temp;
int loop, cutPoint, bottom, top;
pivot=T[first];
bottom = first; top = last;
loop=1; //always TRUE
while (loop)
{
while (T[top]>pivot)
{
// find smaller value than
// pivot from top array
top--;
}
while(T[bottom]<pivot)
{
//find larger value than pivot from
//bottom
bottom++;
}
if (bottom<top)
{
//swap - sort the data
//data less then pivot, on the left
//data bigger then pivot, on the right
temp=T[bottom];
T[bottom]=T[top];
T[top]=temp;
}
else
{
loop=0;
cutPoint = top;
}
}
}
//////////////////////////////////////////////
top = last indeks of array
btm = start indeks of array
pivot = data at start indeks = btm = 1
0 1 2 3 4
---------
1 5 3 2 4
^ #
decrement of top:
array[top] > pivot, top--
4>1, true, top-- = 3
2>1, true, top-- = 2
3>1, true, top-- = 1
5>1, true, top-- = 0
increment of btm:
array[btm] < pivot, btm++
1<1, false, btm=0
0 1 2 3 4
---------
1 5 3 2 4
^
#
is true btm < top
swap
else
return cutPoint=top //0
quickSort(T, 0, 0)
quickSort(T, 1, 4)
quickSort(t, 0, 4) //pivot=1
0 1 2 3 4
---------
1 5 3 2 4
^
#
is it true 1<4?True Move next
is it true 1<2?True move
is it true 1<5?true no swapping
cutPoint(t, 0, 4) = 0
0 1 2 3 4
---------
1 5 3 2 4 // break the 1, coz 1 is not less than 1 so false
quickSort(0, 0) //first<last==F quickSort(1, 4) //pivot=5
[0] 1 2 3 4 //5<4? false..swap
1 -------
5 3 2 4
^ # swap
4 3 2 5
^ #
4 3 2 5
#
^
cutPoint(t, 1, 4) = 4
1 2 3 4
-------
4 3 2 5
quickSort(t, 1, 4) //pivot=4 quickSort(t, 5, 4) first<last==F
1 2 3 4 no result
-------
4 3 2 5
^ #
# swap
2 3 4 5
^ #
^
^
cutPoint(t, 1, 4) = 3
1 2 3 4
-------
2 3 4 5
quickSort(t, 1, 3) //pivot=2 quickSort(t, 4, 4) // first<last==F
1 2 3 [4]
----- 5
2 3 4
^ #
#
#
cutPoint(t, 1, 3) = 1
//first<last==F
quickSort(t, 1, 1) quickSort(t, 2, 3) //pivot=3
[1] 2 3
2 ---
3 4
^ #
#
pembahagi(t, 2, 3) = 2
//first<last==F //first<last==F
quickSort(t, 2, 2) quickSort(3, 3)
[2] [3]
3 4
How to trace example
----------------------------------------------------
----------------------------------------------------
isihCepat(0, 8): done
^=btm=0
#=top=8
pivot = item[btm] = item[0] = 5
[0] [1] [2] [3] [4] [5] [6] [7] [8]
5 15 7 2 4 1 8 10 3
^ #
TOP:
3>5, false, tops=8
BTM:
5<5, false, btm=0
* no change for " btm - top "
btm<top
0<8, true swap(5, 3)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 15 7 2 4 1 8 10 5
^ #
----------------
TOP:
5>5, false, top=8
BTM:
3<5, true, btm++=1 //kalau true buat increment sampai dia jadi salah
15<5, false, btm=1
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 15 7 2 4 1 8 10 5
^ #
1<8, swap(15, 5)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 5 7 2 4 1 8 10 15
^ #
----------------
TOP:
15>5, true, top--=7
10>5, true, top--=6
8>5, true, top--=5
1>5, false, top=5
BTM:
5<5, false, btm=1
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 5 7 2 4 1 8 10 15
^ #
1<5, swap(1, 5)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 1 7 2 4 5 8 10 15
^ #
----------------
TOP:
5>5, false, top=5
BTM:
1<5, true, btm++=2
7<5, false, btm=2
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 1 7 2 4 5 8 10 15
^ #
2<5, swap(7, 5)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 1 5 2 4 7 8 10 15
^ #
----------------
TOP:
7>5, true, top--=4
4>5, false, top=4
BTM:
5<5, false, btm=2
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 1 5 2 4 7 8 10 15
^ #
2<4, swap(5, 4)
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 1 4 2 5 7 8 10 15
^ #
----------------
TOP:
5>5, false, top=4
BTM:
4<5, true, btm++=3
2<5, true, btm++=4
5<5, false, btm=4
[0] [1] [2] [3] [4] [5] [6] [7] [8]
3 1 4 2 5 7 8 10 15
#
^
4<4, false //when top and bottom is the same index,you already reach the cutpoint
>> return atas (4)
isihCepat(0, 4) done
isihCepat(5, 8) //after value more than 5 already sorted,we break it into 2 pieces then focus just on value below 5
----------------------------------------------------
----------------------------------------------------
isihCepat(0, 4): done
^=btm=0
#=top=4
pivot = item[btm] = item[0] = 3
[0] [1] [2] [3] [4]
3 1 4 2 5
^ #
TOP:
5>3, true, top--=3
2>3, false, top=3
BTM:
3<3, false, btm=0
[0] [1] [2] [3] [4]
3 1 4 2 5
^ #
0<3, swap(3, 2)
[0] [1] [2] [3] [4]
2 1 4 3 5
^ #
-------------------
TOP:
3>3, false, top=3
BTM:
2<3, true, btm++=1
1<3, true, btm++=2
4<3, false, btm=2
[0] [1] [2] [3] [4]
2 1 4 3 5
^ #
2<3
swap(4, 3)
[0] [1] [2] [3] [4]
2 1 3 4 5
^ #
-------------------
TOP:
4>3, true, top--=2
3>3, false, top=2
BTM:
3<3, false, btm=2
[0] [1] [2] [3] [4]
2 1 3 4 5
^
#
2<2
>> return top (2)
isihCepat(0, 2) - done
isihCepat(3, 4) //after value more than 3 already sorted,we break it into 2 pieces then focus just on value below 3
------------------------------------
------------------------------------
isihCepat(0, 2): done
^=btm=0
#=top=2
pivot = item[btm] = item[0] = 2
[0] [1] [2]
2 1 3
^ #
TOP
3>2, true, top--=1
1>2, false, top=1
BTM:
2<2, false, btm=0
[0] [1] [2]
2 1 3
^ #
0<1, swap(2, 1)
[0] [1] [2]
1 2 3
^ #
---------------
TOP:
2>2, false, top=1
BTM:
1<2, true, btm++=1
2<2, false, btm=1
[0] [1] [2]
1 2 3
#
^
1<1
>> return top (1)
isihCepat(0, 1): done
isihCepat(2, 2): [2]
3
------------------------------------
------------------------------------
isihCepat(0, 1): done
^=btm=0
#=top=1
pivot = item[btm] = item[0] = 1
[0] [1]
1 2
^ #
TOP
2>1, true, top--=0
1>1, false, top=0
BTM:
1<1, false, btm=0
[0] [1]
1 2
^
#
0<0
>> return top (0)
isihCepat(0, 0): [0]
1
isihCepat(1, 1): [1]
2
---------------------------------------------------------------------
---------------------------------------------------------------------
isihCepat(0, 4)
pivot=1
0 1 2 3 4
---------
1 5 3 2 4
^ #
after btm-top increment/reduce
1 5 3 2 4
^
#
isihCepat(0, 0): [0]
1
isihCepat(1, 4)
--------------------------
isihCepat(1, 4)
pivot=5
1 2 3 4
-------
5 3 2 4
^ #
after btm-top increment/reduce
5 3 2 4
^ #
1<4
swap (5, 4)
4 3 2 5
^ #
after btm-top increment/reduce
4 3 2 5
#
^
return 4;
isihCepat(1, 4)
isihCepat(5, 4): no result
-------------------
isihCepat(1, 4)
pivot=4
1 2 3 4
-------
4 3 2 5
^ #
after btm-top increment/reduce
4 3 2 5
^ #
1<3
swap(4, 2)
2 3 4 5
^ #
after btm-top increment/reduce
2 3 4 5
#
^
return 3;
isihCepat(1, 3)
isihCepat(4, 4): [4]
5
--------------------
isihCepat(1, 3)
pivot=2
1 2 3
-----
2 3 4
^ #
after btm-top increment/reduce
2 3 4
^
#
return 1;
isihCepat(1, 1): [1]
2
isihCepat(2, 3):
--------------------
isihCepat(2, 3):
pivot=3
2 3
---
3 4
^ #
after btm-top increment/reduce
3 4
^
#
return 2;
isihCepat(2, 2): [2]
3
isihCepat(3, 3): [3]
4
0 Comments