পাইথনে সিলেকশন সর্ট

সিলেকশন সর্টঃ বাবল সর্টের মত আরেকটা সহজ সর্টিং অ্যালগরিদম হচ্ছে সিলেকশন সর্ট। সিলেকশন সর্টে প্রতিটা ইটারেশনে মিনিমাম বা ম্যাক্সিমাম নাম্বার খুঁজে বের করে সর্টেড লিস্টের নির্দিষ্ট পজিশনে রাখা হয়।

যদি আমরা ছোট থেকে বড় সংখ্যার জন্য সিলেকশন সর্ট ব্যবহার করি, তাহলে সিলেকশন সর্টের ধাপ গুলো হবেঃ

প্রথম ধাপঃ
লিস্টের প্রথম সংখ্যাকে মিনিমাম হিসেবে সেট করা।

দ্বিতীয় ধাপঃ

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

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

সিলেকশন সর্টের সুডো কোড নিচের মত করে লেখা যায়ঃ

selection_sort(list):
     for i=0 to length(list):
     min  = list[0]
           for each unsorted item:
                   if item < min
           min = item
      swap (min, first_unsorted_item)
end selection_sort

 

ধরে নিচ্ছি 7, 9, 5, 8, 3 এই সংখ্যা গুলো ছোট থেকে বড় আকারে সাজাতে হবে। তার জন্য সিলেকশন সর্টের ধাপ গুলো হবে নিচের মত করেঃ

প্রথম সংখ্যা বা 7 কে মিনিমাম হিসেবে সেট করতে হবে। যেমন min = 7 ।

 

এরপর লিস্টের দ্বিতীয় আইটেমের সাথে min ভ্যালুর তুলনা করবে। এই ক্ষেত্রে 7 এবং 9 এর মধ্যে। যেহেতু 7 নয় থেকে ছোট, তাই মিন ভ্যালু পরিবর্তন হবে না। পরবর্তী সংখ্যা বা তৃতীয় সংখ্যার সাথে min ভ্যালুর তুলনা করবে। এই ক্ষেত্রে  7 এবং 5 এর মধ্যে। যেহেতু 7 থেকে 5 ছোট। তাই min = 5 সেট করবে। এরপরে 8 এর সাথে min ভ্যালুর তুলনা করবে। যেহেতু  5 থেকে 8 বড়, তাই কোন পরিবর্তন হবে না। লিস্টের পরবর্তী আইটেম বা 3 এর সাথে min ভ্যালু 5 এর তুলনা করবে। যেহেতু 5 থেকে 3 ছোট, তাই min ভ্যালু হিসেবে 3 সেট করবে।

প্রথম ইটারেশন শেষে লিস্টের প্রথম আইটেমের সাথে min ভ্যাল্যুর স্থান বদল হবে। এই ক্ষেত্রে 7 এবং 3 এর স্থান বদল হবে। এবং এই প্রথম ইটারেশনে আমরা প্রথম সবচেয়ে ছোট সংখ্যা পেয়ে যাবো। তাই দ্বিতীয় ইটারেশনের ক্ষেত্রে আমাদের একটা সংখ্যা কম তুলনা করতে হবে।

 

দ্বিতীয় ইটারেশনের শুরুতে আনসর্টেড লিস্টের প্রথম আইটেম min হিসেবে সেট করতে হবে। এই ক্ষেত্রে 9 হচ্ছে আনসর্টেড অংশের প্রথম আইটেম।

 

 

দ্বিতীয় ইটারেশন শেসে আমরা আরো একটি সর্টেড সংখ্যা পেয়ে যাবো। আর তা হচ্ছে 5। তাহলে তৃতীয় ইটারেশনে দুইটা সংখ্যা কম তুলনা করতে হবে। কারণ 3 এবং 5 সাজানো অবস্থায় রয়েছে।

এভাবে তৃতীয় ইটারেশনের শুরুতে আনসর্টেড লিস্টের প্রথম আইটেম min হিসেবে সেট করতে হবে। এইখানেও 9 হচ্ছে আনসর্টেড অংশের প্রথম আইটেম।

তৃতীয় ইটারেশন শেষে আমরা মোট তিনটে সর্টেড সংখ্যা পেয়ে যাবো। 3,5,7।

চতুর্থ ইটারেশনের শুরুতে আনসর্টেড অংশের প্রথম ভ্যালু হচ্ছে  8। তাই min = 8 সেট করতে হবে।

এরপর 8 এর সাথে পরবর্তী আইটেমের তুলনা করবে। 8 এবং 9 এর মধ্যে 8ই ছোট। স্থান পরিবর্তন করতে গিয়ে দেখা যাবে দুইটাই সাজানো অবস্থায় আছে। তাই ইটারেশন শেষ করবে এবং সর্টেড লিস্ট পাওয়া যাবে।

 

পাইথনে আমরা সিলেকশন সর্ট নিচের মত করে ইমপ্লিমেন্ট করতে পারিঃ

def selection_sort(list, size):
   
    for step in range(size):
 
        min = step

        for i in range(step + 1, size):

            # select the minimum element 
            if list[i] < list[min]:
                min = i
         
        # swipe items
        (list[step], list[min]) = (list[min], list[step])


numbers = [7, 9, 5, 8, 3]
list_size = len(numbers)
selection_sort(numbers, list_size)
print(numbers)

 

উপের প্রোগ্রামে if list[i] < list[min] এর পরিবর্তে if list[i] > list[min] ব্যবহার করলেই কোন সংখ্যাকে বড় থেকে ছোট আকারে সাজিয়ে দিবে।