সর্টিংঃ সিলেকশন সর্ট

সর্টিং অ্যালগোরিদমের মুল কাজই হচ্ছে অ্যারেতে থাকা দুটি উপাদানের অবস্থান সোয়াপ(swap) বা বিনিময় করা। সিলেকশন সর্ট অ্যারের সুচকগুলোকে প্রতিটি ইন্ডেক্সের জন্য লুপ করে। এখানে মনে রাখতে হবে যে, যদি অ্যারে এর দৈর্ঘ্য n হয়, তবে ঐ অ্যারের ইন্ডেক্স সংখ্যা n হবে।

Ο(n2) এর সকল সর্ট অ্যালগোরিদমের মধ্যে আমার কাছে সিলেকশন সর্ট (Selection Sort) অনেক সহজ লাগে। এর মুল ধারণা হচ্ছে, তুমি শুরুতে প্রথম অবস্থানের সংখ্যাটি নির্বাচন করবে। তারপর ঐ সংখ্যার পরের সংখ্যাগুলো একে একে দেখবে। যদি দেখো পরের কোন সংখ্যা তোমার নির্বাচিত অবস্থানে থাকা সংখ্যার চেয়ে ছোট, তাহলে দুটি সংখ্যাকে সোয়াপ বা অদলবদল করে দিবে। এভাবে সব সংখ্যা দেখা শেষ হয়ে গেলে তোমার নির্বাচিত অবস্থানে সব থেকে ছোট সংখ্যা থাকবে।

এবার দ্বিতীয় অবস্থানের সংখ্যাটি নির্বারচন কর। বাকি সব সংখ্যা দিয়ে যাও, আর যদি দেখো যেই সংখ্যা দিয়ে যাচ্ছো তা ছোট, তাহলে অদলবদল করে ফেলো। এভাবে প্রতিটি সংখ্যা এক এক করে নির্বাচন করলে দকেহবে পুরো অ্যারেটি সর্ট হয়ে গেছে।

সিলেকশন সর্ট কভাবে কাজ করে?

সিলেকশন সর্ট অনেক বড় ডেটা সেটের জন্য উপযুক্ত না। আসলে কোন Ο(n2) অ্যালগোরিদমই অনেক বড় ডেটাসেটের জন্য উপযুক্তি না। বলে রাখি এখানে n হচ্ছে আইটেম সংখ্যা।

সিলেকশন সর্ট কিভাবে কাজ করে বোঝার জন্য আমরা নিচের অ্যারে সেট কে উদাহরণ হিসেবে নিতে পারি।

অ্যারেতে থাকা ডেটা লিস্টে আমরা দেখছি যে প্রথম ডেটা, মানে ১৪ সর্টেড আছে। কিন্তু আমরা যদি পুরো লিস্ট দেখি বা পুরো লিস্টে সার্চ করি, তাহলে দকেহবো যে ১০ সব থেকে ছোট ভ্যালু।

সিলেকশন সর্টের নিয়ম অনুযায়ী আমরা ১৪ এর জায়গা ১০ কে নিয়ে আসবো এবং ১০ এর জায়গা ১৪কে নিয়ে যাবো। এরফলে সব থেকে ছোট মান সবার শুরুতে থাকবে, এবং সর্টেড ও হবে।

এবার দ্বিতীয় অবস্থানের জন্য আমরা ৩৩ নির্বাচন করে সার্চিং শুরু করবো।

দ্বিতীয় অবস্থানের জন্য ৩৩ কে নিয়ে সার্চ দিলে দকেহা যাবে ১৪ সব থেকে ছোট। আর সিলেকশন সর্ট এর নিয়ম অনুযায়ী আমরা ৩৩ এর স্থানে ১৪ কে নিইয়ে আসবো, আর ১৪ এর স্থলে ৩৩।

১৪ এবং ৩৩ সোয়াপের পর আমাদের অ্যারেতে শুরুর দুইটা মান সর্টেড হবে ছোট থেকে বড় আকারে।

এভাবে তৃতীয়, চতুর্থ, পঞ্চমসহ বাকি অবস্থানের জন্য সব থেকে ছোট মান নির্বাচন করে পুরো অ্যারে সর্টেড করতে হবে। তুমি যদি এখন পর্যন্ত সব ঠিক থাক বুঝতে পারো, তাহলে তোমার সর্টেড ফলাফল হবেঃ ১০,১৪,১৯,২৭,২২,২৫,৪২,৪৫।

যদি বুঝতে না পারো বা সর্টিং করতে ভুল করো, তাহলে ফুল প্রসেসটি আরেকবার পড়। তোমাদের বোঝার সুবিধার জন্য ফুল প্রসেস নিচে দিলামঃ

তাহলে সিলেকশন সর্ট আর মুল কাজ কি দাঁড়ালো ? ছোট মান কে প্রথমে নিয়ে ফুল অ্যারেকেট সর্টেড করা, যেখানে ফলাফল হিসেবে আমরা শুরুতে পাবো সব থেকে ছোট মান আর সব শেষে পাবো সব থেকে বড় মান।

সিলেকশন সর্ট অ্যালগোরিদম যদি আমি আমার মত করে লিখি, তাহলে তা হবে নিম্নরুপঃ

Step 1 − Set MIN to location 0
Step 2 − Search the minimum element in the list
Step 3 − Swap with value at location MIN
Step 4 − Increment MIN to point to next element
Step 5 − Repeat until list is sorted

সিলেকশন সর্ট ইমপ্লিমেন্টশনের সব থেকে ছোট কোডঃ

for (int i=1; i<=n; i++) {
  for (int j=i+1; j<=n; j++) {
    if(num[i]>num[j]){
    //swap is inside algorithm header.
    swap(num[i], num[j]);
    }
  }
}

তুমি যদি সি ভালো পারো, তাহলে তোমার বোঝার সুবিদার জন্য আরো একটু সহজ করে করলে এমন হবেঃ

// C program for implementation of selection sort
#include <stdio.h>
 
void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}
 
void selectionSort(int arr[], int n)
{
    int i, j, min_idx;
 
    // One by one move boundary of unsorted subarray
    for (i = 0; i < n-1; i++)
    {
        // Find the minimum element in unsorted array
        min_idx = i;
        for (j = i+1; j < n; j++)
          if (arr[j] < arr[min_idx])
            min_idx = j;
 
        // Swap the found minimum element with the first element
        swap(&arr[min_idx], &arr[i]);
    }
}
 
/* Function to print an array */
void printArray(int arr[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
 
// Driver program to test above functions
int main()
{
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array: \n");
    printArray(arr, n);
    return 0;
}

আউটপুটঃ

Sorted array: 11 12 22 25 64

পাইথন আমার অনেক প্রিয় একটি ল্যাঙ্গুয়েজ। যদি তুমিও পাইথন পছন্দ করে, তবে সিলেকশন সর্ট কিভাবে পাইথনে ইমপ্লিমেন্ট করতে হয়, তা নিচে দিলামঃ

# Python program for implementation of Selection
# Sort
import sys
A = [64, 25, 12, 22, 11]
 
# Traverse through all array elements
for i in range(len(A)):
     
    # Find the minimum element in remaining 
    # unsorted array
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
             
    # Swap the found minimum element with 
    # the first element        
    A[i], A[min_idx] = A[min_idx], A[i]
 
# Driver code to test above
print ("Sorted array")
for i in range(len(A)):
    print("%d" %A[i]),

আউটপুটঃ

Sorted array: 11 12 22 25 64

আশাকরি সিলেকশন সর্টিং এখন থেকে তোমার কাছে অনেক সহজ লাগবে, যেমনটি আমার কাছে লাগে। তুমি যদি ইনসার্শন সর্টিং ভালো করে বুঝতে চাও, তাহলে আমার ইনসার্শন সর্ট পোস্ট পড়তে পারো।

এছাড়া বাবল সর্ট অ্যালগরিদম এর উপর আমার একটি অনেক সহজ একটি লেখাও আছে।