বেসিক সর্টিং অ্যালগরিদম: Bubble Sort, Selection Sort, Insertion Sort

বেসিক সর্টিং অ্যালগরিদম

সর্টিং অ্যালগরিদমগুলো বিভিন্ন ডেটা সেটকে একটি নির্দিষ্ট ক্রমে সাজানোর জন্য ব্যবহৃত হয়। নিচে কিছু বেসিক সর্টিং অ্যালগরিদমের ধারণা দেওয়া হলো।

১. Bubble Sort

Bubble Sort হলো একটি সরল সর্টিং অ্যালগরিদম, যেখানে বারবার তালিকার পাশের উপাদানগুলোর তুলনা করা হয় এবং বড় উপাদানগুলোকে শেষে সরিয়ে দেওয়া হয়। এটি প্রতিটি ধাপে বৃহত্তম উপাদানকে সঠিক স্থানে সরিয়ে দেয়, যেমন বুদ্বুদ পানির ওপরে উঠে আসে।

কাজ করার পদ্ধতি:

1. তালিকার প্রতিটি উপাদান পরীক্ষা করে।
2. পাশের উপাদানগুলোর তুলনা করা হয় এবং প্রয়োজন অনুযায়ী স্থান পরিবর্তন করা হয়।
3. প্রতিটি পাসে তালিকার সর্বশেষ উপাদান সঠিক স্থানে চলে আসে।
4. তালিকা পুরোপুরি সর্টেড না হওয়া পর্যন্ত এই ধাপগুলো পুনরাবৃত্তি করা হয়।

টাইম কমপ্লেক্সিটি:

• Worst Case: O(n²)
• Best Case: O(n) (যদি তালিকা আগে থেকেই সাজানো থাকে)

Python উদাহরণ:

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# ব্যবহার উদাহরণ
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print("Sorted array:", arr)

২. Selection Sort

Selection Sort অ্যালগরিদমটি তালিকায় ন্যূনতম উপাদানটি খুঁজে বের করে এবং সেটিকে সঠিক স্থানে সরিয়ে রাখে। প্রতিটি ধাপে বাকি অংশের জন্য এটি পুনরাবৃত্তি করে।

কাজ করার পদ্ধতি:

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

টাইম কমপ্লেক্সিটি:

• Worst Case: O(n²)
• Best Case: O(n²)

Python উদাহরণ:

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_index = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_index]:
                min_index = j
        arr[i], arr[min_index] = arr[min_index], arr[i]

# ব্যবহার উদাহরণ
arr = [64, 25, 12, 22, 11]
selection_sort(arr)
print("Sorted array:", arr)

৩. Insertion Sort

Insertion Sort হলো এমন একটি অ্যালগরিদম যেখানে তালিকার প্রতিটি উপাদানকে একটি সঠিক স্থানে স্থানান্তর করা হয়। এটি প্রতিটি নতুন উপাদানকে সাজানো অংশে যুক্ত করে এবং সঠিক স্থানে স্থাপন করে।

কাজ করার পদ্ধতি:

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

টাইম কমপ্লেক্সিটি:

• Worst Case: O(n²)
• Best Case: O(n) (যদি তালিকা আগে থেকেই সাজানো থাকে)

Python উদাহরণ:

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

# ব্যবহার উদাহরণ
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print("Sorted array:", arr)

তুলনামূলক চার্ট

উপসংহার

Bubble Sort, Selection Sort, এবং Insertion Sort সরল ও মৌলিক সর্টিং অ্যালগরিদম হিসেবে ব্যবহার করা হয়। প্রত্যেকটি অ্যালগরিদমের নিজস্ব সুবিধা ও অসুবিধা রয়েছে। তবে ছোট তালিকায় বা বিশেষ পরিস্থিতিতে এই অ্যালগরিদমগুলো কার্যকরী।