හොඳයි අද කතා කරමු Sorting Algorithms ගැන. ඒ වගේම ඒවගේ තියන වැදගත්කම සහ භාවිතා වෙන අවස්ථා ගැනත් බලමු. මොකද්ද මේ Sorting කියන්නේ ?
පිළිවෙලකට පෙළගස්වනවා කිව්වොත් වැරද්දක් නෑ නේද ? ඔව් එහෙම තමයි. ඇයි අපි පිළිවෙලකට පෙළගස්වන්නේ. ඇත්තෙන්ම කිව්වොත් හොයා ගන්න ලේසි වෙන්න නේද ? මොකද පිළිවෙලකට තිබ්බේ නැත්නම් මොකක් හරි හොයන්න ගියහම ඔක්කොම හාර අවුස්සන්න වෙනවා. සාමාන්‍ය ජිවිතයේ නම් මේකට හැමෝටම වගේ ඕන තරම් අත්දැකීම් ඇති.

ඇත්තෙන්ම පරිගණක ක්ෂේත්‍රයේ මේ Sorting කියන concept එක ගොඩාක් ලොකුවට භාවිතා වෙනවා. පොඩි උදාහරණයක් කියන්නම්. හැමෝම වගේ use කරලා ඇති නේද Ebay. ඉතින් මේ Ebay වල මොකක් හරි දෙයක් Search කරහම අපිට පුළුවන් නේද අපිට කැමති විදිහට Search Results Sort කරගන්න. කැමති නම් Price එක වැඩි වෙන පිළිවෙලට , එහෙම නැත්නම් Ratings වැඩි වෙන පිළිවෙලට. ඉතින් මේ විදිහට ගොඩක් තැන් වල Sorting කියන දේ දකින්න ලැබෙනවා. මන් ඒක කිව්වේ මේකේ තියන වැදගත්කම ගැන පොඩි අදහසක් ගන්නයි.
හරි එහෙම නම් බලමු කොහොමද Sorting කරන්න පුළුවන් කියන එක ගැන.
බොහෝ දුරට අපි sort කරන්නේ දත්ත පෙළක් (data list එකක්). අපි sort කරද්දී එම දත්ත පෙළ සතුවෙලා තියන යම්කිසි ලක්‍ෂණයක වැඩි වීම එහෙම නැත්නම් අඩු වීම කියන දේ ප්‍රධාන වශයෙන්ම සැලකිල්ලට ගන්නවා. ඉතින් අපිට පුළුවන් එම ලක්‍ෂණය වැඩිවෙන පිළිවෙලට හරි එහෙම නැත්නම් අඩුවෙන පිළිවෙලට හරි අපේ දත්ත පෙළ පෙළගස්වන්න. සරලවම කිව්වොතින් Sorting කරනවා කියල කරන්නේ ඔන්න ඔය දේ තමයි.
උදාහරණයක් විදිහට සංඛ්‍යා පෙළක් අගය වැඩි වෙන පිළිවෙලට පෙළගස්වන්න අපිට පුළුවන්.

Sort කරන්න කලින්      9 , 10 , 4 , 2 , 1 , 15 , 6
sort කරාට පස්සේ        1 , 2 , 4 , 6 , 9 , 10 , 15

මන් මෙතැනදී ලක්ෂණය විදිහට අරගෙන තියෙන්නේ සංඛ්‍යාවේ අගයයි. (වටිනාකම)

තව ටිකක් පැහැදිලි වෙන්න මෙන්න මේ උදාහරණයත් බලන්න.

Sort කරන්න කලින්        6 , 4 , 2 , 3 , 9
sort කරාට පස්සේ          2 , 3 , 9 , 4 , 6

මොකද්ද මෙතැනදී සැලකිල්ලට අරගෙන තියන ලක්ෂණය. හිතන්න ටිකක් … … …

මන් මෙතැනදී සැලකිල්ලට අරගෙන තියෙන්නේ පවතින සාධක ගණන වැඩි වෙන අනුපිළිවෙල කියන දේ.

2 ට සාධක 2 යි (1 සහ 2)
3 ට සාධක 2 යි (1 සහ 3)
9 ට සාධක 3 යි (1 , 3 සහ 9)
4 ට සාධක 3 යි (1 , 2 සහ 4)
6 ට සාධක 4 යි (1 , 2 , 3 සහ 6)

ඉතින් දැන් පැහැදිලි ඇති කියල හිතනවා මේ Sort කරද්දී අපි සැලකිල්ලට ගන්න ලක්ෂණය කොච්චර වැදගත් වෙනවද කියන එක.

සංඛ්‍යා පමණක් නෙවෙයි අපිට මේ විදිහට වචන පවා sort කර ගන්න පුළුවන්.

හොඳයි හිතන්න ටිකක් මේ විදිහට … අපි විශාල data list එකක් sort නොකර තිබ්බොතින් අපිට මේකේ මොකක් හරි element එකක් හොයද්දි අනිවාර්යෙන් Linear Search එකකට යන්න වෙනවා නේද? ඒ කියන්නේ අපිට ඒ data list එකේ මුල ඉඳල ඉවර වෙනකන්ම අපිට අවශ්‍ය data එක හම්බෙනකන් search කරන්න වෙනවා නේද ? ඉතින් අපි data list එකේ අඩංගු element ගණන n නම් worst case එකේදී (ඒ කියන්නේ යන්න පුළුවන් උපරිම කාලය ගතවුනොත් – මෙහෙම වෙන්නේ අපි හොයන element එක අවසානයට තිබ්බොතින් තමයි) අපිට n ට සමානුපාතික කාලයක් යනවා නේද හොයා ගන්න. n ඉතා විශාල නම් ගත වෙන කාලයත් ඒත් එක්ක ගොඩාක් වැඩි වෙනවා. නමුත් මේ data list එක sort කරලා තිබ්බොතින් අපිට ලැබෙන වාසිය තමයි Binary Search මගින් කලින්ට වඩා සැලකිය යුතු මට්ටමකින් අඩු කාලයකදී අපට අවශ්‍ය සංඛ්‍යාව හොයා ගන්න පුළුවන් වීම. ඇත්තෙන්ම කියනවා නම් මෙතැනදී සමානුපාතික වෙන්නේ log 2n වලට. ඉදිරියේදී කතා කරනවා මේ සියල්ක්ලක්ම පිළිබඳව. දැනට දල අදහසක් ගන්න තමයි මේ විදිහට පෙන්නුම් කරේ.

ඉතින් මෙතරම් වැදගත් වෙන Sort කියන දේ කරන්න අපි algorithms භාවිතා කරනවා. ඉදිරියේදී මේවගෙන් බොහොමයක් algorithms ගැන සවිස්තරාත්මකව කතා කරන්න බලාපොරොත්තු වෙනවා .

Some Sorting Algorithms

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Merge Sort
  • Quick Sort
  • Heap Sort
  • Counting Sort
  • Radix Sort

 

Advertisements