সর্টিং অ্যালগোরিদম

থাম্ব|সাজানোর অ্যালগরিদম মার্জ করার চিত্র
কম্পিউটার বিজ্ঞানে (ইংরেজি: computer science) **সর্টিং অ্যালগোরিদম** (ইংরেজি: Sorting algorithm) বলতে একটি নির্দিষ্ট ক্রমে সাজানো বা ক্রম অনুযায়ী একটি তালিকা তৈরী করাকে বোঝায়। মূলত সর্টিং দুই প্রকার। একটি বড় থেকে ছোট এবং অপরটি ছোট থেকে বড় ক্রমে সাজানো। সবচেয়ে ব্যবহৃত ক্রম হচ্ছে সংখ্যা (১,২,৩,৪.....) এবং আভিধানিক (ক,খ,গ.....) বা (A,B,C.....) ক্রম।

আনুষ্ঠানিকভাবে, যে কোনও সর্টিং অ্যালগরিদমের আউটপুট দুটি শর্ত পূরণ করতে হবে:

# আউটপুটটি মনোটোনিক ক্রমে রাখতে হবে। (প্রতিটি উপাদান প্রয়োজনীয় ক্রমানুসারে পূর্ববর্তী উপাদানের চেয়ে ছোট/বড় নয়)।
# আউটপুটটি ইনপুটের বিন্যাস হবে (একটি reordering, কিন্তু মূল উপাদান সব বজায় থাকবে)।

যদিও কিছু অ্যালগরিদম ক্রমিক অ্যাক্সেসের জন্য ডিজাইন করা হয়েছে, সর্বোচ্চ-পারফরমিং অ্যালগরিদমগুলি ধরে নেয় যে ডেটা একটি ডেটা স্ট্রাকচারে সংরক্ষণ করা হয় যা র‍্যান্ডম অ্যাক্সেসের অনুমতি দেয়।

## প্রকারভেদ

# উর্ধক্রম (acsending): ছোট থেকে বড় । যেমন :      ১ ,২,৩ ...
# অধঃক্রম (decending):  বড় থেকে ছোট । যেমন :  ... ৩ ,২ ,১

## অ্যালগরিদমের তুলনা
এই বিশ্লেষণে ধরে নেয়া হয়েছে যে প্রতিটি কি-টির দৈর্ঘ্য ধ্রুবক এবং সমস্ত তুলনা, সোয়াপ এবং অন্যান্য অপারেশন ধ্রুবক সময়ে এগিয়ে যেতে পারে।

লেজেন্ড:

* *n* হল সাজানোর জন্য রেকর্ডের সংখ্যা।
* তুলনা কলামে নিম্নলিখিত র‍্যাংকিং শ্রেণীবিভাগে বিভক্ত: "সেরা", "গড়" এবং "সবচেয়ে খারাপ" যদি প্রতিটি ক্ষেত্রে সময় জটিলতা দেওয়া হয়।
* "মেমোরি" দ্বারা অ্যালগরিদম কর্তৃক প্রয়োজনীয় অতিরিক্ত স্টোরেজের পরিমাণ নির্দেশ করে।
* রান টাইম এবং মেমরি প্রয়োজনীয়তা ভিতরে বড় O নোটেশন দ্বারা তালিকাভুক্ত, এজন্য লগারিদমের ভিত্তি কোন বিষয় না।
* এখানে নোটেশন log2 *n* মানে (log *n*)2.

### তুলনা ক্রম
নিম্নলিখিত অংশটি  তুলনার সর্টের একটি টেবিল। গাণিতিক বিশ্লেষণ দেখায় যে একটি তুলনা সর্ট গড়ে *O*(*n* log *n*) এর চেয়ে ভাল কাজ সম্পাদন করতে পারে না।

### Non-comparison sorts
The following table describes integer sorting algorithms and other sorting algorithms that are not comparison sorts. These algorithms are not limited to *Ω*(*n* log *n*) unless meet unit-cost random-access machine model as described below. 

* Complexities below assume *n* items to be sorted, with keys of size *k*, digit size *d*, and *r* the range of numbers to be sorted.
* Many of them are based on the assumption that the key size is large enough that all entries have unique key values, and hence that *n* ≪ 2*k*, where ≪ means "much less than".
* In the unit-cost random-access machine model, algorithms with running time of , such as radix sort, still take time proportional to Θ(*n* log *n*), because *n* is limited to be not more than , and a larger number of elements to sort would require a bigger *k* in order to store them in the memory.

Samplesort can be used to parallelize any of the non-comparison sorts, by efficiently distributing data into several buckets and then passing down sorting to several processors, with no need to merge as buckets are already sorted between each other.

### Others
Some algorithms are slow compared to those discussed above, such as the bogosort with unbounded run time and the stooge sort which has *O*(*n*2.7) run time. These sorts are usually described for educational purposes to demonstrate how the run time of algorithms is estimated. The following table describes some sorting algorithms that are impractical for real-life use in traditional software contexts due to extremely poor performance or specialized hardware requirements.

Theoretical computer scientists have invented other sorting algorithms that provide better than *O*(*n* log *n*) time complexity assuming certain constraints, including:

* Thorup's algorithm, a randomized integer sorting algorithm, taking *O*(*n* log log *n*) time and *O*(*n*) space.
* AHNR algorithm, an integer sorting algorithm which runs in  time deterministically, and also has a randomized version which runs in linear time when words are large enough, specifically  (where *w* is the word size).
* A randomized integer sorting algorithm taking  expected time and *O*(*n*) space.

## তালিকা
# বাবল সর্ট
# হিপ সর্ট
# মার্জ সর্ট
# কুইক সর্ট
# সিলেকশন সর্ট
# ইনসার্শন সর্ট
# কিউব সর্ট
# শেল সর্ট
# বাইনারি ট্রি সর্ট
# কম্ব সর্ট
# কাউন্টিং সর্ট
# বাকেট সর্ট
# রেডিক্স সর্ট
# জোড়-বিজোড় সর্ট
# ইন্ট্রো সর্ট
# কিউব সর্ট
# টপোলজিকাল সর্ট
# কোয়ান্টাম সর্ট

বিষয়শ্রেণী:সর্টিং অ্যালগোরিদম
বিষয়শ্রেণী:অসম্পূর্ণ
বিষয়শ্রেণী:উপাত্ত প্রক্রিয়াজাতকরণ