রুবি দিয়ে ইন্সারশন সর্টিং দক্ষতা অর্জন: ধাপে ধাপে গাইড

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

ডেটা সর্ট করার বিভিন্ন পদ্ধতি অন্বেষণ করার ক্রমে আমরা এখন ইন্সারশন সর্টের দিকে মোড় খাচ্ছি। ইন্সারশন সর্ট পছন্দ করার অনেক কারণ রয়েছে! প্রথমত, ইন্সারশন সর্ট স্থিতিশীল (stable), অর্থাৎ এটি সমান কী-বালা উপাদানগুলির আপেক্ষিক ক্রম পরিবর্তন করে না। এটি একটি ইন-প্লেস অ্যালগরিদম (in-place algorithm)ও, অর্থাৎ সর্ট করা উপাদানগুলি সংরক্ষণের জন্য এটি নতুন অ্যারে তৈরি করে না। চূড়ান্ত olarak, ইন্সারশন সর্ট বাস্তবায়ন করা αρκতেই সহজ, যা আপনি শীঘ্রই দেখতে পাবেন!

কেন এতে গুরুত্ব দেবেন

এখানে একই কথা বারবার বলতে হচ্ছে এমন লাগতে পারে, কিন্তু পূর্বের সব পোস্টে যেমন আলোচনা করা হয়েছে, ডেটা সর্ট করার বিভিন্ন প্রক্রিয়া এবং প্রতিটি পদ্ধতির ট্রেড-অফ বোঝা গুরুত্বপূর্ণ। উদাহরণস্বরূপ, ইন্সারশন সর্ট বড় ডেটাসেটের জন্য খুব উপযোগী নয় (এটি আমরা নিচে আরও আলোচনা করব), তবে ছোট ডেটাসেট এবং প্রায়-প্রায় সর্ট করা ডেটাসেটের জন্য এটি খুবই দক্ষ এবং কার্যকর হতে পারে। বাস্তবায়নের মাধ্যমে আপনি বুঝতে পারবেন কেন। নিশ্চিতভাবে আপনি আপনার প্রোগ্রামিং ভাষার বিল্ট-ইন সর্টিং মেথড ব্যবহার করবেন, কিন্তু এটি ইন্টারভিউতে পেয়ার-প্রোগ্রামিং এক্সারসাইজ বা টাইম কমপ্লেক্সিটি সংক্রান্ত প্রশ্ন হিসেবে আসতে পারে। এই পোস্ট শেষ হলে আপনি সহজেই ইন্সারশন সর্ট কোড করতে এবং এর টাইম কমপ্লেক্সিটি বোঝতে পারবেন।

দৃষ্টিমূলক প্রতিনিধিত্ব

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

কোডের ধাপে ধাপে ওয়াক-থ্রু

কোডটি দেখি!

def insertion_sort(array)
  for i in 1...(array.length)  # ধাপ ১
    j = i                      # ধাপ ২
    while j > 0                # ধাপ ৩
      if array[j-1] > array[j] # ধাপ ৪
        temp = array[j]
        array[j] = array[j-1]
        array[j-1] = temp
      else
        break
      end
      j = j - 1                # ধাপ ৫
    end
  end
  return array
end

ধাপ ১:

আমরা একটি for লুপ দিয়ে শুরু করি যা ভেরিয়েবল i-কে ১ সেট করে এবং অ্যারے দৈর্ঘ্যের সমান হওয়া পর্যন্ত বাড়ায়।

ধাপ ২:

আমরা j নামে অন্য একটি ভেরিয়েবল তৈরি করি এবং এটি ১ দিয়ে ইনিশিয়ালাইজ করি (কারণ i সেটা)।

ধাপ ৩:

এরপর একটি নেস্টেড while লুপ থাকে যা ততক্ষণ চলবে যতক্ষণ j শূন্যের চেয়ে বড়। যেহেতু j ১ দিয়ে শুরু হয়, এটি অন্তত একবার এক্সিকিউট হবে।

ধাপ ৪:

if... else ব্লকটি প্রথমে ভয়াবহ দেখতে পারে, কিন্তু চিন্তা করবেন না। ওয়াক-থ্রু করার পর এটি বোঝা যাবে (আপনি ইউটিউবের নৃত্য উদাহরণটি পুনর্বার দেখতে পারেন!)।

if শর্তে আমরা চেক করি array[j-1] কি array[j]-এর চেয়ে বড়। যেহেতু j বর্তমানে ১, তাই আমরা মূলত array[0] এবং array[1]-এর তুলনা করছি। এটি অর্থহীন নয় কারণ আমরা অ্যারের প্রথম দুটি উপাদান তুলনা করছি।

যদি প্রথম উপাদান (array[0]) পরেরটি (array[1])-এর চেয়ে বড় হয়, তাহলে অবশ্যই সোয়াপ করতে হবে, যা if ব্লকে করা হয়। কিন্তু যদি array[0] মানটি array[1]-এর চেয়ে ছোট হয়, তবে চমৎকার! কিছু করতে হবেনা কারণ এটি ইতিমধ্যে সর্ট করা, তাই আমরা সহজে else ব্লকে break এ যাব।

ধাপ ৫:

এখান থেকে আমরা j ডিক্রিমেন্ট করি। এখন আমরা ফিরে for লুপে যাই, এবং i এখন ২ হবে। আপনি কল্পনা করতে পারেন কিভাবে আমরা while লুপের প্রথম ইটারেশনে array[1] এবং array[2] তুলনা করব, এবং তারপর আবার while লুপে যাব কারণ আমাদের j এখন ২ থেকে শুরু হয়েছে, ১ থেকে না।

বাস্তব ডেটার সাথে উদাহরণ

নিচের উদাহরণ অ্যারে ব্যবহার করে কোডটি ওয়াক-থ্রু করি: [5,7,2,10,9,12]

প্রথম ইটারেশনে, আমরা 5 এবং 7 তুলনা করব। যেহেতু 5 < 7, আমরা দ্রুত if/else-এ서 বের হয়ে যাব এবং পরবর্তীতে যাব।

পরবর্তী ইটারেশনে, আমরা 7 এবং 2 তুলনা করি। এখন এই মানগুলি সোয়াপ করতে হবে, তাই আমরা পাব [5, 2, 7, 10, 9, 12]। তারপর 2-কে আবার 5-এর সাথে সোয়াপ করব ফলাফল [2, 5, 7, 10, 9, 12] পাওয়ার জন্য।

for লুপের পরবর্তী ইটারেশনে, আমরা 10 এবং 7 তুলনা করব -- যей! এগুলো ইতিমধ্যে ক্রমে আছে।

আগে বাড়ते, আমরা 10 এবং 9 তুলনা করি এবং দেখি সোয়াপ করতে হবে। তারপর, 7 যেহেতু 9-এর চেয়ে ছোট, আর কোনো সোয়াপ প্রয়োজন নেই। এখন আমাদের আছে [2, 5, 7, 9, 10, 12]।

শেষ ইটারেশনে 12 পাওয়া যায়, যা 10-এর চেয়ে বড়, তাই ওলালা! আমরা সর্ট করা শেষ করলাম।

পারফরম্যান্স বিশ্লেষণ

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

যদি অ্যারে ইতিমধ্যে সর্ট করা থাকে, তবে ইন্সারশন সর্ট কোড O(n)-এ চলে কারণ এটি শুধু n বার লুপ করতে হবে। এটি যাচাই করতে চাইলে, মেথডের শুরুতে puts i যোগ করুন এবং ইতিমধ্যে সর্ট করা অ্যারে পাস করে প্রোগ্রাম চালান।

যদি অ্যারে রিভার্স-সর্ট করা থাকে, তবে ইন্সারশন সর্ট O(n²)-এ চলে। আপনি মस्तিষ্কে এটি ভিজ্যুয়ালাইজ করতে পারেন। যেহেতু এটি প্রতিটি উপাদানের জন্য সোয়াপ করতে হবে, এটি প্রতিবার if শর্তে যাবে। ভয়ানক! আবার, রিভার্স-সর্ট করা অ্যারে পাস করে এবং একটি কাউন্টার ভেরিয়েবল প্রিন্ট করে এটি পরীক্ষা করতে পারেন।

যদিও ওয়ার্স্ট কেস O(n²) যা, আপনি মনে করবেন, বাবল সর্ট এবং সিলেকশন সর্টের জন্যও একই, তবে ইন্সারশন সর্ট সাধারণত পছন্দনীয়। কারণ, আমরা দেখেছি, বেস্ট কেস হতে পারে O(n), যেখানে সিলেকশন সর্টের বেস্ট কেস O(n²)। ইন্সারশন সর্টে বাবল সর্টের চেয়ে কম সোয়াপ হয়, তাই এখানেও এটা জিতেছে।

উপসংহার

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