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

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

কী গুলোতে পাটিগাণিতীক অপারেশন প্র‍্যোগের সুবিধা থাকায় পূর্ণসংখ্যা বিন্যস্তকরণ অ্যালগরিদমগুলো অনেক ক্ষেত্রে তুলনামূলক বিন্যস্তকরণ অ্যালগরিদমগুলোর চেয়ে অধিক দ্রুত, যা নির্ভর করে হিসাব-নিকাশে কোন কোন অপারেশন ব্যবহার করা হবে এবং সংখ্যার পরিমাণের উপর।

পূর্ণ সংখ্যা বিন্যাসকরণ অ্যালগোরিদমগুলোর মধ্যে পিজিয়নহোল বিন্যস্তকরন, গণন বিন্যস্তকরন এবং র‍্যাডিক্স বিন্যস্তকরণ বাস্তব সম্মত এবং ব্যাপকভাবে ব্যবহৃত। ছোট worst-case সময়সীমাবিশিষ্ট অন্যান্য বিন্যস্তকরণ অ্যালগরিদমগুলো ৬৪ কিংবা তার চেয়ে কম বিট প্রতি শব্দ বিশিষ্ট কম্পিউটার স্থাপত্যের জন্য বাস্তবসম্মত নয় বলে ধারণা করা হয়।

সাধারণ বিবেচ্য বিষয়সমূহ

হিসাবের মডেল

মূলত তিনটি পরামিতির উপর পূর্ণসংখ্যা বিন্যস্তকরণ অ্যালগরিদম এর সময়সীমা নির্ভর করে : মোট উপাত্তের সংখ্যা n , সর্বোচ্চ সম্ভাব্য কী এর মান K, এবং যে কম্পিউটারে অ্যালগরিদমটি সম্পন্ন করা হবে সেখানে একটি শব্দ ধারণ করতে যে সংখ্যক বিটের প্রয়োজন হয় w। ধরা হয় যে, w ≥ log₂(max(n, K)); অর্থাৎ ইনপুট উপাত্তের একটি ধারা ধারণ করতে মেশিন এর বিট/শব্দ যথেষ্ট বড়।

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

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

বিন্যস্তকরন বনাম পূর্ণসংখ্যা প্রাধান্য সারি

প্রাধান্য সারি হলো উপাত্তগুলোর প্রাধান্য বজায় রাখার জন্য এক ধরনের ডেটা স্ট্রাকচার, যাতে সর্বনিম্ন প্রাধান্যবিশিষ্ট কোন একটি উপাত্তকে খোঁজা এবং অপসারণ করার অপারেশন। বিদ্যমান তুলনাভিত্তিক প্রাধান্য সারি যেমন বাইনারি হিপ প্রতিটি আপডেট লগারিদমিক হারে সময় প্রয়োজন হয়। কিন্তু অন্যান্য গঠন যেমন ভ্যান এম বস ট্রি অথবা বাকেট সারিতে ছোট পূর্ণসংখ্যা প্রাধান্য বিশিষ্ট ইনপুট তুলনামূলকভাবে দ্রুত কাজ করে। এসব ডাটা স্ট্রাকচার সিলেকশন সর্ট আলগরিদম এ ব্যবহৃত হতে পারে, যা কোন পূর্ণসংখ্যার একটি সংগ্রহ থেকে সবচেয়ে ছোট উপাদান খুঁজে বের করে এবং অপসারণ এর মাধ্যমে পৌনঃপুনিকভাবে বিন্যস্ত করে। এই অ্যালগোরিদমে প্রাধান্য সারি ব্যবহার করা যেতে পারে এবং n সংখ্যক উপাদান বিশিষ্ট কোন সংগ্রহের জন্য সময়সীমা নির্ধারণ করা যেতে পারে। যেমন সিলেকশন সর্ট এ প্রাধান্য সারি হিসেবে বাইনারি হিপকে ব্যবহার করলে অ্যালগরিদম কি হিপ সর্টের দিকে ধাবিত হয়, যা O(n log n) সময় নেয়। এর পরিবর্তে বাকেট সারি দ্বারা সিলেকশন সর্ট ব্যবহার করলে এটি পিজিয়ন হোল সর্ট এ রূপ নেয় এবং ভ্যান এমস বস ট্রি অথবা অন্যান্য পূর্ণ সংখ্যা প্রাধান্য শাড়ি ব্যবহার অন্য দ্রুততর পূর্ণ সংখ্যা বিন্যস্ত করার অ্যালগরিদম এর দিকে নেয়। ।Thorup (2007) এ ধরনের ব্যবহার করে দেখান যে, যদি প্রতিটি কী এর জন্য T(n) সময় দিয়ে কোন বিন্যস্তকরণ অ্যালগরিদম নির্বাহ করা যায়, তবে প্রাধান্য সারি ডাটা স্ট্রাকচার এ কোন উপাদান যোগ বা অপসারণের জন্য একই সময় সীমা প্রযোজ্য হবে। তার বক্তব্য অতি জটিল এবং তালিকা অনুসন্ধান অথবা দ্রুত গুণন প্রক্রিয়া উপলব্ধ তা মেনে নিতে হয়। কিন্তু তিনি শুধুমাত্র যোগ এবং বুলিয়ান অপারেশন এর দ্বারা বিকল্প প্রাধান্য সারি প্রস্তাব করেছেন যাতে প্রতিটি অপারেশনের জন্য T(n) + T(log n) + T(log log n) + ... সময় প্রয়োজন, যা সর্বোচ্চ পৌনঃপুনিক লগারিদম এর গুণিতক হতে পারে।

ব্যবহারযোগ্যতা

প্রচলিত আলগরিদমসমূহের মধ্যে পিজিয়ন হোল সর্ট,র‍্যাডিক্স সর্ট, গণন সর্ট ইত্যাদি বহুল ব্যবহৃত এবং ব্যবহারিক ভাবে প্রযুক্ত। পূর্ণ সংখ্যা বিন্যস্ত করার অ্যালগরিদম সমূহের উপর পরিচালিত গবেষণা সমুহ ব্যবহারিক এর চেয়েও তাত্ত্বিকভাবে প্রতিকূল অবস্থা বিশ্লেষণ এর উপর জোর দেয়া হয়েছে এবং এ ধরনের গবেষণা থেকে প্রাপ্ত অ্যালগরিদমসমূহ এখনো 64-bit কম্পিউটার স্থাপত্যের জন্য উপযোগী নয় বলে ধারণা করা হয়, যদিও অনেক পরীক্ষণ দেখায় যে এদের মধ্যে কিছু অ্যালগরিদম ১২০ অথবা তার চেয়ে বেশি বিট প্রতি শব্দ এর জন্য র‍্যাডিক্স সর্ট এর উন্নত সংস্করণ হতে পারে। পাশাপাশি, বৃহৎ উপাত্ত সেটের জন্য অনেক পূর্ণ সংখ্যা বিন্যস্তকরণ অ্যালগোরিদমের নিকটবর্তী রেনডম মেমোরি এক্সেস প্যাটার্ন অন্যান্য মেমোরি হায়ারার্কির মাধ্যমে ডিজাইন করা পূর্ণ সংখ্যা বিন্যস্তকরণ অ্যালগরিদমের তুলনায় একটু সময়সাপেক্ষ।

পূর্ণসংখ্যা বিন্যস্তকরণ DARPA উচ্চ উৎপাদনশীলতা কম্পিটিং সিস্টেম বিচ্ছিন্ন গণিত বেঞ্চমার্ক সাইটের ছয়টি বেঞ্চমার্কের একটি বেঞ্চমার্ক এবং NAS Parallel Benchmarks সাইটের এগারোটির মধ্যে একটি বেঞ্চমার্ক প্রদান করে।

ব্যবহারিক অ্যালগরিদম

পিজিয়ন হোল শর্ট অথবা র‍্যাডিক্স সর্ট উভয়ই O(n + K) সময়ে 0 থেকে K − 1 পর্যন্ত কী বিশিষ্ট n সংখ্যক উপাত্ত বিন্যস্ত করতে পারে। পিজিয়ন হোল সর্টে (প্রায়শই বাকেট সর্টও বলা হয়) উপাত্ত উপাদানগুলোর পয়েন্টারগুলো একটি বাকেটের সারণীতে কী গুলোকে ইন্ডেক্স ধরে বিভাজিত থাকে, যা লিংকড লিস্ট এর মত কালেকশন ডেটা টাইপ এর মাধ্যমে উপস্থাপন করা হয়। অতঃপর আউটপুট সারণী গঠন করতে সবগুলো বাকেট একত্র করা হয়। গণন সর্ট বাকেটের টেবিল এর পরিবর্তে প্রতিটি কী এর উপাদান সংখ্যা নির্ণয়ের জন্য কাউন্টারের সারণি ব্যবহার করে। অতঃপর প্রাকসমষ্টির মাধ্যমে বিন্যস্ত ফলাফলে অবস্থানসমূহের পরিসর নির্ণয় করা হয়, যাতে প্রত্যেকটি কী অবস্থান করবে। সর্বশেষে, দ্বিতীয় দফায় প্রত্যেকটি উপাদান তার ফলাফল এর কী অবস্থানে স্থানান্তরিত হয়। উভয় অ্যালগোরিদমে একটি সরল লুপ ব্যবহৃত হয় যা ইনপুট উপাত্ত এর ক্ষেত্রে O(n)) সময় নেয়।

র‍্যাডিক্স সর্ট হল একটি বিন্যস্ত করার অ্যলগরিদম, যা উপাত্ত গুলোর মধ্যে একাধিক লুপ পরিচালনার মাধ্যমে পিজিয়ন হোল শর্ট এর চেয়েও বড় কী এর জন্য কাজ করে। প্রত্যেক দফায় ইনপুট গুলিকে কী গুলোর শুধুমাত্র একটি অংশ অনুযায়ী বিভিন্ন সর্টিং অ্যালগরিদম (যেমন পিজিয়ন হোল সর্ট অথবা গণন সর্ট) প্রয়োগ করে বিন্যস্ত করে। কী গুলোকে বিভিন্ন অংশে বিভক্ত করতে র‍্যাডিক্স সর্ট আলগরিদম কিছু নির্বাচিত র‍্যাডিক্স এর সাপেক্ষে পজিশনাল নোটেশন হিসাব করে ; i তম দফার কীয়ের অংশটি পজিশনাল নোটেশন এ সর্বনিম্ন তাৎপর্যপূর্ণ অঙ্ক থেকে সর্বোচ্চ তাৎপর্যপূর্ণ অঙ্ক এর দিকে সম্পূর্ণ কী এর i তম অঙ্ক। এ আলগরিদম ঠিকঠাক কাজ করার জন্য প্রত্যেক দফায় ব্যবহৃত সর্টিং অ্যালগরিদম টি অবশ্যই স্থিতিশীল হতে হবে : সমঅঙ্ক বিশিষ্ট উপাদান গুলো একে অপরের সঙ্গে অবস্থান বদল করতে পারবে না। সর্বোচ্চ কর্মদক্ষতার জন্য উপাত্ত উপাদান সমূহের সংখ্যা n এর কাছাকাছি র‍্যাডিক্স ধরতে হয়। পাশাপাশি র‍্যাডিক্স হিসেবে n এর কাছাকাছি ২ এর ঘাত ব্যবহার করলে শুধুমাত্র বাইনারি শিফট এবং মাস্ক অপারেশন এর মাধ্যমে দ্রুততম উপায়ে হিসাব করা যায়। পিজিয়ন হোল সর্ট অথবা গণনা সর্ট কে ভিত্তি অ্যালগরিদম ধরে এসব ব্যবস্থাপনা সাপেক্ষে র‍্যাডিক্স সর্টিং অ্যালগরিদম 0 থেকে K − 1 পর্যন্ত কি বিশিষ্ট n সংখ্যক উপাত্তকে O(n log_n K) সময়ে বিন্যস্ত করতে পারে।

তাত্ত্বিক অ্যালগরিদম সমূহ

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

ছোট কী এর জন্য অ্যালগরিদম

0 থেকে K − 1 পরিসরের মধ্যে n সংখ্যক কী কে বিন্যস্ত করার জন্য প্রাধান্য সারি হিসেবে ভ্যান এম বস ট্রি O(n log log K) সময়সীমার মধ্যে ব্যবহার করা যেতে পারে। যখন K যথেষ্ট বড়, তখন এটি র‍্যাডিক্স সর্ট এর তুলনায় ভালো কাজ করে। তবে ভ্যান এম বস ক্রিম ব্যবহার করার জন্য K শব্দ বিশিষ্ট সরাসরি মেমোরি অ্যাড্রেস অথবা হ্যাশ টেবিল এর প্রয়োজন।Willard (1983) এর Y-fast trie হল সমপারদর্শী আরেকটি প্রাধান্য সারি (হ্যাশ টেবিলে বিচ্ছিন্নতাকে প্রাধান্য দিয়ে)।

Kirkpatrick & Reisch (1984) এরকম আর একটু জটিল এবং তাত্ত্বিকভাবে ভালো পারফরম্যান্সের পদ্ধতি প্রচলন করেন। তারা লক্ষ্য করেন যে র‍্যাডিক্স সর্ট এর প্রত্যেকটি দফা পরিসর হ্রাসকরণের উপায় হিসেবে বিবেচনা করা যেতে পারে, যা কী এর আকারকে n এর গুণিতকভাবে হ্রাস করে; এর পরিবর্তে তাদের উপায়টি কোন কী কে পূর্ববর্তী মান এর বর্গমূল পরিমাণ কমায় যাতে পূর্বের তুলনায় অর্ধেক সংখ্যক বিটের প্রয়োজন হয়। র‍্যাডিক্স সর্ট এ তারা প্রত্যেকটি কী কে দুই অঙ্ক বিশিষ্ট b ভিত্তিক সংখ্যা বিবেচনা করেন, যা প্রায় √K। অতঃপর তারা বৃহৎ কিন্তু বিক্ষিপ্ত হ্যাশ টেবিল অথবা সরাসরি মেমোরি অ্যাড্রেস এর মাধ্যমে তাদের উচ্চ অঙ্কসমূহের ক্রমানুসারে বাকেট এ গ্রুপ করেন। প্রত্যেকটি বাকেটের প্রতিনিধি হল সর্ববৃহৎ কী বিশিষ্ট উপাদান। উপাদানের তালিকা কে প্রতিনিধিদের উচ্চ অঙ্ক এবং অপ্রতিনিধিদের নিম্ন অঙ্ক অনুসারে বিন্যস্ত করে, এই তালিকার উপাদানগুলোকে পুনরায় বাকেটে গ্রুপ করে, প্রত্যেকটি বাকেট কে বিন্যস্ত ক্রমানুসারে সাজানো যেতে পারে এবং বিন্যাস তালিকার প্রতিনিধিদেরকে নিয়ে বাকেটগুলোর সংযোগে একটি বিন্যস্ত পাওয়া যেতে পারে। এভাবে বিন্যস্ত করার সমস্যাটি আরো ছোট হয়ে যায়। কী গুলো ছোট থাকলে এ অ্যালগরিদমটির সময়সীমা O(n log log_n K)।

word RAM হিসাবের মডেলে Han & Thorup (2002) এর একটি জটিল এবং বিক্ষিপ্ত অ্যালগরিদম এই সময়সীমা আরও কমিয়ে O(n√log log K) পর্যন্ত নিয়ে আসে।

বৃহত্তর শব্দের জন্য অ্যালগরিদম

একটি পূর্ণ সংখ্যা বিন্যস্তকরণ অ্যালগরিদম অসংরক্ষণশীল বলা হয়, যদি এর প্রয়োজনীয় শব্দের আকার w, log max(n, K) এর চেয়েও তাৎপর্যপূর্ণ ভাবে বড় হয়। উদাহরণস্বরূপ, যদি w ≥ K এবং প্রতিটি কি স্বতন্ত্র হয় তবে কী এর একটি সেটকে i অবস্থানে ১ বিট বিশিষ্ট একটি বিট ভেক্টর দ্বারা উপস্থাপন এবং ক্রমান্বয়ে নিম্ন তাৎপর্যপূর্ণ অঙ্ক অপসারণের মাধ্যমে রৈখিক সময়ে বিন্যস্ত করা সম্ভব, যেখানে i ইনপুট কী গুলোর একটি।

Albers & Hagerup (1997) এর অসংরক্ষণশীল বিন্যস্তকরণ অ্যালগরিদমটি দুটি বিন্যস্ত ধারাকে একীভূত করার জন্য কেনের এর bitonic সর্টিং এর উপর ভিত্তি করে একটি সাবরুটিন ব্যবহার করেন। প্যাক সর্টিং অ্যালগরিদম তার ইনপুটকে একটি প্যাকে রূপান্তরিত করে, যার প্রত্যেকটি শব্দ এই সাবরুটিনটি বারবার ব্যবহার করে বিন্যস্ত করে। যখনই ইনপুট গুলো প্যাক ফর্মে আসে , Albers and Hagerup এক প্রকারের একীভূত বিন্যস্তকরণ অ্যালগরিদম ব্যবহার করে এদেরকে বিন্যস্ত করেন। অ্যালগরিদমটি রৈখিক সময়ে এর ইনপুট গুলো কে বিন্যস্ত করতে পারে, যেখানে একটি শব্দের Ω(log n log log n) সংখ্যক কী থাকে ;অর্থাৎ যখন কিছু ধ্রুবক c > 0 এর জন্য log K log n log log n ≤ cw হয়।

স্বল্পসংখ্যক উপাদানের জন্য অ্যালগরিদম

যখন কী এর আকার ছোট থাকে, তখন পিজিয়ন হোল সর্ট, রাদিক্স সর্ট, গণন সর্ট এবং ভ্যান এম বস সর্ট খুব ভালো কাজ করে  ; কিন্তু কী গুলোর আকার বৃহত্তর হলে, তারা তুলনামূলক অ্যালগরিদম এর তুলনায় ধীর হয়ে যায়। তবে যখন উপাদানের সংখ্যার তুলনায় কী এর আকার বৃহত্তর হয়ে যায়, তখন সমান্তরাল প্রোগ্রাম এর মাধ্যমে এসব অ্যালগোরিদমের ভালো ফলাফল পাওয়া যেতে পারে।

Ajtai, Fredman & Komlós (1984) এর দেওয়া একটি ফলাফলে তিনি cell-probe model ব্যবহার করেন (একটি কৃত্রিম মডেল যা কোনো অ্যালগোরিদমের জটিলতা শুধুমাত্র মেমরি এক্সেস পরিমাপের মাধ্যমে নির্ধারণ করে)। তাদের কাজের উপর ভিত্তি করে , Fredman & Willard (1994) দুটি ডেটা স্ট্রাকচার বর্ণনা করেন, Q-heap এবং atomic heap, যা একটি রেনডম এক্সেস মেশিন এ প্রয়োগ করা সম্ভব। Q-heap বাইনারি ট্রাই এর বিট-সমান্তরাল সংস্করণ এবং O((log N)^1/4) সংখ্যক উপাদানের জন্য ধ্রুবসময়ে উভয় প্রাধান্য সারি অপারেশন এবং পূর্ববর্তী ও পরবর্তী কুয়েরি নির্বাহ করে, যেখানে N ≤ 2^w হল ডাটা স্ট্রাকচারটি প্রয়োগের জন্য পূর্বে হিসাবকৃত টেবিল এর আকার। atomic heap হলো বি-ট্রী, যেখানে প্রত্যেকটি নোড এক একটি Q-heap; এটি ধ্রুব সময়ে (log N)^O(1) সংখ্যক উপাদানকে বিন্যস্ত করতে পারে।

Andersson et al. (1998) স্বাক্ষর বিন্যস্তকরণ নামে একটি র‍্যান্ডমাইজড অ্যালগরিদম প্রদান করেন, যা কোনও ধ্রুবক ε> 0 এর জন্য 2^{O((log w)1/2 − ε)} সময়ে সেটকে বিন্যস্ত করে। Kirkpatrick and ড়েইসছ এর এলগরিদমে, তারা একটি যথার্থ b এর জন্য,কী গুলোকে b-ভিত্তিক সংখ্যা ধরে পরিসর হ্রাস করেন। তাদের পরিসর হ্রাসকরণ এলগরিদম প্রত্যেকটি অঙ্ককে O(log n) বিটের একটি হ্যাশ মান (স্বাক্ষর) দ্বারা প্রতিস্থাপন করেন, যেন প্রত্যেক অঙ্কের জন্য স্বাক্ষরগুলো ভিন্ন ভিন্ন হয়।যদি n যথেষ্ট ছোট হয়, এই প্রতিস্থাপন প্রক্রিয়া দ্বারা প্রাপ্ত সংখ্যাগুলো মূল কী গুলোর চেয়েও ব্যাপক ক্ষুদ্র হবে। প্রতিস্থাপিত বিন্যস্ত সংখ্যাগুলোর তালিকা থেকে রৈখিক সময়ে কি গুলোর একটি কম্প্রেসড ট্রাই গঠন করা সম্ভব যার অধস্তন প্রতিটি নোড শুধুমাত্র b আকারের কী দ্বারা পৌনঃপুনিক ভাবে বিন্যস্ত করা যাবে। অবশেষে ট্রি ট্রাভার্স উপাদানগুলোকে বিন্যস্ত করবে।

বৈপরীত্যন্তর অ্যালগরিদম

Fredman & Willard (1993) বিশ্লেষণ এর বৈপরীত্যান্তর মডেল উপস্থাপন করেন , যাতে পূর্ণ সংখ্যা কী গুলোর পরিসরের ব্যাপারে কোন রূপ পূর্বজ্ঞান থাকে না এবং শুধুমাত্র উপাত্তের সংখ্যার ভিত্তিতে অ্যালগরিদমের পারফরম্যান্স বিচার করা হয়। অন্যভাবে বলা যায়, এই মডেলে n সংখ্যক উপাদান বিশিষ্ট কোন সেটে অ্যালগোরিদমের প্রযুক্ত সময় K এবং  w এর মানের যেকোনো সমাবেশের জন্য প্রতিকূল হবে। Fredman and Willard's fusion tree এর সর্টিং অ্যালগরিদম টি ছিল এই ধরনের প্রথম অ্যালগরিদম, যার সময় সীমা ছিল O(n log n / log log n); যেকোনো K এবং  w এর জন্য এটি তুলনামূলকভাবে তুলনামূলক বিন্যস্তকরণ অ্যালগরিদম হতে উন্নত।তাদের অ্যালগোরিদমের বিকল্প সংস্করণ যাতে [[দৈব নির্বাচন|দৈব সংখ্যাল্ল এবং পূর্ণসংখ্যার ভাগ অপারেশন বিদ্যমান, একে O(n√log n) তে উন্নীত করে।

তাদের কাজের পরে, এমনকি আরো উন্নত অ্যালগরিদম আবিষ্কৃত হয়েছে। উদাহরণস্বরূপ, পৌনঃপুনিক ভাবে Albers–Hagerup বিন্যস্ত করার অ্যালগরিদম প্রযুক্ত না হয় ততক্ষণ পর্যন্ত–Reisch পরিসর হ্রাসকরণ পদ্ধতি ব্যবহারের মাধ্যমে O(n log log n) সময়ে বিন্যস্তকরণ সম্ভব; তবে, এই অ্যালগোরিদমের পরিসর হ্রাসকরণ অংশটুকু হয় প্রচুর মেমোরি (√K এর সমানুপাতে) অথবা হ্যাশ টেবিল গঠনের প্রয়োজন পড়ে।

Han & Thorup (2002) দেখান যে, কীভাবে O(n√log log n) সময়ে বিন্যস্ত করতে হয়। তাদের পদ্ধতিটি স্বাক্ষর বিন্যস্তকরণ পদ্ধতির অনুরূপ ধারণা বহন করে, যেখানে উপাত্ত গুলোকে বিভিন্ন ছোট উপতালিকায় বিভক্ত করা হয়, যেন বিন্যস্ত করার অ্যালগরিদম দক্ষভাবে কাজ করে। একই ধরনের ধারণা প্রয়োগ করে পূর্ণসংখ্যাকে O(n log log n) সময়ে এবং রৈখিক ক্ষেত্রে বিন্যস্ত করা সম্ভব। শুধুমাত্র সরল পাটিগণিত অপারেশন ব্যবহার করে (কোন গুণন কিংবা তালিকা অনুসন্ধান ব্যতিরেকে) প্রত্যাশিত O(n log log n) সময়ে অথবা বিভেদ পদ্ধতিতে O(n (log log n)^{1 + ε}) সময়ে বিন্যস্ত করা সম্ভব, যেখানে ε > 0 যেকোনো একটি ধ্রুবক।

তথ্যসূত্র

মাধ্যমিক উৎস

• Chowdhury, Rezaul A. (২০০৮), "Equivalence between priority queues and sorting", Kao, Ming-Yang, Encyclopedia of Algorithms, Springer, পৃষ্ঠা 278–281, আইএসবিএন 9780387307701 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (২০০১), Introduction to Algorithms (2nd সংস্করণ), MIT Press and McGraw-Hill, আইএসবিএন 0-262-03293-7 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Goodrich, Michael T.; Tamassia, Roberto (২০০২), "4.5 Bucket-Sort and Radix-Sort", Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, পৃষ্ঠা 241–243 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .

প্রাথমিক উৎস

• Ajtai, M.; Fredman, M.; Komlós, J. (১৯৮৪), "Hash functions for priority queues", Information and Control, 63 (3): 217–225, এমআর 0837087, ডিওআই:10.1016/S0019-9958(84)80015-7 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Albers, Susanne; Hagerup, Torben (১৯৯৭), "Improved parallel integer sorting without concurrent writing", Information and Computation, 136 (1): 25–51, এমআর 1457693, ডিওআই:10.1006/inco.1997.2632 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Andersson, Arne; Hagerup, Torben; Nilsson, Stefan; Raman, Rajeev (১৯৯৮), "Sorting in linear time?", Journal of Computer and System Sciences, 57 (1): 74–93, এমআর 1649809, ডিওআই:10.1006/jcss.1998.1580 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Andersson, Arne; Nilsson, Stefan (১৯৯৮), "Implementing radixsort", ACM Journal of Experimental Algorithmics, 3, এমআর 1717389, ডিওআই:10.1145/297096.297136 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Andersson, Arne; Miltersen, Peter Bro; Thorup, Mikkel (১৯৯৯), "Fusion trees can be implemented with AC⁰ instructions only", Theoretical Computer Science, 215 (1-2): 337–344, এমআর 1678804, ডিওআই:10.1016/S0304-3975(98)00172-8 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Bhatt, P. C. P.; Diks, K.; Hagerup, T.; Prasad, V. C.; Radzik, T.; Saxena, S. (১৯৯১), "Improved deterministic parallel integer sorting", Information and Computation, 94 (1): 29–47, এমআর 1123154, ডিওআই:10.1016/0890-5401(91)90031-V উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Cole, R.; Vishkin, U. (১৯৮৬), "Deterministic coin tossing with applications to optimal parallel list ranking", Information and Control, 70 (1): 32–53, ডিওআই:10.1016/S0019-9958(86)80023-7 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Comrie, L. J. (১৯২৯–১৯৩০), "The Hollerith and Powers tabulating machines", Trans. Office Mach. Users’ Assoc., Ltd.: 25–37 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) . Cited by Thorup (2007) as an early source for radix sort.
• Fredman, Michael L.; Willard, Dan E. (১৯৯৩), "Surpassing the information-theoretic bound with fusion trees", Journal of Computer and System Sciences, 47 (3): 424–436, এমআর 1248864, ডিওআই:10.1016/0022-0000(93)90040-4 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Fredman, Michael L.; Willard, Dan E. (১৯৯৪), "Trans-dichotomous algorithms for minimum spanning trees and shortest paths", Journal of Computer and System Sciences, 48 (3): 533–551, এমআর 1279413, ডিওআই:10.1016/S0022-0000(05)80064-9 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Hagerup, Torben (১৯৮৭), "Towards optimal parallel bucket sorting", Information and Computation, 75 (1): 39–51, এমআর 0910976, ডিওআই:10.1016/0890-5401(87)90062-9 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Han, Yijie (২০০৪), "Deterministic sorting in O(n log log n) time and linear space", Journal of Algorithms, 50 (1): 96–105, এমআর 2028585, ডিওআই:10.1016/j.jalgor.2003.09.001 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Han, Yijie; Thorup, M. (২০০২), "Integer sorting in O(n√log log n) expected time and linear space", Proceedings of the 43rd Annual Symposium on Foundations of Computer Science (FOCS 2002), IEEE Computer Society, পৃষ্ঠা 135–144, ডিওআই:10.1109/SFCS.2002.1181890 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Kirkpatrick, David; Reisch, Stefan (১৯৮৪), "Upper bounds for sorting integers on random access machines", Theoretical Computer Science, 28 (3): 263–276, এমআর 0742289, ডিওআই:10.1016/0304-3975(83)90023-3 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• McIlroy, Peter M.; Bostic, Keith; McIlroy, M. Douglas (১৯৯৩), "Engineering Radix Sort" (পিডিএফ), Computing Systems, 6 (1): 5–27 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Pedersen, Morten Nicolaj (১৯৯৯), A study of the practical significance of word RAM algorithms for internal integer sorting, Masters thesis, Department of Computer Science, University of Copenhagen, Denmark, ১৬ মার্চ ২০১২ তারিখে মূল থেকে আর্কাইভ করা, সংগ্রহের তারিখ ১১ জুলাই ২০১৯ উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Rahman, Naila; Raman, Rajeev (১৯৯৮), "An experimental study of word-level parallelism in some sorting algorithms", Algorithm Engineering, 2nd International Workshop, WAE '92, Saarbrücken, Germany, August 20–22, 1998, Proceedings (পিডিএফ), Max Planck Institute for Computer Science, পৃষ্ঠা 193–203 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Reif, John H. (১৯৮৫), "An optimal parallel algorithm for integer sorting", Proceedings of the 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), IEEE Computer Society, পৃষ্ঠা 496–504, ডিওআই:10.1109/SFCS.1985.9 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Thorup, Mikkel (২০০২), "Randomized sorting in O(n log log n) time and linear space using addition, shift, and bit-wise Boolean operations", Journal of Algorithms, 42 (2): 205–230, এমআর 1895974, ডিওআই:10.1006/jagm.2002.1211 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Thorup, Mikkel (২০০৩), "On AC⁰ implementations of fusion trees and atomic heaps", Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, MD, 2003), New York: ACM, পৃষ্ঠা 699–707, এমআর 1974982 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Thorup, Mikkel (২০০৭), "Equivalence between priority queues and sorting", Journal of the ACM, 54 (6): Art. 28, এমআর 2374029, ডিওআই:10.1145/1314690.1314692 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .
• Willard, Dan E. (১৯৮৩), "Log-logarithmic worst-case range queries are possible in space Θ(N)", Information Processing Letters, 17 (2): 81–84, এমআর 0731126, ডিওআই:10.1016/0020-0190(83)90075-3 উদ্ধৃতি টেমপ্লেট ইংরেজি প্যারামিটার ব্যবহার করেছে (link) .