Monday, June 20, 2011

බුබුලු සැකසුම (Bubble Sort)

සංඛ්‍යාවන් පිලිවලට පෙලගස්වා ගැනීමේ සරළ ඇල්ගොරිතමයක් ලෙස බුබුලු සැකසුම (Bubble Sort) ඇල්ගොරිතමය හඳුන්වා දිය හැක. මෙහිදී සිදුවන්නේ කිසියම් සංඛ්‍යා පෙලගැස්මක, පිලිවෙලින් වරකට අනුයාත සංඛ්‍යා දෙක බැගින් ගෙන ඉන් වඩා කුඩා (හෝ විශාල) එක තෝරා ගැනීමයි. මෙසේ පියවර nxn (n යනු ලබාදී ඇති සංඛ්‍යා ගනනයි) වාරයක් සිදුකල විට සංඛ්‍යා පෙලගැස්ම ආරෝහණ (හෝ අවරෝහණ ) ආකාරයට පෙලගස්වාගත හැක. 
පරිගණක ක්‍රමලේඛ (Computer Programming) වලදී කිසියම් දී ඇති සංඛ්‍යා පෙලගැස්මක් (Number Array) ආරෝහණ හෝ අවරෝහණ අයුරින් පිලියෙල කරගැනීමට මෙම බුබුලු සැකසුම් ඇල්ගොරිතමය (Bubble Sort Algorithm) භාවිතා කරයි. මෙමෙ ඇල්ගොරිතමය පරිගණක භාෂාවක් (Programming Language) මඟින් ගොඩනැංවීමට ඉතා පහසු බැවින් මෙම ඇල්ගොරිතමය ඉතා ප්‍රචලිතය. නමුත් මෙහි ඇති සරල බව නිසාම මෙම ඇල්ගොරිතමය ක්‍රියාත්මක වී ප්‍රථිඵලය ලබාදීමට යන කාලය සාපේක්ෂව වැඩිය. එබැවින් මෙම ඇල්ගොරිතමය සුදුසු වන්නේ සංඛ්‍යා අඩු ගනනක් පිලියල කරගැනීමට ය. පිලියල කිරීමට ඇති සංඛ්‍යා ගනන වැඩිවත් ම, ගතවන කාලයද වැඩිවේ.

ඇල්ගොරිතම්යක කාර්යක්ෂමතාව මැනීමට O අංකනය (Big O Notation) භාවිතා කරයි. එයින් කියවෙන්නේ ඇල්ගොරිතමයක ආදානයන්ට (Inputs) වලට සාපේක්ෂව සැකසුමට (Process) ගතවන කාලයයි. ඒ අනුව බුබුලු සකසන ඇල්ගොරිතමයේ (Bubble Sort Algorithm) සාමාන්‍ය කාර්යක්ෂමතාව (Average Performance) O(n2 ) වේ. එනම් උදාහරණයක් ලෙස,
මෙම ඇල්ගොරිතමයෙන් සංඛ්‍යා 10 ක් පිලියෙල කරගැනීමට ඇත්නම් (එනම් ආදාන(Inputs) 10ක් එවිට n=10) හා එක ආදානයක් සකස් කිරීමට ගතවන කාලය මිලි තත්පර 2ක් නම්, සම්පූර්ණ සංඛ්‍යා 10 ම සැකසීමට ගතවන කාලය (2xn2 එනම් 2x102) මිලිතත්පර 200කි.

මෙම ඇල්ගොරිතමය C# පරිගණක භාෂාවෙන් ගොඩනඟා ඇති ආකාරය පහත දැක්වේ.


 1. for (int t = 0; t < 10; t++)
 2.             {
 3.                 for (int i = 0; i < 9; i++)
 4.                 {
 5.                     if (numbers[i] > numbers[i + 1])
 6.                     {
 7.                         temp = numbers[i];
 8.                         numbers[i] = numbers[i + 1];
 9.                         numbers[i + 1] = temp;
10.                     }
11.                 }
12.             }


පස්වන පේලියේ දී සිදුකර ඇතේ දී ඇති සඛ්‍යා පෙලගැස්මේ (Integer Array) අනුයාත සංඛ්‍යා දෙකෙන් වඩා කුඩා එක තෝරා ගැනීමයි. එහිදී අනුයාත සංඛ්‍යා දෙකෙන් මුල් එක අනෙකට වඩා විශාල නම්, 7-9  පේලි වලදී ඒ සංඛ්‍යා දෙකේ පිහිටීම හුවමාරු කර ඇත. මෙසේ දී ඇති සඛ්‍යා පෙලගැස්මේ (Integer Array) සෑම අනුයාත සංඛ්‍යා දෙකකටම වාර දහයක් සිදුකල විට දී ඇති සංඛ්‍යාවන් ආරෝහණ අයුරින් පෙල ගැසේ.   


සංඛ්‍යා 10ක් ලබාගෙන ඒවා බුබුලු සකසන ඇල්ගොරිතමයෙන් (Bubble Sort Algorithm) ආරෝහන පිලිවෙලට සකස් කරන සරල C# Console Program එකක කේත මෙසේය. රතුපාටි දක්වා ඇත්තේ බුබුලු සකසන ඇල්ගොරිතමය (Bubble Sort Algorithm) ගොඩනංවා ඇති කේත කොටසයි.


static void Main(string[] args)
        {
            int[] numbers = new int[10];
            int temp;


            for (int i = 0; i < 10; i++)
            {
                Console.Write("Enter a number: ");
                numbers[i] = Convert.ToInt16( Console.ReadLine());
            }




            Console.WriteLine();
            Console.WriteLine("Your Order");




            for (int i=0;i<10;i++)
            {
                Console.Write("{0}, ",Convert.ToString(numbers[i]));
            }




            Console.WriteLine();
            Console.WriteLine();
            Console.WriteLine("Ascending Order");




            for (int t = 0; t < 10; t++)
            {
                for (int i = 0; i < 9; i++)
                {
                    if (numbers[i] > numbers[i + 1])
                    {
                        temp = numbers[i];
                        numbers[i] = numbers[i + 1];
                        numbers[i + 1] = temp;
                    }
                }
            }




            for (int i = 0; i < 10; i++)
            {
                Console.Write("{0}, ", Convert.ToString(numbers[i]));
            }


            Console.ReadLine();
            
        }

16 comments:

  1. ohoma baa comment daala udin copyright statements daala piliwelata karanna ona :)

    ReplyDelete
  2. Algorithm කියන්නෙ මොකද්ද අය්යා?එතකොට මම් අහල තියනව Genetic Algorithm කියලා එකකුත්.පුලුවන් නම් පැහැදිලි කරල දෙනවද?

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. අපෝ මට නම් ඔය බුබුලු සෝට් එකයි, සිලෙක්ශන් සෝර්ට් එකයි තව සෝර්ට් එකකුයි එපාම වෙලා තිබ්බේ ඒ දවස්වල. කොටින්ම කෝඩ් එක කටපාඩම් කරන්න මාරම අමාරුයි නේ.

    @නදී :
    නංගි Algorithm කියලා කියන්නේ A step by step process that solving a specific problem කියන එකනේ.

    ඒ කියන්නේ ප්‍රශ්නයක් විසදීම සදහා භාවිතා කරන පියවරෙන් පියවර කලයුතු ක්‍රියා මාර්ගයට. මෘදුකාංග වලදි කෝඩ් එකක් ලියන්න කලින් ඇල්ගෝ එකක් ලියන එක හොදයි. එතකොට ප්‍රශ්නේ අනලයිස් කරගන්න පුලුවන් නේ.

    ඇල්ගෝ එකක් කියලා කියන්නේ කෝඩ් එකකට කලින් වෙන්න ඕන දේ කියලා ලියන සටහනකට. කෝග් එකකට ගොඩක්ම කිට්ටු උනාට මේක කෝඩ් එකක්ම නෙමෙයි.

    ReplyDelete
  5. @මධුරංග- "කෝඩ් එක කටපාඩම් කරන්න මාරම අමාරුයි"

    ආ එතකොට ඔය කොම්පියුටර් ගහන ඇත්තො ඔක්කොම ලියන එව්වා කට පාඩම් කරනවද?අපෝ එපා වෙනව ඇතිනේද?ඔයාල ඔහොමවත් ඉතුරු වෙලා ඉන්නව ඇති..

    "ප්‍රශ්නයක් විසදීම සදහා භාවිතා කරන පියවරෙන් පියවර කලයුතු ක්‍රියා මාර්ගයට."

    එතකොට "සූඩො කෝඩ්" කියන්නෙ මොක?මම් හරියටම දන්නෙ නැති නිසා මේ අහන්නෙ.සමාවෙන්න!

    ReplyDelete
  6. අද මාතෘකාව සම්පූර්ණයෙන්ම වෙනස් වෙලා ..නේද.
    මට නම් මෙලෝ දෙයක් තේරුනේ නෑ..ටී.බී.

    ඒත්..මේ ෆීල්ඩ් එකේ ඉන්න අයට නම්...මේ පෝස්ට් එක සැහෙන්න වැදගත් වේවි...නේද.

    ReplyDelete
  7. @ banda,
    අපේ ඔය ගුරු මුෂ්ටි නෑ නෙ, දන්න දෙයක් ඒ විදියටම ඕනෙ කෙනෙක්ට කියල දෙනව. මගේ බ්ලොග් එකේ නමට යටින් තියන ටික බලපන් කො... ;)

    ReplyDelete
  8. @ නදී,
    මධුරංග අයිය පැහැදිලි කරල තියනවනෙ ඇල්ගොරිතමයක් කියන්නෙ මොකක්ද කියල, ඒකට කිසියම් ඌණ පූර්ණයක් සපයනවනම්, ඇල්ගොරිතමයක් යනු,
    "කිසියම් ගණිතමය ගැටළුවක් විසඳීමේ සාධාරණ අනුපිළිවෙලක් සහිත පරිමේය පියවරයන් සංඛ්‍යාවක් ඇති ක්‍රියා පටිපාටියක්"
    ලෙස හැඳින්විය හැකී.

    ඒ කියන්නෙ ඔය දෙන්න දෙමහල්ලො අතර තියන ප්‍රශ්ණයක් විසඳන ක්‍රියා පටිපාටියක් වගේ එකක් ඇල්ගොරිතමයක් වෙන්නෙ නෑ, ඇල්ගොරිතමයක් කිසියම් ගණිතමය ගැටළුවකටයි සම්භන්ධ වෙන්නෙ. ඒ වගේම ඇල්ගොරිතමයේ ක්‍රියාකාරීත්වය භාවිතාකරන පුද්ගලයා මත වෙනස් වෙන්නෙත් නෑ, ඒක සාධාරණ ප්‍රකාශනයක් නිසා. ඒ වගේම ඇල්ගොරිතමයක ඇති පියවර ගණන අනන්තයක්,ඍණ ගණනක් වගේ අතාත්වික වෙන්නෙත් නෑ සහ ඒ පියවරයන් අනුගමනය කල යුතු නිශ්චිත පිළිවෙලකුත් තියනව.

    Genetic Algorithm (ගෙනෝම ඇල්ගොරිතම) සහ Neural Networks (ස්නායුක ජාලක) පිළිබඳව වෙනමම ලිපියක් ලඟදිම පළ කරන්නම් කො. එතකං පොඩ්ඩක් ඉවසල ඉන්න... :)

    ReplyDelete
  9. @ නදී,
    කෝඩ් කටපාඩම් කරනව කියනව වෙනුවට, කෝඩ් හුරු වෙනව කීවොත් නිවැරදී. ඒ කියන්නෙ නිතර භාවිතා කරන කෝඩින්ග්ස් හුරුයි ඒ වගේම නිතර භාවිතා නොවෙන කෝඩින්ග්ස් උවමනා උනහම අන්තර්ජාලයෙන් බලනව, නැත්නම් අදාල පොතකින් බලනව. හැබැයි ඉතින් ඒ ඒ දේවල් කොතැනින් බැලිය යුතුයි ද කියල මතක තියාගන්න එක නම් වටිනව. අර කතාවක් තියෙන්නෙ දැනුමත් වැදගත් දැනුම පිළිබඳ දැනුමත් වැදගත් කියල. ඊට අමතරව සමහර කෝඩින්ග්ස් නම් අපට හිතලම කරන්න වෙනව. එහෙම නැතුව කෙනෙක්ට හැම කෝඩ් එකක් ම කටපාඩම් කරල වැඩ කරන්න බෑ, ඒක ප්‍රායෝගිකත් නෑ.
    මධුරංග අයිය මොකද කියන්නෙ?

    සූඩො කෝඩ්ස් (Pseudo Codes) කියන්නෙ කිසියම් ඇල්ගොරිතමයක්, කිසිම පරිගණක භාෂාවකට අයත් නොවන අන්තර්ජාතිකව පිලිගත් සාධාරණ සලකුණු වලින් ලියා දැක්වීමයි. මෙසේ ලියා දක්වන්නේ පරිගණක වල භාවිතයට නොව මිනිසාගේ භාවිතයටයි. මෙවැනි සූඩො කෝඩ් එකක් බලා මිනිසුන් ට එය ඕනෑම පරිගණක භාෂාවකින් ගොඩනැගිය හැකී.

    උදාහරණයක් ලෙස a කියන විචල්‍යට (variable) 5 ආදේශ කරන්න කියන එක සූඩො කෝඩ්ස් වලින් ලියන්නෙ මෙහෙමයි,
    a<-5

    එතකොට ඒක දිහා බලාගෙන C# පරිගණක භාශාව දන්න කෙනෙකුට ඒක C# වලින් මෙහෙම ලියන්න පුලුවන්,
    int a;
    a=5;

    ඒ වගේම Visual Basic පරිගණක භාශාව දන්න දන්න කෙනෙකුට මෙහෙම ලියන්න පුලුවන්,
    a=5

    ...

    ඔය වගේ සූඩො කෝඩ්ස් වලින් වෙන්නෙ, කරන්න තියන දේ කියන එක, ඒක දිහා බලල ඒ ඒ පරිගණක භාශාවෙන් ඒ කරන්න කියල තියන දේ ගොඩනගන්න පුලුවන්.

    ReplyDelete
  10. @ - නිල් අහස -,
    විව්ධත්වයක් තියෙන්න ඕනෙ නිසා අද මාතෘකාව ටිකක් වෙනස් කලා. ඔන්න ඉතින් මෙලෝ දෙයක් තේරුනේ නෑ කියපු එක නම් බොරුවක්!
    මේ ක්ෂේත්‍රයේ ඉන්න අය නම් මේව භාවිතා කරනව...

    ReplyDelete
  11. @ මධුරංග,
    බොහොම ස්තූතියි මේ පැත්තෙ ආවටත්, ටීකාවන් ඉදිරිපත් කලාටත්. ආයෙත් එන්න කියල ආරාධනා කරනව...

    ReplyDelete
  12. @නදී :
    නෑ නංගි. මම් කෝඩ් එක කටපාඩම් කලේ විභාගේ ගොඩ දාගන්න විතරයි. නැත්නම් කෝඩ් එක පාඩම් කරගන්න ඕනේ නෑ. වෙන්න ඕන දේ හිතලා ලියන්න පුලුවන් නම් එච්චරයි.

    මම විභාගෙට ගියාම හිතන ප්‍රශ්න වලට වඩා ආස පාඩම් කරලා ලියන ප්‍රශ්න වලට. ගෙඩි පිටින්ම අලවලා ආව හැකි නේ.

    සූඩෝ කියන එකේ තේරුම නීට් නස් (neatness) කියන එක. ඒක ගොඩක්ම කිට්ටු ඇල්ගෝ එකට. කෝඩ් එකට නම් ගොඩක්ම ඈතයි.

    ටීබී දිලා තියෙනේ නිර්වචණේ.

    දිගටම එන්නම්.

    ReplyDelete
  13. අලුතින් මොකක් හරි සංකල්පයකට කෝඩ් එකක් කොටන්න යද්දී අමාරුම වැඩේ වෙන්නේ ඇල්ගොරිදම් එක හදාගන්න එක.ඇල්ගොරිදම් එක හදාගත්තට පස්සේ සුදුසු පරිගණක භාෂාවකින් වැඩේ ගොඩදාන එක පහසුයි.සංකීර්ණ ඇල්ගොරිදම් එකක් හදාගන්න යද්දී ගණිතය සෑහෙන්න ඕන වෙනවා.A/L බයෝ කරපු මම නම් Data Structures & Algorithms ඉගන ගද්දි යම්පමණකට මාඥ්ඥමික උනා. ටී.බී නං අමාරුවක් නැතිව ගොඩදාන්න ඇති.මොකද මට මතකයි ඉස්සර physics පීරියඩ් එකේ සර් එන්න කලින් අපි ලයිබ්‍රියට මාරුවෙද්දී ටී.බී පොත අරන් ලෑස්තිවෙන හැටි :D. අනික් අතට අපි ජීවිතේ ඕනම දෙයක් කරද්දි ඇල්ගොරිදම් එකක් ඉස්සරල හදාගන තමයි වඩේ කරන්නේ.නැද්ද මං අහන්නේ...

    ReplyDelete
  14. @ තීර්ථ යාත්‍රිකයා,
    උඹල මාරු උනේ ලයිබ්‍රරියට කීවට ලයිබ්‍රරියටම නෙමේ නේද... ;)

    ReplyDelete
  15. මං නං මාරුවුනේ ලයිබ්‍රියට තමයි මචෝ.ඒ කලෙ තමයි වැඩිහරියක්ම පරිවර්තන පොත් කියෙව්වේ... :D

    ReplyDelete
  16. @ තීර්ථ යාත්‍රිකයා,
    ඇත්තටම මචන් ඉස්කෝලෙ A/L පංති වල ඉද්දි කරපු දේවල් නම් හුඟක් ම සුන්දරයි තමයි, උඹ කීව වගේ ඒයිනුත් physics පීරියඩ් එකට නම් ගොඩක් කැමතියි තමා. ඒ වගේම physics practicals වලටත් ගොඩක්ම කැමැත්තක් තිබුන නිසා එකම එක ප්‍රැක්ටිකල් එකක් විතරයි අතපසු උනෙ. අපේ physics සර් ගෙ රුව, හඬ මැවිල වගේ පේනව, ඇහෙනව. ස්තූතියි ඒ මතකය අලුත් කරාට... :)

    ReplyDelete

ඔබේ ටීකාව පහතින් සටහන් කරන්න