Sorting Algorithms හඳුන්වාදීමේ ( පළමු කොටස ) බැලුවේ නැත්නම් මෙතනින් ගිහින් ඒක බලන්න.

අද අපි කතා කරන්න යන්නේ Sorting Algorithms වල මීළඟ Algorithm එක, Bubble Sort Algorithm එක ගැනයි.

ඉතින් මම Sort කරන්න තියන Array එක මෙන්න මේ විදිහට ගන්නම් …

array-a

ඉතින් මම මෙතනදි කරන්නේ මේ array එකේ මුල ඉඳන් අන්තිම element එක වෙනකන් බලාගෙන යනවා. මේ විදිහට නිකන්ම බලාගෙන යනවා නෙවෙයි. හැම අවස්ථාවකදීම මම බලන තැන තියන Value එකට වඩා මට 1 index එකක් ඉස්සරහින් තියන index එකේ value එක අඩු  නම්, ඒ වැඩි අගය සහ මම ඉන්න තැන අගය හුවමාරු කර ගන්නවා. ඊට පස්සේ තව 1 index එකක් ඉස්සරහට යනවා. ඉතින් මේ විදිහට දිගටම Array එක ඉවර වෙනකන්ම පරික්ෂා කරනවා (කලින් සඳහන් කරපු විදිහට අවශ්‍ය නම් හුවමාරු කිරීම් සිදු කරනවා).
ඉතින් මේ විදිහට Array එක දිගේ එක වටයක් ගියහම අපේ වැඩේ ඉවරයක් වෙයිද ?
නෑ …
ඉතින් මේකට Array එක පුරා කීප වතාවක් මේ විදිහට ගමන් කරන්න වෙනවා.
ඒකට හේතුව මේකයි …
අපි Array එකේ අගයන් 2 ක් හුවමාරු කරා කියල හිතන්නකෝ . ඉතින් අපි Array එකේ දිගින් දිගටම ඉදිරියට යද්දී අර හුවමාරු කරලා තමන් ඉන්න තැනට දා ගත්තු අගයක් ඊටත් කලින් තියන අගයකටත් වඩා කුඩාද කියල පරික්ෂා කිරීමක් සිද්ද වෙන්නේ නෑ නේද ?
මොහොතකට හිතන්න Array එකේ කුඩාම අගය අන්තිමට තිබ්බ කියල. එතකොට එක වටයක් යද්දී වෙන්නේ අන්තිමට තිබ්බ අගය ඊට කලින් ස්ථානයට එන එක විතරයි.
හොඳයි ඒ දේ පැහැදිලි වෙන්න ඇති කියල මම හිතනවා. ඉතින් අපි ඒකට මොකද කරන්නේ. එක වතාවකදී එකක් පස්සට අවනම් මුලටම ගන්න නම් Array එකේ length එකට සමාන වතාවක් (වට ගණනක්) මේ දේ කරන්න ඕනේ නේද ?
ඔව් ..  ඒ විදිහට කරොත් අපිට පුළුවන් සම්පුර්ණ Array එකම අපිට අවශ්‍ය විදිහට Sort කර ගන්න.

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

මෙන්න තියනව Array එක …

bbs

ඔන්න මන් දැන් ඉන්නේ index 0 වල. 0 වල තියන 2 ට වඩා 1 තියන 7 අගයෙන් වැඩියි. ඒක නිසා හුවමාරු කිරීමේ අවශ්‍යතාවයක් නෑ .
දැන් මම යනවා index 1 ට. 1 වල තියන 7ට වඩා 2 තියන 4 අගයෙන් අඩුයි. ඉතින් මට සිද්ද වෙනවා 1 තියන 7 සමග 2 තියන 4 හුවමාරු කර ගන්න. එතකොට මේ Array එක මෙන්න මේ විදිහට වෙනස් වෙනවා …

bs10

දැන් මම යනවා index 2 ට. 2 වල තියන 7ට වඩා 3 තියන 1 අගයෙන් අඩුයි. ඉතින් මට සිද්ද වෙනවා 2 තියන 7 සමග 3 තියන 1 හුවමාරු කර ගන්න. එතකොට මේ Array එක මෙන්න මේ විදිහට වෙනස් වෙනවා …

bs11

දැන් මම යනවා index 3 ට. 3 වල තියන 7ට වඩා 4 තියන 5 අගයෙන් අඩුයි. ඉතින් මට සිද්ද වෙනවා 3 තියන 7 සමග 4 තියන 5 හුවමාරු කර ගන්න. එතකොට මේ Array එක මෙන්න මේ විදිහට වෙනස් වෙනවා …

bs12

දැන් මම යනවා index 4 ට. 4 වල තියන 7ට වඩා 5 තියන 3 අගයෙන් අඩුයි. ඉතින් මට සිද්ද වෙනවා 4 තියන 7 සමග 5 තියන 3 හුවමාරු කර ගන්න. එතකොට මේ Array එක මෙන්න මේ විදිහට වෙනස් වෙනවා …

bs13

ඉතින් දැන් පැහැදිලි නේද වැඩේ වෙන්නේ කොහොමද කියන එක. Array එකේ තිබුණ අගයෙන් වැඩිම අගය (7) , Array එකේ අවසාන ස්ථානයට ගියා. ඒ කියන්නේ Array එකේ අවසාන index එක sort උනා. ඉතින් මේ විදිහට තවත් වතාවක් කරොත් අපිට පුළුවන් වෙනවා මීළඟට විශාලතම අගය වන 5 Array එකේ 4 වන index එකට දාගන්න.
දැන් පැහැදිලි ඇති කියල හිතනවා සිද්ධාන්තයක් විදිහට Bubble sort වෙන්නේ කොහොමද කියන එක.

දැන් අපි බලමු implementation කර ගන්නේ කොහොමද කියන එක. මම මුලින්ම Array එක පුරා එක වතාවක් ගිහින් විශාලම අගය අන්තිම index එකට ගන්න උත්සහ කරන්නම්. පස්සේ අනිත් කොටස් ගැන හිතමු.

එහෙනම් ඉතින් මුලින්ම for loop එකක් මාර්ගයෙන් i = 0 ඉඳන් n – 2 වෙනකන් Array එක පරික්ෂා කරමින් යමු . ඉතින් මෙහෙම යද්දී කලින් කියපු විදිහට i ස්ථානයේ තියන අගයට වඩා
i + 1 ස්ථානයේ තියන අගය අඩු නම් අපි අගයන් දෙක හුවමාරු කර ගමු.
මෙන්න මේ විදිහට ..

for i = 0 to i  A[i+1]){
                   swap(A[i] , A[i+1]);
              }

ඉතින් දැන් අපි මේ සම්පුර්ණ සිද්දිය Array එකේ length එක (n) වතාවක් සිද්ද කරමු.
එතකොට අපිට සම්පුර්ණයෙන්ම sort වුන Array එකක් බලා ගන්න පුළුවන්.

for k = 1 to k <= n-1
         for i = 0 to i  A[i+1]){
                       swap(A[i] , A[i+1]);
                    }

දැන් අපිට පුළුවන් මේ algorithm එක ටිකක් දියුණු කරන්න.
Array එකේ අග පියවරෙන් පියවර sort වන නිසා. හැම වටයකදීම සම්පුර්ණ Array එක පරික්ෂා කරන්න අවශ්‍ය වෙන්නේ නෑ. ඒක නිසා දෙවෙනි loop එක (inner loop එක) n – k – 1 දක්වා සලකා බැලුවහම ඇති. (k = 1 විට n – 2 දක්වාත් k = 2 විට n – 3 දක්වාත් යනාදී වශයෙන් කෙමෙන් කෙමෙන් පරාසය අඩු කර ගන්න අපිට පුළුවන්)
අනිත් කාරණය තමයි array එක මගදි sort උනොත් මොකද වෙන්නේ ? එතනින් ඉදිරියට සිද්ද කරන පරික්ෂා කිරීම් වලට ගතවෙන කාලය අපරාදේ නේද ? ඉතින් මේකට විසඳුමක් විදිහට අපිට පුළුවන් එක වටයකට අදාලව එක වතාවකදී හෝ swap වීමක් සිදු නොවුනෝතින් එතනින් loop එක (outer loop එක) break කරලා දාන්න. ඉතින් මේ කරුණු දෙකම සැලකිල්ලට අරගෙන අපිට මෙන්න මේ විදිහට Algorithm එක සකස් කර ගන්න පුළුවන් …

  for(k = 1; k <= n-1 ; k++) { 
     bool swapped = false;
      for(i = 0; i <= n-k-1; i++) {		
         if(A[i] > A[i+1]) {
           int temp = A[i];
            A[i] = A[i+1];
            A[i+1] = temp;
            swapped = true;
         }		
      }
      if(!swapped) {
         break;
      }
   }
Advertisements