রুবিতে সন্নিবেশ বাছাই বোঝা

দ্রষ্টব্য:এটি রুবির সাথে বিভিন্ন সাজানোর অ্যালগরিদম বাস্তবায়নের দিকে লক্ষ্য করা একটি সিরিজের 4 অংশ। পার্ট 1 অন্বেষণ করা বুদ্বুদ সাজানো, অংশ 2 অন্বেষণ করা নির্বাচনের সাজানো, এবং অংশ 3 অন্বেষণ করা মার্জ সাজানো৷

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

কেন যত্ন

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

একটি ভিজ্যুয়াল প্রতিনিধিত্ব

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

কোডের ধাপে ধাপে হাঁটা

আসুন কোডটি দেখি!

def insertion_sort(array)
    for i in 1...(array.length)  # Step 1
        j = i # Step 2
        while j > 0 # Step 3
            if array[j-1] > array[j] # Step 4
                temp = array[j]
                array[j] = array[j-1]
                array[j-1] = temp
            else
                break
            end
            j = j - 1 # Step 5
        end
    end
    return array
end

ধাপ 1:

আমরা একটি for দিয়ে শুরু করি লুপ যা পরিবর্তনশীল i সেট করে 1 থেকে এবং i পর্যন্ত বৃদ্ধি পেতে থাকে আমাদের অ্যারের দৈর্ঘ্যের সমান।

ধাপ 2:

আমরা আরেকটি পরিবর্তনশীল j তৈরি করি এবং এটিকে 1 এর মান দিয়ে আরম্ভ করুন (যেহেতু এটাই i হয়)।

ধাপ 3:

এর পরে, আমাদের একটি নেস্টেড আছে while লুপ যা j পর্যন্ত চলতে থাকবে শূন্যের চেয়ে বড়। যেহেতু আমরা j দিয়ে শুরু করি 1 এর সমান, আমরা জানি এটি অন্তত একবার কার্যকর হবে।

পদক্ষেপ 4:

if... else ব্লক সম্ভবত প্রথমে ভীতিকর দেখায়, কিন্তু চিন্তা করবেন না। আমরা একবার এটির মধ্য দিয়ে হেঁটে গেলে এটি বোঝা যাবে (এবং আপনি সর্বদা নাচের YouTube উদাহরণটি আবার দেখতে পারেন!)।

if-এর জন্য শর্ত, আমরা [j-1] কিনা তা পরীক্ষা করি array[j] থেকে বড় . যেহেতু j বর্তমানে 1, আমরা মূলত array[0] তুলনা করব array[1] সহ . এটি অর্থপূর্ণ কারণ আমরা অ্যারের প্রথম দুটি উপাদান তুলনা করছি৷

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

ধাপ 5:

এখান থেকে, আমরা j হ্রাস করি . এখন, আমরা for-এ ফিরে এসেছি লুপ, এবং i এখন 2 হতে যাচ্ছে . আপনি কল্পনা করতে পারেন কিভাবে আমরা array[1] তুলনা করব array[2] সহ while এর মধ্যে প্রথম পুনরাবৃত্তির জন্য লুপ, এবং তারপর আমরা আসলে while দিয়ে যাব আবার লুপ করুন কারণ আমাদের j 2 এ শুরু হয়েছে বনাম 1 .

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

চলুন নিম্নলিখিত উদাহরণ অ্যারে ব্যবহার করে এই কোডের মধ্য দিয়ে চলুন:[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^2) এ চলবে আপনি আপনার মাথায় এটি কল্পনা করতে সক্ষম হতে পারে. যেহেতু এটিকে পরপর অদলবদল করতে হবে, তাই এটি if এ আঘাত করবে প্রতিটি একক উপাদানের জন্য শর্ত। হায়! আবার, একটি বিপরীত সাজানো অ্যারেতে পাস করে নির্দ্বিধায় এটি চেষ্টা করুন এবং একটি কাউন্টার ভেরিয়েবল তৈরি করুন যা মুদ্রিত হয়৷

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

রেপ আপ

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