সর্টিং অ্যালগরিদমগুলি একটি তালিকার উপাদানগুলিকে সাজানোর জন্য ব্যবহৃত হয়। বিভিন্ন অ্যালগরিদম বিভিন্ন কার্যকরীতা, জটিলতা এবং সুবিধা প্রদান করে। নিচে চারটি জনপ্রিয় সর্টিং অ্যালগরিদম—বব্বল সর্ট, ইনসার্শন সর্ট, কোয়িক সর্ট, এবং মার্জ সর্ট—বিস্তারিত আলোচনা করা হলো।
১. বব্বল সর্ট (Bubble Sort)
বব্বল সর্ট একটি সহজ সর্টিং অ্যালগরিদম যা তালিকার প্রতিটি উপাদানকে তুলনা করে এবং প্রয়োজন অনুসারে স্থান পরিবর্তন করে।
কাজের প্রক্রিয়া:
- তালিকার প্রথম উপাদানটি পরের উপাদানের সাথে তুলনা করুন।
- যদি প্রথমটি বড় হয়, তাহলে তাদের স্থান পরিবর্তন করুন।
- এটি সম্পূর্ণ তালিকা পরিদর্শন করে এবং এই প্রক্রিয়াটি তালিকার শেষ পর্যন্ত পুনরাবৃত্তি করুন।
- এই প্রক্রিয়াটি যতক্ষণ না তালিকা সাজানো হয় ততক্ষণ চালাতে থাকুন।
উদাহরণ (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)
সময়ের জটিলতা: O(n^2) (গড় ও খারাপ ক্ষেত্রে)
২. ইনসার্শন সর্ট (Insertion Sort)
ইনসার্শন সর্ট একটি সহজ এবং কার্যকরী সর্টিং অ্যালগরিদম যা একটি উপাদানকে নিয়মিতভাবে সঠিক স্থানে ইনসার্ট করে।
কাজের প্রক্রিয়া:
- প্রথম উপাদানটি একটি সাজানো তালিকা হিসাবে মনে করুন।
- পরবর্তী উপাদানটি নিয়ে কাজ করুন এবং সেটিকে সঠিক স্থানে ইনসার্ট করুন।
- এটি পুরো তালিকা জুড়ে পুনরাবৃত্তি করুন।
উদাহরণ (Python):
def insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and key < arr[j]: # স্থান খোঁজা
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key # ইনসার্ট করা
# ব্যবহারের উদাহরণ
arr = [64, 34, 25, 12, 22, 11, 90]
insertion_sort(arr)
print("Sorted array:", arr)
সময়ের জটিলতা: O(n^2) (গড় ও খারাপ ক্ষেত্রে)
৩. কোয়িক সর্ট (Quick Sort)
কোয়িক সর্ট একটি কার্যকরী এবং দ্রুত সর্টিং অ্যালগরিদম, যা ভাগাভাগি এবং শাসন (divide and conquer) কৌশল ব্যবহার করে।
কাজের প্রক্রিয়া:
- একটি পিভট উপাদান নির্বাচন করুন।
- তালিকার অন্যান্য উপাদানগুলিকে পিভটের তুলনায় ছোট ও বড় দুই ভাগে ভাগ করুন।
- পুনরাবৃত্তি করে প্রতিটি ভগ্নাংশ সাজান।
উদাহরণ (Python):
def quick_sort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot] # পিভটের থেকে ছোট
middle = [x for x in arr if x == pivot] # পিভটের সমান
right = [x for x in arr if x > pivot] # পিভটের থেকে বড়
return quick_sort(left) + middle + quick_sort(right)
# ব্যবহারের উদাহরণ
arr = [64, 34, 25, 12, 22, 11, 90]
sorted_arr = quick_sort(arr)
print("Sorted array:", sorted_arr)
সময়ের জটিলতা: O(n log n) (গড় ক্ষেত্রে), O(n^2) (খারাপ ক্ষেত্রে)
৪. মার্জ সর্ট (Merge Sort)
মার্জ সর্ট একটি অন্য একটি জনপ্রিয় ও কার্যকরী সর্টিং অ্যালগরিদম, যা ভাগাভাগি এবং শাসন কৌশল ব্যবহার করে।
কাজের প্রক্রিয়া:
- তালিকাটি দুইটি সমান ভগ্নাংশে ভাগ করুন।
- প্রতিটি ভগ্নাংশের জন্য মার্জ সর্ট রিক্রসিভলি প্রয়োগ করুন।
- সাজানো উপাদানগুলিকে একত্রিত (merge) করুন।
উদাহরণ (Python):
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left_half = arr[:mid]
right_half = arr[mid:]
merge_sort(left_half) # বাম অংশ মার্জ সর্ট
merge_sort(right_half) # ডান অংশ মার্জ সর্ট
i = j = k = 0
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
# ব্যবহারের উদাহরণ
arr = [64, 34, 25, 12, 22, 11, 90]
merge_sort(arr)
print("Sorted array:", arr)
সময়ের জটিলতা: O(n log n) (গড় এবং খারাপ ক্ষেত্রে)
উপসংহার
বব্বল সর্ট, ইনসার্শন সর্ট, কোয়িক সর্ট, এবং মার্জ সর্ট চারটি জনপ্রিয় সর্টিং অ্যালগরিদম, প্রত্যেকটির নিজস্ব বৈশিষ্ট্য, সময় জটিলতা, এবং ব্যবহার রয়েছে। সঠিক অ্যালগরিদম নির্বাচন করা ডেটা পরিচালনার দক্ষতার জন্য গুরুত্বপূর্ণ। কোডের কার্যকারিতা এবং কার্যকরী ডেটা সংগঠন নিশ্চিত করতে বিভিন্ন পরিস্থিতিতে সঠিক সর্টিং অ্যালগরিদম প্রয়োগ করা উচিত।
Read more
