මිට කලින් කොටසින් අපි කතා කරා Sorting Algorithm කියන්නේ මොනවද සහ එහි තියන වැදගත්කම ගැන. අද අපි කතා කරන්නේ මේ Selection Sort කියන Sorting Algorithm එක ගැනයි. ඉතින් එහෙනම් බලමු කොහොමද Selection Sort Algorithm එක තේරුම් ගන්නේ කියන එක.

ඇත්තෙන්ම Selection Sort Algorithm එකේ සරලම අදහස මෙන්න මෙහෙම දෙයක්. ඔන්න මගේ වම් අතේ තියනවා ඉලක්කම් ලියපු card කිහිපයක්. ඉතින් මන් කරන්නේ මගේ වම් අතේ තියන card වලින් මුලින්ම අඩුම අගය තියන card එක හොයල ඒක දකුණු අතෙන් තියා ගන්නවා. ඊට පස්සේ වම් අතේ ඉතුරු card ටිකෙන් අඩුම අගය තියන card එක හොයල දකුණු අතේ කලින් card එකට යටින් තියා ගන්නවා. ඉතින් මේ විදිහට වම් අතේ card ඔක්කොම ඉවර වෙනකන්ම අඩුම අගය තියන card එක හොයාගෙන දකුණු අතේ එකතු වෙන card ගොඩේ යටින්ම තියනවා.ඉතින් මේ විදිහට දිගටම කරගෙන ගියහම (වම් අතේ card ඉවර වෙනකන්ම) දකුණු අතේ හැදෙන card වල අගයන් ගැන මොකද කියන්න තියෙන්නේ. අගය අඩු card එකේ ඉඳන් අගය වැඩි card එක දක්වා පිළිවෙලට card ටික පෙළ ගැහිල තියනවා නේද ? ඉතින් අපි Selection Sort Algorithm එකෙන් කරන්නේ මේ සිද්ධාන්තය පාවිච්චි කරලා Array එකක තියන element sort කර ගන්න එකයි.
දැන් බලමු ඒක කරන්නේ කොහොමද කියල …

ඔන්න මං ගාව Integer Array එකක් තියනවා A කියල මෙන්න මේ විදිහට.

array-a

ඉතින් මන් තවත් Array එකක් හදාගන්නවා (හරියටම A Array එකට සමාන elements ගාණක් දාන්න පුළුවන් Empty Array එකක්). ඒ Array එක B කියල හඳුන්වන්නම්.

array-b

ඉතින් කලින් පැහැදිලි කරපු විදිහට මන් A වල තියන elements එකින් එක අඩුම එකේ ඉඳන් පිළිවෙලට තෝරාගෙන B වලට දානවා

එහෙනම් A වල තියන අගය අඩුම Integer එක 1 මන් දානවා B වල 0 index එකේ element එක විදිහට. මෙන්න මේ විදිහට …

array-a-and-b

දැන් පොඩි ප්‍රශ්නයක් මතු වෙනව නේද ? දෙවෙනි වතාවට A Array එකේ අඩුම අගය හොයාගෙන යනකොට කලින් වතාවේ B ට දාපු අගය සහිත index එක පරික්ෂා නොකර ඉන්නේ කොහොමද කියන එක තමයි ප්‍රශ්නේ. මේ උදාහරණයේ හැටියට නම් පරික්ෂා කරන හැම අවස්ථාවකම අඩුම අගය වෙන්නේ 1. මේ ප්‍රශ්නෙන් මිදෙන්නට නම් A වල පරික්ෂා කරන ලද index එකක අගය තිබිය හැකි උපරිම අගයකින් replace කරමින් යනවා වගේ දෙයක් අපිට පහසුවෙන්ම කරගන්න පුළුවන්. Integer වල නම් (32 bit ) 231 -1 කියන අගය තමා උපරිම අගය වෙන්නේ. ඉතින් අනිත් ස්ථාන වල අගය මේ අගයට වඩා අනිවාර්යෙන්ම අඩු බව දන්නා නිසා මේ ක්‍රමය සාර්ථකයි.

එතකොට මෙන්න මේ විදිහට තමා වැඩේ වෙන්නේ …

array-a-and-b-final

හොඳයි මෙතෙක් කරපු දේ තේරෙන්න ඇති කියල විශ්වාස කරනවා.
නමුත් මේකේ පොඩි අවුලක් තියනවා නේද ?

දැන් හිතන්න අපිට element ගාන ගොඩාක් වැඩි Array එකක් හම්බුනොත්, මේ විදිහට Sort කරන්න ගියහම Memory Space වැය වෙන එක ගැන මොකද හිතෙන්නේ (අපි මේකට කියනවා Space Complexity කියල). අපරාදේ නිකන්ම Memory නාස්ති වීමක් සිද්ද වෙනවා නේද ? මොකද B කියල අපි හදා ගන්න Array එක නිසා.
හරියටම කියනවා නම් මෙතැනදී Space Complexity එක elements ගානට සමානුපාතික වෙනවා. ඒක නිසා මේක හරියන වැඩක් නෙවෙයි.

අපි පුළුවන් තරම් බලන්න ඕනේ element ගණන කීයක් උනත්, පාවිච්චි කරන Memory Space ප්‍රමාණය නියත වෙන විදිහට අපේ Algorithm එක develop කරන්නයි.
ඉතින් කලින් වතාවේ වගේම අපි A කියන Array එකේ අඩුම අගය හොයා ගමු. කලින් වතාවේ වගේ වෙනම Array එකකට මේ අගය දානවා වෙනුවට A Array එකේම 0 index එකේ තියන element එකත් එක්ක මේක හුවමාරු (swap) කර ගමු.
මෙන්න මේ විදිහට …

aaaaa

කොළ පාටින් පෙන්නලා තියෙන්නේ අඩුම අගයට මුල index එකට එන්න ඕන නිසා swap වෙච්ච කලින් මුල හරියේ තිබ්බ element එක.

දැන් අපිට ලැබෙන අනිත් වාසිය තමයි Array එකේ පරික්ෂා කරන්න වෙන පරාසය ටිකෙන් ටික අඩු වේගන යන එක (දෙවෙනි වතාවේ අඩුම අගය තියන element එක හොයද්දි මුල ඉඳලම බලන්න ඕනේ නෑ , 1 index එකේ ඉඳන් පරික්ෂා කරගෙන ගියහම ඇති). ඉතින් මේ නිසාම කලින් වගේ නැවත පරික්ෂා කරන එක වලක්වන්න විශේෂ උපක්‍රමයක් යොදාගන්න අවශ්‍යතාවයක් වෙන්නේ නෑ.

ඉතින් මේ විදිහට දිගටම කරගෙන යද්දී මෙන්න මෙහෙම තමයි වැඩේ වෙන්නේ ….

bbbbb

හොඳයි එහෙනම් දැන් අපි බලමු මේ algorithm එකට අදාලව Pseudo-code එකක් හදා ගන්නේ කොහොමද කියල. ඇත්තටම concept එක හරියටම තේරුනා නම් මේක හදා ගන්න එක හරිම ලේසියි.

මම මෙතැනදී තේරුම් ගන්න පහසු වෙන්න මේ කාර්යය ට function එකක් පාවිච්චි කරනවා. function එක කාර්යය තමා තමන්ට හම්බවෙන Array එක Sort කරල දෙන එක.

ඉතින් මම මේ හදා ගන්න function එක නම් කරන්නම් SelectionSort කියල. ඒ වගේම මේ function එකට Arguments විදිහට Array එක සහ ඒ Array එකේ elements ගණන(Array එකේ length එක) ගන්නම්.
හොඳයි මම මෙතනදී කරන්නේ මෙහෙම දෙයක් for loop එකක් use කරලා i = 0 ඉඳන් n -1 වෙනකන් තියන elements පරික්ෂා කරමින් යනවා. මෙහෙම යන එකේ අරමුණ තමයි යම් අවස්ථාවක i වෙනි index එකට අදාලව i වෙනියට විශාල අගය සහිත element එක තොර ගන්න එක. ඉතින් මේක කරන්න නම් මට තනි for loop එකකින් නම් බෑ. මම මේ හදා ගත්ත for loop එක athule තවත් for loop එකක් හදා ගන්නවා. මේකේ අරමුණ නම් i ට අදාළ යම් අගයකදී එතනින් ඉස්සරහ පවතින elements වලින් කුඩාම අගය සහිත element එක හොයා ගන්න එක.

මෙන්න මේ විදිහට …

SelectionSort(A,n){
    for i = 0 to n-2 
         min = i 
         for j = i+1 to n - 1
              if (A[j] < A[min]){
                    min = j
               }
               temp = A[i]
               A[i] = A[min]
               A[min] = temp
}

මේ දක්වල තියන දේ පැහැදිලි ඇති කියල හිතනවා. මෙතන min කියල variable එකක් පාවිච්චි කරලා තියන්නේ ඇයි කියල කියන්නම් … එකෙන් කරන්නේ පලවෙනි for loop එකේදී i index එක හැම වෙලේම මේ min කියන variable එකට සමාන කරනවා. inner for loop එකේදී i වලින් ඉදිරියට පවතින අගයන්ගෙන් කුඩාම අගයේ index මේ min ට සමාන කර ගන්නවා. ඉතින් දැන් හරිම පහසුවෙන් i වලින් ඉදිරියේ තියන අගයන්ගෙන් කුඩාම අගය සමග i වල අගය හුවමාරු කරගන්න පුළුවන්.

මේ විදිහට හදා ගත්තු C++ code එක මෙන්න …

void SelectionSort(int A[],int n){
	for(i=0;i<n-1;i++){
		int min = i;
		for(j=i+1;j<n;j++){
			if(A[j] < A[min]){
				min = j;
			}
		}
		int temp = A[i];
		A[i] = A[min];
		A[min] = temp;
	}
}
Advertisements