একটি অ্যারে সাজানোর সমস্যা সমাধানের জন্য বেশ কয়েকটি মৌলিক অ্যালগরিদম রয়েছে। তাদের মধ্যে সবচেয়ে বিখ্যাত এক সন্নিবেশ সাজানোর. এর স্বচ্ছতা এবং সরলতার কারণে, কিন্তু কম দক্ষতার কারণে, এই পদ্ধতিটি প্রধানত প্রোগ্রামিং শেখানোর জন্য ব্যবহৃত হয়। এটি আপনাকে প্রাথমিক বাছাই প্রক্রিয়াগুলি বুঝতে দেয়৷
অ্যালগরিদমের বর্ণনা
সন্নিবেশ সাজানোর অ্যালগরিদমের সারমর্ম হল যে প্রাথমিক অ্যারের ভিতরে একটি সঠিকভাবে অর্ডার করা সেগমেন্ট তৈরি হয়। প্রতিটি উপাদান একে একে চেক করা অংশের সাথে তুলনা করা হয় এবং সঠিক জায়গায় ঢোকানো হয়। এইভাবে, সমস্ত উপাদানের মাধ্যমে পুনরাবৃত্তি করার পরে, তারা সঠিক ক্রমে সারিবদ্ধ হয়৷
উপাদান নির্বাচনের ক্রম যেকোনো হতে পারে, সেগুলি নির্বিচারে বা কিছু অ্যালগরিদম অনুযায়ী নির্বাচন করা যেতে পারে। প্রায়শই, অ্যারের শুরু থেকে অনুক্রমিক গণনা ব্যবহার করা হয়, যেখানে একটি ক্রমকৃত সেগমেন্ট গঠিত হয়।
বাছাইয়ের শুরুটি এই রকম হতে পারে:
- অ্যারের প্রথম উপাদানটি নিন।
- যেহেতু এটির সাথে তুলনা করার মতো কিছুই নেই, তাই এলিমেন্টটিকে অর্ডার অনুযায়ী নিনক্রম।
- দ্বিতীয় আইটেমে যান৷
- বাছাই নিয়মের উপর ভিত্তি করে প্রথমটির সাথে এটির তুলনা করুন।
- যদি প্রয়োজন হয়, জায়গাগুলিতে উপাদানগুলি অদলবদল করুন৷
- একটি ক্রমানুসারে প্রথম দুটি উপাদান নিন।
- তৃতীয় আইটেমে যান।
- এটি দ্বিতীয়টির সাথে তুলনা করুন, প্রয়োজনে অদলবদল করুন।
- যদি প্রতিস্থাপন করা হয়, প্রথমটির সাথে তুলনা করুন।
- একটি ক্রমানুসারে তিনটি উপাদান নিন।
এবং আসল অ্যারের শেষ না হওয়া পর্যন্ত।
বাস্তব জীবন সন্নিবেশ বাছাই
স্বচ্ছতার জন্য, দৈনন্দিন জীবনে এই সাজানোর প্রক্রিয়াটি কীভাবে ব্যবহার করা হয় তার একটি উদাহরণ দেওয়া মূল্যবান৷
উদাহরণস্বরূপ, একটি মানিব্যাগ ধরুন। শত, পাঁচশ, হাজার ডলারের বিল ব্যাংকনোটের বগিতে বিশৃঙ্খলায় পড়ে আছে। এটি একটি জগাখিচুড়ি, যেমন একটি হজপজে অবিলম্বে কাগজের সঠিক টুকরা খুঁজে পাওয়া কঠিন। ব্যাঙ্কনোটের অ্যারে অবশ্যই সাজাতে হবে৷
প্রথমটি হল 1000 রুবেলের একটি ব্যাঙ্কনোট, এবং এর পরপরই - 100। আমরা একশো নিয়ে এটিকে সামনে রাখি। পরপর তৃতীয়টি হল 500 রুবেল, এটির জন্য সঠিক জায়গা হল একশ থেকে এক হাজারের মধ্যে৷
যেভাবে আমরা প্রাপ্ত কার্ডগুলিকে "ফুল" খেলার সময় বাছাই করি যাতে তাদের নেভিগেট করা সহজ হয়৷
অপারেটর এবং হেল্পার ফাংশন
সন্নিবেশ বাছাই পদ্ধতিটি সাজানোর জন্য একটি প্রাথমিক অ্যারে ইনপুট হিসাবে নেয়, একটি তুলনা ফাংশন, এবং, যদি প্রয়োজন হয়, একটি ফাংশন যা উপাদান গণনার নিয়ম নির্ধারণ করে। প্রায়শই পরিবর্তে ব্যবহৃত হয়নিয়মিত লুপ স্টেটমেন্ট।
প্রথম উপাদানটি নিজেই একটি অর্ডারকৃত সেট, তাই তুলনাটি দ্বিতীয় থেকে শুরু হয়।
অ্যালগরিদম প্রায়ই দুটি মান (অদলবদল) বিনিময় করতে একটি সহায়ক ফাংশন ব্যবহার করে। এটি একটি অতিরিক্ত অস্থায়ী ভেরিয়েবল ব্যবহার করে, যা মেমরি খরচ করে এবং কোডটিকে কিছুটা ধীর করে দেয়।
একটি বিকল্প হল উপাদানগুলির একটি গ্রুপকে ভর করে স্থানান্তর করা এবং তারপরে বর্তমানটিকে মুক্ত স্থানে ঢোকানো। এই ক্ষেত্রে, পরবর্তী উপাদানে রূপান্তর ঘটে যখন তুলনা একটি ইতিবাচক ফলাফল দেয়, যা সঠিক ক্রম নির্দেশ করে।
বাস্তবায়নের উদাহরণ
নির্দিষ্ট বাস্তবায়ন মূলত ব্যবহৃত প্রোগ্রামিং ভাষা, এর সিনট্যাক্স এবং কাঠামোর উপর নির্ভর করে।
মান বিনিময়ের জন্য একটি অস্থায়ী পরিবর্তনশীল ব্যবহার করে ক্লাসিক সি বাস্তবায়ন:
int i, j, temp; (i=1; i =0; j--) { if (array[j] < temp) break; array[j + 1]=array[j]; array[j]=temp; } }
PHP বাস্তবায়ন:
($i=1; $i=0 &&$a[$j] > $x; $j--) { $a[$ j + 1]=$a[$j]; } $a[$j + 1]=$x; } }
এখানে, প্রথমে, সাজানোর শর্তের সাথে মেলে না এমন সমস্ত উপাদান ডানদিকে স্থানান্তরিত হয়, এবং তারপরে বর্তমান উপাদানটি ফাঁকা স্থানে ঢোকানো হয়।
জাভা কোড যখন লুপ ব্যবহার করে:
সর্বজনীন স্ট্যাটিক অকার্যকর সন্নিবেশSort(int arr) { for(int i=1; i =0 &&arr[prevKey] > currElem){ arr[prevKey+1]=arr[prevKey]; arr[prevKey]=currElem; prevKey--; } } }
কোডের সাধারণ অর্থ অপরিবর্তিত রয়েছে: অ্যারের প্রতিটি উপাদান ক্রমানুসারে পূর্ববর্তীগুলির সাথে তুলনা করা হয় এবং প্রয়োজনে তাদের সাথে অদলবদল করা হয়।
আনুমানিক চলমান সময়
অবশ্যই, সর্বোত্তম ক্ষেত্রে, অ্যালগরিদমের ইনপুট একটি অ্যারে হবে যা ইতিমধ্যেই সঠিকভাবে অর্ডার করা হয়েছে। এই পরিস্থিতিতে, অ্যালগরিদমকে প্রতিটি উপাদানকে এক্সচেঞ্জ না করেই সঠিক জায়গায় তা নিশ্চিত করতে পরীক্ষা করতে হবে। সুতরাং, চলমান সময় সরাসরি মূল অ্যারের O(n) দৈর্ঘ্যের উপর নির্ভর করবে।
সবচেয়ে খারাপ কেস ইনপুট হল বিপরীত ক্রমে সাজানো একটি অ্যারে। এর জন্য প্রচুর পরিমাণে পারমুটেশনের প্রয়োজন হবে, রানটাইম ফাংশনটি বর্গকৃত উপাদানের সংখ্যার উপর নির্ভর করবে।
একটি সম্পূর্ণরূপে বিন্যাসহীন অ্যারের জন্য সঠিক সংখ্যা নির্ণয় করা যেতে পারে সূত্রটি ব্যবহার করে:
n(n-1)/2
যেখানে n হল মূল অ্যারের দৈর্ঘ্য। এইভাবে, 100টি উপাদানকে সঠিক ক্রমে সাজাতে 4950টি পারমুটেশন লাগবে।
ছোট বা আংশিকভাবে সাজানো অ্যারে সাজানোর জন্য সন্নিবেশ পদ্ধতি খুবই কার্যকর। যাইহোক, গণনার উচ্চ জটিলতার কারণে এটি সর্বত্র প্রয়োগ করার পরামর্শ দেওয়া হয় না।
অ্যালগরিদমটি আরও অনেক জটিল বাছাই পদ্ধতিতে সহায়ক হিসেবে ব্যবহৃত হয়।
সমান মান সাজান
সন্নিবেশ অ্যালগরিদম তথাকথিত স্থিতিশীল প্রকারের অন্তর্গত। এর মানে,যে এটি অভিন্ন উপাদান অদলবদল করে না, তবে তাদের মূল ক্রম সংরক্ষণ করে। স্থায়িত্ব সূচক অনেক ক্ষেত্রেই সঠিক অর্ডারের জন্য গুরুত্বপূর্ণ৷
উপরেরটি একটি নৃত্যে সন্নিবেশ সাজানোর একটি দুর্দান্ত চাক্ষুষ উদাহরণ৷
