Quick Sort

ကြန္ပ်ဴတာ သိပၸံ (Computer Science) ေလ့လာသူေတြနဲ႕ သတင္းနည္းပညာ (IT) ေလ့လာသူေတြအတြက္ အစီအစဥ္ဆြဲနည္း (Programming) သင္ခန္းစာေတြမွာ မပါမျဖစ္ကေတာ့ အခ်က္အလက္မ်ားကုိ စီျခင္း (Sorting) အစီအစဥ္ပါပဲ။ Sorting စီတဲ့ နည္းလမ္းစဥ္ (Algorithm) အမ်ိဳးေပါင္း ေျမာက္မ်ားစြာ ရွိတဲ့အထဲက Bubble Sort, Counting Sort, Insertion Sort, Selection Sort နဲ႕ Quick Sort တုိ႕ဟာ ထင္ရွားပါတယ္။ (စာေရးသူ အႀကိဳက္ဆံုးကေတာ့ Selection Sort ျဖစ္ၿပီး အေၾကာင္းရင္းကေတာ့ နားလည္ရလြယ္လြန္းလုိ႕ ျဖစ္ပါတယ္။) ဒါေပမဲ့ လက္ေတြ႕ဘ၀မွာ အသံုး၀င္တာကေတာ့ နားလည္ရခက္၊ ေရးရတာ လက္၀င္တဲ့ Quick Sort ေလ။ ေရးလုိက္ၾကတဲ့ အစီအစဥ္ေတြတုိင္းမွာ စီစရာ (object, data type) တစ္မ်ိဳး ေပၚလာတုိင္း Quick Sort ကုိ တစ္ခါ ထထ ေရးရမယ္ ဆုိတာကေတာ့ လြန္လြန္းပါတယ္။ ဒါေၾကာင့္ C/C++ စံသတ္မွတ္ခ်က္မွာ Array အားလံုးကို စီႏုိင္ဖုိ႕ qsort ဆုိတဲ့ function ပါေနတာ ျဖစ္ပါတယ္။ ဒီေဆာင္းပါးမွာ အဲဒီ qsort ကုိ အသံုးျပဳနည္းကို ေရးသားေပးမွာ ျဖစ္ပါတယ္။

qsort ရဲ႕ သတ္မွတ္ခ်က္မွာ အစီအစဥ္ေရးသားသူ (programmer) ဒါမွမဟုတ္ ကုဒ္ဒါကို ၿခိမ္းေျခာက္ေနတာကေတာ့ pointer ေတြပါပဲ။ ရုိးရုိး Data Pointer ေတြတင္မကပဲ Function Pointer ႀကီးပါ ပါေနေတာ့ Pointer ဆုိရင္ ေက်ာစိမ့္ေနၾကလူေတြ လန္႕ကုန္တာ မဆန္းပါဘူး။ ဒါေပမဲ့ အေက်ာသိရင္ လြယ္လြယ္ကေလးပါ။ qsort ရဲ႕ အဓိပၸါယ္ သတ္မွတ္ခ်က္ကို အရင္ၾကည့္ရေအာင္ေနာ္။

void qsort ( void * base, size_t num, size_t size, int ( * comparator ) ( const void *, const void * ) );

ပထမဆံုး return type ကေတာ့ ဒီ function ဟာ return မျပန္ပါဘူးလုိ႕ အဓိပၸါယ္ရပါတယ္။ ဆုိလုိတာက ေပးလိုက္တဲ့ array ကုိ စီပဲ စီေပးမယ္။ ဘာ ဂဏန္းမွ တြက္ၿပီး အေျဖမထုတ္ေပးပါဘူးေပါ့။

ပထမဆံုး parameter က စီရမဲ့ array ရဲ႕ ပထမဆံုးအကြက္ရဲ႕ လိပ္စာ (address) ပါ။ အမ်ားေၾကာက္တဲ့ pointer ေပါ့။ Array အားလံုးဟာ Fix Pointer ေတြ ျဖစ္တဲ့အတြက္ စိတ္ခ်လက္ခ်ပဲ array name ကုိ ျဖည့္လုိက္လုိ႕ရပါတယ္။

ဒုတိယ parameter ကေတာ့ Array ရဲ႕ အရြယ္အစား (size) ျဖစ္ပါတယ္။ C/C++ မွာ Array ရဲ႕ size ကုိ compile-time/run-time check မလုပ္ပဲ ကုဒ္ဒါကပဲ အၿမဲ ကုိင္တြယ္ ႀကီးၾကပ္ရတာမုိ႕ ဒါကို ထည့္ေပးရတာပါ။ ႏုိ႕မုိ႕ရင္ ဘယ္ႏွခု စီရမလဲ မသိပဲ ျဖစ္ေနမယ္ေလ။ ကုိယ့္ Array မွာ Element ၁၀ ခုပါရင္ 10 လုိ႕ထည့္ေပါ့။ Variable တစ္ခုခု ထည့္လုိ႕လဲ ရပါတယ္။

တတိယ parameter ကေတာ့ စီခ်င္တဲ့ Array Element တစ္ခုခ်င္းရဲ႕ အရြယ္အစားေပါ့။ အဲဒါမွ အဲဒီ မွတ္ဥာဏ္တံုးႀကီး (memory block) ေတြကို ေရႊ႕လုိ႕ရမယ္ေလ။ ဒါလဲ မခက္ပါဘူး။ sizeof(element) လုိ႕ ေပးလုိက္ရင္ရပါတယ္။

စတုတၳနဲ႕ ေနာက္ဆံုး parameter ကေတာ့ နည္းနည္း ရွင္းျပရ လက္၀င္ပါတယ္။ ဒါဟာ Function Pointer ႀကီးျဖစ္ပါတယ္။ ကုိယ့္ဘာသာကုိယ္ သတ္မွတ္ထားတဲ့ Element ေတြကို ႏိႈင္းယွဥ္ခ်င္ရင္ ဒီ Function နဲ႕ တြက္ဆုိၿပီး ေျပာရတဲ့ သေဘာပါ။ (ေနာက္တမ်ိဳးေျပာရရင္ အဲဒီ Function ႀကီးကုိ qsort ကေန လွမ္းေခၚမွာ ျဖစ္ပါတယ္။ အဲဒီ Function ႀကီးက qsort ဆီကုိ ေရွ႕ကေကာင္က ငယ္ရင္ အႏႈတ္ကိန္း၊ တူရင္ သုည၊ ႀကီးရင္ အေပါင္းကိန္း တစ္ခုခု return ျပန္ရပါမယ္။) အဲဒီ Function ႀကီးရဲ႕ ပံုစံကလဲ

int function_name(const void* a, const void* b);

ပဲျဖစ္ရပါမယ္။ ပုိနားလည္လြယ္ေအာင္ ဥပမာေလးနဲ႕ ၾကည့္ရေအာင္ေနာ္။

ဥပမာ ၀န္ထမ္းေတြကို လစာ အမ်ားဆံုးကေန အနည္းဆံုးကို စီၿပီးသား အစီရင္ခံစာထုတ္ေပးတဲ့ အစီအစဥ္ကုိ လုိခ်င္တယ္။ တကယ္လုိ႕ လစာတူေနရင္ လုပ္သက္ရင့္တဲ့လူကုိ ေရွ႕မွာ ထားခ်င္တယ္ ဆုိပါစုိ႕။ ဒါဆုိရင္ ၀န္ထမ္းေတြရဲ႕ အခ်က္အလက္ေတြကုိ သိမ္းဖုိ႕ class တစ္ခု ေဆာက္ရပါမယ္။

class employee{

int experience; //in year

float salary; //in kyat

/* Blar Blar Blar */

public:

bool operator < (employee &e) { If(this->salary == e.salary) return (this->experience <>salary < temp_e =" (employee*)" temp_f =" (employee*)">' ကုိ ဒီလုိေလး temp_e->my_emp_function() ဆုိၿပီးေတာ့ သံုးေပးရပါမယ္။) အဲဒီ '*' ေလးကို ထည့္ၿပီး operator '>' နဲ႕ ႏိႈင္းယွဥ္လုိ႕ရလာတဲ့ အေျဖေပၚမူတည္ၿပီး -1 သုိ႕မဟုတ္ +1 ကို qsort အတြက္ return ျပန္ေပးလုိက္ရပါမယ္။

ဒီ Function ေလးေရးလုိ႕ အခ်ိဳးေျပသြားၿပီဆုိရင္ေတာ့ qsort ကုိ စိတ္ေအးခ်မ္းသာ အသံုးျပဳႏုိင္ပါၿပီ။ (employee ရဲ႕ private member ေတြကို accessor method ေတြကေနတဆင့္ ေခၚထားတာ သတိျပဳပါ။ တကယ္တမ္း ေရးတဲ့အခါက်ေတာ့ သတိလက္လြတ္ ဒီတုိင္း ေရးမိတတ္ပါတယ္။ အဲဒီလုိေရးခ်င္ရင္ေတာ့လဲ friend လုပ္လုိက္ေပါ့ဗ်ာ၊ ေနာ။) ေအာက္မွာက main Function ပါ။

/* preprocessor Yada Yada Yada */

void main(void)

{

employee myEmployeeArray[NUM_OF_EMPLOYEE];

/* input data into myEmployeeArray */

qsort(myEmployeeArray, NUM_OF_EMPLOYEE, sizeof(employee), employee_comparer);

/* output sorted myEmployeeArray */

}

qsort ကုိ လြယ္လြယ္ေခၚၿပီး ကုဒ္ဒါအေပါင္း သက္သာၾကပါေစေၾကာင္း …

စာေရးသူ ေရးသားစမ္းသပ္ထားေသာ Code ကုိ ရယူရန္

Source : ကိုေလာရွည္ blog http://opera.lawshay.com/2009/08/quick-sort-sorting.html