পূর্ণসংখ্যা শ্রেণিকরণ

কম্পিউটার বিজ্ঞানে পূর্ণসংখ্যা বিন্যস্তকরণ বলতে একটি পূর্ণ সংখ্যার সেট কে তাদের মান অনুযায়ী বিন্যস্ত করাকে বুঝায় । পূর্ণ সংখ্যা বিন্যস্ত করার জন্য ডিজাইন করা অ্যালগরিদম গুলো প্রায়শই বিভিন্ন বিন্যস্তকরণ সমস্যা সমাধানে প্রয়োগ করা হয়, যেখানে কী (Key) গুলো দশমিক সংখ্যা, মূলদ সংখ্যা অথবা বর্ণসমষ্টি 
কী গুলোতে পাটিগাণিতীক অপারেশন প্র‍্যোগের সুবিধা থাকায় পূর্ণসংখ্যা বিন্যস্তকরণ অ্যালগরিদমগুলো অনেক ক্ষেত্রে তুলনামূলক বিন্যস্তকরণ অ্যালগরিদমগুলোর চেয়ে অধিক দ্রুত, যা নির্ভর করে হিসাব-নিকাশে কোন কোন অপারেশন ব্যবহার করা হবে এবং সংখ্যার পরিমাণের উপর।
পূর্ণ সংখ্যা বিন্যাসকরণ অ্যালগোরিদমগুলোর মধ্যে পিজিয়নহোল বিন্যস্তকরন, গণন বিন্যস্তকরন এবং র‍্যাডিক্স বিন্যস্তকরণ বাস্তব সম্মত এবং ব্যাপকভাবে ব্যবহৃত। ছোট worst-case সময়সীমাবিশিষ্ট অন্যান্য বিন্যস্তকরণ অ্যালগরিদমগুলো ৬৪ কিংবা তার চেয়ে কম বিট প্রতি শব্দ বিশিষ্ট কম্পিউটার স্থাপত্যের জন্য বাস্তবসম্মত নয় বলে ধারণা করা হয়।
মূলত তিনটি পরামিতির উপর পূর্ণসংখ্যা বিন্যস্তকরণ অ্যালগরিদম এর সময়সীমা নির্ভর করে : মোট উপাত্তের সংখ্যা , সর্বোচ্চ সম্ভাব্য "কী" এর মান , এবং যে কম্পিউটারে অ্যালগরিদমটি সম্পন্ন করা হবে সেখানে একটি শব্দ ধারণ করতে যে সংখ্যক বিটের প্রয়োজন হয় । ধরা হয় যে, ; অর্থাৎ ইনপুট উপাত্তের একটি ধারা ধারণ করতে মেশিন এর বিট/শব্দ যথেষ্ট বড়।
পূর্ণসংখ্যা বিন্যস্তকরার অ্যালগরিদম গুলো সাধারণত পয়েন্টার মেশিন অথবা রেন্ডম অ্যাক্সেস মেশিন মডেলের উপর ভিত্তি করে কাজ করার জন্য ডিজাইন করা হয়। এ দুটি মডেলের প্রধান পার্থক্য হল কীভাবে মেমোরিতে এড্রেস দেওয়া হয়। রেনডম অ্যাকসেস মেশিন রেজিষ্টারে থাকা যে কোন মানকে মেমোরি অ্যাড্রেস হিসেবে ব্যবহার করতে দেয়। ফলে তালিকা অনুসন্ধান এর মাধ্যমে কি কোন জটিল অপারেশন খুব দ্রুত প্রয়োগ করা যায় অন্যদিকে পয়েন্ট এর মডেলে মেমোরি এড্রেস গুলো পয়েন্টারে সংরক্ষিত থাকে যা বীজগাণিতিক অপারেশন করতে সক্ষম নয়। উভয় মডেলে উপাত্ত এর মান গুলো যোগ বিটভিত্তিক বুলিয়ান অপারেশন এবং বাইনারি শিফট অপারেশন করা যায়। এক্ষেত্রে সমান্তরাল random-access মেশিন এর মত অন্যান্য মডেলগুলোকেও বিবেচনা করা হয়। 
প্রাধান্য সারি হলো উপাত্তগুলোর প্রাধান্য বজায় রাখার জন্য এক ধরনের ডেটা স্ট্রাকচার, যাতে সর্বনিম্ন প্রাধান্যবিশিষ্ট কোন একটি উপাত্তকে খোঁজা এবং অপসারণ করার অপারেশন। বিদ্যমান তুলনাভিত্তিক প্রাধান্য সারি যেমন বাইনারি হিপ প্রতিটি আপডেট লগারিদমিক হারে সময় প্রয়োজন হয়। কিন্তু অন্যান্য গঠন যেমন ভ্যান এম বস ট্রি অথবা বাকেট সারিতে ছোট পূর্ণসংখ্যা প্রাধান্য বিশিষ্ট ইনপুট তুলনামূলকভাবে দ্রুত কাজ করে। এসব ডাটা স্ট্রাকচার সিলেকশন সর্ট আলগরিদম এ ব্যবহৃত হতে পারে, যা কোন পূর্ণসংখ্যার একটি সংগ্রহ থেকে সবচেয়ে ছোট উপাদান খুঁজে বের করে এবং অপসারণ এর মাধ্যমে পৌনঃপুনিকভাবে বিন্যস্ত করে। এই অ্যালগোরিদমে প্রাধান্য সারি ব্যবহার করা যেতে পারে এবং সংখ্যক উপাদান বিশিষ্ট কোন সংগ্রহের জন্য সময়সীমা নির্ধারণ করা যেতে পারে। যেমন সিলেকশন সর্ট এ প্রাধান্য সারি হিসেবে বাইনারি হিপকে ব্যবহার করলে অ্যালগরিদম কি হিপ সর্টের দিকে ধাবিত হয়, যা সময় নেয়। এর পরিবর্তে বাকেট সারি দ্বারা সিলেকশন সর্ট ব্যবহার করলে এটি পিজিয়ন হোল সর্ট এ রূপ নেয় এবং ভ্যান এমস বস ট্রি অথবা অন্যান্য পূর্ণ সংখ্যা প্রাধান্য শাড়ি ব্যবহার অন্য দ্রুততর পূর্ণ সংখ্যা বিন্যস্ত করার অ্যালগরিদম এর দিকে নেয়। । এ ধরনের ব্যবহার করে দেখান যে, যদি প্রতিটি কী এর জন্য সময় দিয়ে কোন বিন্যস্তকরণ অ্যালগরিদম নির্বাহ করা যায়, তবে প্রাধান্য সারি ডাটা স্ট্রাকচার এ কোন উপাদান যোগ বা অপসারণের জন্য একই সময় সীমা প্রযোজ্য হবে। তার বক্তব্য অতি জটিল এবং তালিকা অনুসন্ধান অথবা দ্রুত গুণন প্রক্রিয়া উপলব্ধ তা মেনে নিতে হয়। কিন্তু তিনি শুধুমাত্র যোগ এবং বুলিয়ান অপারেশন এর দ্বারা বিকল্প প্রাধান্য সারি প্রস্তাব করেছেন যাতে প্রতিটি অপারেশনের জন্য সময় প্রয়োজন, যা সর্বোচ্চ পৌনঃপুনিক লগারিদম এর গুণিতক হতে পারে। 
প্রচলিত আলগরিদমসমূহের মধ্যে পিজিয়ন হোল সর্ট,র‍্যাডিক্স সর্ট, গণন সর্ট ইত্যাদি বহুল ব্যবহৃত এবং ব্যবহারিক ভাবে প্রযুক্ত।
পূর্ণ সংখ্যা বিন্যস্ত করার অ্যালগরিদম সমূহের উপর পরিচালিত গবেষণা সমুহ ব্যবহারিক এর চেয়েও তাত্ত্বিকভাবে প্রতিকূল অবস্থা বিশ্লেষণ এর উপর জোর দেয়া হয়েছে এবং এ ধরনের গবেষণা থেকে প্রাপ্ত অ্যালগরিদমসমূহ এখনো 64-bit কম্পিউটার স্থাপত্যের জন্য উপযোগী নয় বলে ধারণা করা হয়, যদিও অনেক পরীক্ষণ দেখায় যে এদের মধ্যে কিছু অ্যালগরিদম ১২০ অথবা তার চেয়ে বেশি বিট প্রতি শব্দ এর জন্য র‍্যাডিক্স সর্ট এর উন্নত সংস্করণ হতে পারে। পাশাপাশি, বৃহৎ উপাত্ত সেটের জন্য অনেক পূর্ণ সংখ্যা বিন্যস্তকরণ অ্যালগোরিদমের নিকটবর্তী রেনডম মেমোরি এক্সেস প্যাটার্ন অন্যান্য মেমোরি হায়ারার্কির মাধ্যমে ডিজাইন করা পূর্ণ সংখ্যা বিন্যস্তকরণ অ্যালগরিদমের তুলনায় একটু সময়সাপেক্ষ।
পূর্ণসংখ্যা বিন্যস্তকরণ DARPA উচ্চ উৎপাদনশীলতা কম্পিটিং সিস্টেম বিচ্ছিন্ন গণিত বেঞ্চমার্ক সাইটের ছয়টি বেঞ্চমার্কের একটি বেঞ্চমার্ক এবং NAS Parallel Benchmarks সাইটের এগারোটির মধ্যে একটি বেঞ্চমার্ক প্রদান করে।
পিজিয়ন হোল শর্ট অথবা র‍্যাডিক্স সর্ট উভয়ই সময়ে থেকে পর্যন্ত কী বিশিষ্ট সংখ্যক উপাত্ত বিন্যস্ত করতে পারে। পিজিয়ন হোল সর্টে (প্রায়শই বাকেট সর্টও বলা হয়) উপাত্ত উপাদানগুলোর পয়েন্টারগুলো একটি বাকেটের সারণীতে কী গুলোকে ইন্ডেক্স ধরে বিভাজিত থাকে, যা লিংকড লিস্ট এর মত কালেকশন ডেটা টাইপ এর মাধ্যমে উপস্থাপন করা হয়। অতঃপর আউটপুট সারণী গঠন করতে সবগুলো বাকেট একত্র করা হয়। গণন সর্ট বাকেটের টেবিল এর পরিবর্তে প্রতিটি কী এর উপাদান সংখ্যা নির্ণয়ের জন্য কাউন্টারের সারণি ব্যবহার করে। অতঃপর প্রাকসমষ্টির মাধ্যমে বিন্যস্ত ফলাফলে অবস্থানসমূহের পরিসর নির্ণয় করা হয়, যাতে প্রত্যেকটি কী অবস্থান করবে। সর্বশেষে, দ্বিতীয় দফায় প্রত্যেকটি উপাদান তার ফলাফল এর কী অবস্থানে স্থানান্তরিত হয়। উভয় অ্যালগোরিদমে একটি সরল লুপ ব্যবহৃত হয় যা ইনপুট উপাত্ত এর ক্ষেত্রে ) সময় নেয়।
র‍্যাডিক্স সর্ট হল একটি বিন্যস্ত করার অ্যলগরিদম, যা উপাত্ত গুলোর মধ্যে একাধিক লুপ পরিচালনার মাধ্যমে পিজিয়ন হোল শর্ট এর চেয়েও বড় কী এর জন্য কাজ করে। প্রত্যেক দফায় ইনপুট গুলিকে কী গুলোর শুধুমাত্র একটি অংশ অনুযায়ী বিভিন্ন সর্টিং অ্যালগরিদম (যেমন পিজিয়ন হোল সর্ট অথবা গণন সর্ট) প্রয়োগ করে বিন্যস্ত করে। কী গুলোকে বিভিন্ন অংশে বিভক্ত করতে র‍্যাডিক্স সর্ট আলগরিদম কিছু নির্বাচিত র‍্যাডিক্স এর সাপেক্ষে পজিশনাল নোটেশন হিসাব করে ; তম দফার কীয়ের অংশটি পজিশনাল নোটেশন এ সর্বনিম্ন তাৎপর্যপূর্ণ অঙ্ক থেকে সর্বোচ্চ তাৎপর্যপূর্ণ অঙ্ক এর দিকে সম্পূর্ণ কী এর তম অঙ্ক। এ আলগরিদম ঠিকঠাক কাজ করার জন্য প্রত্যেক দফায় ব্যবহৃত সর্টিং অ্যালগরিদম টি অবশ্যই স্থিতিশীল হতে হবে : সমঅঙ্ক বিশিষ্ট উপাদান গুলো একে অপরের সঙ্গে অবস্থান বদল করতে পারবে না। সর্বোচ্চ কর্মদক্ষতার জন্য উপাত্ত উপাদান সমূহের সংখ্যা এর কাছাকাছি র‍্যাডিক্স ধরতে হয়। পাশাপাশি র‍্যাডিক্স হিসেবে এর কাছাকাছি ২ এর ঘাত ব্যবহার করলে শুধুমাত্র বাইনারি শিফট এবং মাস্ক অপারেশন এর মাধ্যমে দ্রুততম উপায়ে হিসাব করা যায়। পিজিয়ন হোল সর্ট অথবা গণনা সর্ট কে ভিত্তি অ্যালগরিদম ধরে এসব ব্যবস্থাপনা সাপেক্ষে র‍্যাডিক্স সর্টিং অ্যালগরিদম থেকে পর্যন্ত কি বিশিষ্ট সংখ্যক উপাত্তকে সময়ে বিন্যস্ত করতে পারে।
অনেক পূর্ণসংখ্যা বিন্যস্তকরণ আলগরিদম আবিষ্কৃত হয়েছে যাদের তাত্ত্বিক বিশ্লেষণে দেখা যায় যে, তারা উপাদান সংখ্যা কী সমূহের পরিসর এবং মেশিন শব্দ আকার ইত্যাদি যথেষ্ট বড় হলেও তুলনামূলক অ্যালগরিদম, পিজিয়ন হোল আলগরিদম অথবা র‍্যাডিক্স সর্টিং অ্যালগরিদম এর চেয়েও ভাল আচরণ করে। কোন অ্যালগরিদমটি সবচেয়ে ভালো কাজ করবে তা এসব পরামিতিসমূহের উপর নির্ভর করে।
তবে এসব এলগরিদম এর তাত্ত্বিক সুবিধা থাকলেও, বাস্তবে যে পরিসরের উপাত্ত বিন্যস্ত করার প্রয়োজন হয় তাতে খুব একটা দক্ষ ভাবে প্রয়োগ সম্ভব হয় না। 
 থেকে পরিসরের মধ্যে সংখ্যক কী কে বিন্যস্ত করার জন্য প্রাধান্য সারি হিসেবে ভ্যান এম বস ট্রি সময়সীমার মধ্যে ব্যবহার করা যেতে পারে। যখন যথেষ্ট বড়, তখন এটি র‍্যাডিক্স সর্ট এর তুলনায় ভালো কাজ করে। তবে ভ্যান এম বস ক্রিম ব্যবহার করার জন্য শব্দ বিশিষ্ট সরাসরি মেমোরি অ্যাড্রেস অথবা হ্যাশ টেবিল এর প্রয়োজন। এর Y-fast trie হল সমপারদর্শী আরেকটি প্রাধান্য সারি (হ্যাশ টেবিলে বিচ্ছিন্নতাকে প্রাধান্য দিয়ে)।
word RAM হিসাবের মডেলে এর একটি জটিল এবং বিক্ষিপ্ত অ্যালগরিদম এই সময়সীমা আরও কমিয়ে পর্যন্ত নিয়ে আসে।
একটি পূর্ণ সংখ্যা বিন্যস্তকরণ অ্যালগরিদম "অসংরক্ষণশীল" বলা হয়, যদি এর প্রয়োজনীয় শব্দের আকার , 
এর অসংরক্ষণশীল বিন্যস্তকরণ অ্যালগরিদমটি দুটি বিন্যস্ত ধারাকে একীভূত করার জন্য কেনের এর bitonic সর্টিং এর উপর ভিত্তি করে একটি সাবরুটিন ব্যবহার করেন। প্যাক সর্টিং অ্যালগরিদম তার ইনপুটকে একটি প্যাকে রূপান্তরিত করে, যার প্রত্যেকটি শব্দ এই সাবরুটিনটি বারবার ব্যবহার করে বিন্যস্ত করে। যখনই ইনপুট গুলো প্যাক ফর্মে আসে , Albers and Hagerup এক প্রকারের একীভূত বিন্যস্তকরণ অ্যালগরিদম ব্যবহার করে এদেরকে বিন্যস্ত করেন। অ্যালগরিদমটি রৈখিক সময়ে এর ইনপুট গুলো কে বিন্যস্ত করতে পারে, যেখানে একটি শব্দের সংখ্যক কী থাকে ;অর্থাৎ যখন কিছু ধ্রুবক এর জন্য হয়।
যখন কী এর আকার ছোট থাকে, তখন পিজিয়ন হোল সর্ট, রাদিক্স সর্ট, গণন সর্ট এবং ভ্যান এম বস সর্ট খুব ভালো কাজ করে ; কিন্তু কী গুলোর আকার বৃহত্তর হলে, তারা তুলনামূলক অ্যালগরিদম এর তুলনায় ধীর হয়ে যায়। তবে যখন উপাদানের সংখ্যার তুলনায় কী এর আকার বৃহত্তর হয়ে যায়, তখন সমান্তরাল প্রোগ্রাম এর মাধ্যমে এসব অ্যালগোরিদমের ভালো ফলাফল পাওয়া যেতে পারে।
 বিশ্লেষণ এর বৈপরীত্যান্তর মডেল উপস্থাপন করেন , যাতে পূর্ণ সংখ্যা কী গুলোর পরিসরের ব্যাপারে কোন রূপ পূর্বজ্ঞান থাকে না এবং শুধুমাত্র উপাত্তের সংখ্যার ভিত্তিতে অ্যালগরিদমের পারফরম্যান্স বিচার করা হয়। অন্যভাবে বলা যায়, এই মডেলে সংখ্যক উপাদান বিশিষ্ট কোন সেটে অ্যালগোরিদমের প্রযুক্ত সময় এবং   এর মানের যেকোনো সমাবেশের জন্য প্রতিকূল হবে। Fredman and Willard's fusion tree এর সর্টিং অ্যালগরিদম টি ছিল এই ধরনের প্রথম অ্যালগরিদম, যার সময় সীমা ছিল ; যেকোনো এবং   এর জন্য এটি তুলনামূলকভাবে তুলনামূলক বিন্যস্তকরণ অ্যালগরিদম হতে উন্নত।তাদের অ্যালগোরিদমের বিকল্প সংস্করণ যাতে [[দৈব নির্বাচন|দৈব সংখ্যাল্ল এবং পূর্ণসংখ্যার ভাগ অপারেশন বিদ্যমান, একে তে উন্নীত করে।
তাদের কাজের পরে, এমনকি আরো উন্নত অ্যালগরিদম আবিষ্কৃত হয়েছে। উদাহরণস্বরূপ, পৌনঃপুনিক ভাবে Albers–Hagerup বিন্যস্ত করার অ্যালগরিদম প্রযুক্ত না হয় ততক্ষণ পর্যন্ত–Reisch পরিসর হ্রাসকরণ পদ্ধতি ব্যবহারের মাধ্যমে সময়ে বিন্যস্তকরণ সম্ভব; তবে, এই অ্যালগোরিদমের পরিসর হ্রাসকরণ অংশটুকু হয় প্রচুর মেমোরি ( এর সমানুপাতে) অথবা হ্যাশ টেবিল গঠনের প্রয়োজন পড়ে।
[[বিষয়শ্রেণী:সর্টিং অ্যালগোরিদম]]
[[বিষয়শ্রেণী:অ্যালগোরিদম]]
[[বিষয়শ্রেণী:সংখ্যাতত্ত্ব]]