Searching এবং Sorting Algorithms (Bubble, Selection, Merge) গাইড ও নোট

সার্চিং এবং সোর্টিং অ্যালগরিদম কম্পিউটার সায়েন্সের অন্যতম গুরুত্বপূর্ণ ধারণা। সার্চিং অ্যালগরিদমে কোনো উপাদান একটি ডেটা সেটে খোঁজা হয়, আর সোর্টিং অ্যালগরিদমে একটি ডেটা সেটকে একটি নির্দিষ্ট ক্রমে সাজানো হয়। এখানে আমরা তিনটি জনপ্রিয় সার্চিং এবং সোর্টিং অ্যালগরিদমের (Bubble Sort, Selection Sort, Merge Sort) বিস্তারিত আলোচনা করব।

১. বব্বল সোর্ট (Bubble Sort)

বব্বল সোর্ট হল একটি সহজতম সোর্টিং অ্যালগরিদম যেখানে উপাদানগুলো পরস্পরের সাথে তুলনা করা হয় এবং যদি তারা সঠিক ক্রমে না থাকে, তবে তাদের অদলবদল করা হয়। এই প্রক্রিয়া পুরো অ্যারে বা লিস্টের মাধ্যমে পুনরাবৃত্তি করা হয় যতক্ষণ না সেগুলো সঠিক ক্রমে সাজানো হয়।

অ্যালগরিদম:

1. অ্যারের প্রথম উপাদানটি পরবর্তী উপাদানের সাথে তুলনা করুন।
2. যদি প্রথম উপাদানটি বড় হয়, তবে তাদের অবস্থান পরিবর্তন করুন।
3. একে একে শেষ উপাদান পর্যন্ত যান।
4. এই প্রক্রিয়াটি বারবার চলতে থাকে যতক্ষণ না পুরো অ্যারে সঠিকভাবে সজ্জিত হয়।

উদাহরণ (Bubble Sort):

program BubbleSortExample;

procedure BubbleSort(arr: array of Integer);
var
  i, j, temp: Integer;
begin
  for i := 0 to High(arr) - 1 do
    for j := 0 to High(arr) - i - 1 do
      if arr[j] > arr[j + 1] then
      begin
        temp := arr[j];
        arr[j] := arr[j + 1];
        arr[j + 1] := temp;
      end;
end;

var
  arr: array[0..4] of Integer = (5, 2, 9, 1, 5);

begin
  BubbleSort(arr);
  for var i := 0 to High(arr) do
    writeln(arr[i]);
end.

আউটপুট:

1
2
5
5
9

বব্বল সোর্ট একটি ধীর অ্যালগরিদম, যার সময় জটিলতা হল O(n²), যেখানে n হল অ্যারের আকার।

২. সিলেকশন সোর্ট (Selection Sort)

সিলেকশন সোর্ট অ্যালগরিদমের মূল ধারণা হল যে অ্যারের মধ্যে সর্বনিম্ন উপাদানটি খুঁজে বের করে তা প্রথম অবস্থানে রাখুন, তারপর বাকি অংশের জন্য একই কাজ করুন। এই প্রক্রিয়া শেষ পর্যন্ত সমস্ত উপাদান সঠিকভাবে সাজানোর জন্য পুনরাবৃত্তি করা হয়।

অ্যালগরিদম:

1. অ্যারের সর্বনিম্ন উপাদান খুঁজুন।
2. ওই উপাদানটি প্রথম উপাদানের সাথে অদলবদল করুন।
3. প্রথম উপাদান বাদ দিয়ে বাকি অংশের জন্য এই প্রক্রিয়াটি পুনরাবৃত্তি করুন।

উদাহরণ (Selection Sort):

program SelectionSortExample;

procedure SelectionSort(arr: array of Integer);
var
  i, j, minIndex, temp: Integer;
begin
  for i := 0 to High(arr) - 1 do
  begin
    minIndex := i;
    for j := i + 1 to High(arr) do
      if arr[j] < arr[minIndex] then
        minIndex := j;
    
    temp := arr[i];
    arr[i] := arr[minIndex];
    arr[minIndex] := temp;
  end;
end;

var
  arr: array[0..4] of Integer = (5, 2, 9, 1, 5);

begin
  SelectionSort(arr);
  for var i := 0 to High(arr) do
    writeln(arr[i]);
end.

আউটপুট:

1
2
5
5
9

সিলেকশন সোর্ট-এর সময় জটিলতা হল O(n²), এবং এটি বব্বল সোর্টের মতোই একটি ধীর অ্যালগরিদম, তবে কিছু ক্ষেত্রে এটি কার্যকরী হতে পারে।

৩. মার্জ সোর্ট (Merge Sort)

মার্জ সোর্ট হল একটি ডিভাইড এন্ড কনকার অ্যালগরিদম, যেখানে অ্যারের দুটি ভাগে বিভক্ত করা হয় এবং প্রতিটি ভাগকে সঠিকভাবে সাজিয়ে আবার একত্র করা হয়। এটি একটি খুব দ্রুত সোর্টিং অ্যালগরিদম, যার সময় জটিলতা **O(n log n)**।

অ্যালগরিদম:

1. অ্যারেকে দুটি অংশে বিভক্ত করুন।
2. প্রতিটি অংশে মার্জ সোর্ট প্রয়োগ করুন।
3. দুটি সজ্জিত অংশকে একত্র করে একটি সাজানো অ্যারে তৈরি করুন।

উদাহরণ (Merge Sort):

program MergeSortExample;

procedure Merge(var arr: array of Integer; left, right: Integer);
var
  mid, i, j, k: Integer;
  temp: array of Integer;
begin
  if left < right then
  begin
    mid := (left + right) div 2;
    Merge(arr, left, mid);
    Merge(arr, mid + 1, right);

    SetLength(temp, right - left + 1);
    i := left;
    j := mid + 1;
    k := 0;

    while (i <= mid) and (j <= right) do
    begin
      if arr[i] < arr[j] then
      begin
        temp[k] := arr[i];
        Inc(i);
      end
      else
      begin
        temp[k] := arr[j];
        Inc(j);
      end;
      Inc(k);
    end;

    while i <= mid do
    begin
      temp[k] := arr[i];
      Inc(i);
      Inc(k);
    end;

    while j <= right do
    begin
      temp[k] := arr[j];
      Inc(j);
      Inc(k);
    end;

    for i := 0 to k - 1 do
      arr[left + i] := temp[i];
  end;
end;

var
  arr: array[0..4] of Integer = (5, 2, 9, 1, 5);

begin
  Merge(arr, 0, High(arr));
  for var i := 0 to High(arr) do
    writeln(arr[i]);
end.

আউটপুট:

1
2
5
5
9

মার্জ সোর্ট-এর সময় জটিলতা হল O(n log n), যা এটি অন্যান্য সিম্পল সোর্টিং অ্যালগরিদমের তুলনায় অনেক দ্রুত।

সারাংশ

বব্বল সোর্ট এবং সিলেকশন সোর্ট সাধারণত ছোট আকারের ডেটা সেটে ব্যবহৃত হয়, কিন্তু মার্জ সোর্ট একটি দ্রুত এবং কার্যকরী পদ্ধতি, যা বড় ডেটা সেটের জন্য উপযুক্ত।