Parallel Sorting Algorithms (Parallel Sorting Algorithms) গাইড ও নোট

Parallel Sorting Algorithms

Parallel Sorting Algorithms হল এমন অ্যালগরিদম যা একাধিক প্রসেসর বা কম্পিউটিং ইউনিট ব্যবহার করে একটি তালিকা বা অ্যারে কে দ্রুত সজ্জিত করতে সক্ষম। এই ধরনের অ্যালগরিদমগুলোর উদ্দেশ্য হলো সজ্জা প্রক্রিয়াকে দ্রুততর করা, বিশেষ করে যখন বড় ডেটাসেট নিয়ে কাজ করা হয়। নিচে Parallel Sorting Algorithms এর কিছু জনপ্রিয় এবং কার্যকরী পদ্ধতি আলোচনা করা হলো:

১. Parallel Merge Sort

বর্ণনা:
Parallel Merge Sort হলো Merge Sort এর একটি পরিবর্ধিত সংস্করণ, যেখানে সমান্তরালভাবে ভাগ করা হয় এবং পৃথক অংশগুলোর ওপর একসাথে কাজ করা হয়। এই অ্যালগরিদমটি ডেটাকে দুই অংশে বিভক্ত করে এবং প্রতিটি অংশকে সমান্তরালে সাজিয়ে পরে তাদের একত্রিত করে।

পদ্ধতি:

• প্রথমে তালিকাটি দুইটি সমান অংশে ভাগ করুন।
• প্রতিটি অংশকে আলাদাভাবে Parallel Merge Sort ব্যবহার করে সাজান।
• সাজানো অংশগুলোকে একত্রিত করুন (Merge)।

গতি:
\[ O(n \log p) \] (যেখানে \(p\) হলো প্রসেসরের সংখ্যা)

২. Parallel Quick Sort

বর্ণনা:
Parallel Quick Sort হলো Quick Sort অ্যালগরিদমের সমান্তরাল সংস্করণ। এখানে পিভট নির্বাচন করে ডেটাকে ভাগ করা হয় এবং পৃথক সেগমেন্টগুলোর জন্য Quick Sort প্রয়োগ করা হয়।

পদ্ধতি:

• পিভট নির্বাচন করুন এবং তালিকাটিকে দুই ভাগে ভাগ করুন: পিভটের থেকে ছোট এবং বড়।
• প্রতিটি ভাগের জন্য আলাদাভাবে Parallel Quick Sort প্রয়োগ করুন।
• পিভটের সাথে দুই ভাগের সজ্জিত অংশগুলোকে একত্রিত করুন।

গতি:
\[ O(n \log n) \] (সর্বাধিক ক্ষেত্রে), তবে এটি প্রসেসরের সংখ্যা দ্বারা দ্রুততর হয়।

৩. Bitonic Sort

বর্ণনা:
Bitonic Sort একটি সমান্তরাল অ্যালগরিদম, যা সমান্তরাল Sorting Network এর ভিত্তিতে কাজ করে। এটি একটি Bitonic সিকোয়েন্স তৈরি করে এবং পরে সেগুলোকে সজ্জিত করে।

পদ্ধতি:

• তালিকাকে Bitonic সিকোয়েন্সে পরিণত করুন।
• Bitonic Merge ব্যবহার করে সজ্জিত করুন।

গতি:
\[ O(\log^2 n) \]

৪. Sample Sort

বর্ণনা:
Sample Sort একটি সমান্তরাল অ্যালগরিদম যা নমুনা ব্যবহার করে বিভাজন করে Sorting প্রক্রিয়া সম্পন্ন করে। এটি বড় ডেটাসেটের জন্য কার্যকর এবং একাধিক প্রসেসরের সাথে ব্যবহার করা হয়।

পদ্ধতি:

• একটি নমুনা নির্বাচন করুন এবং তা থেকে ডেটাকে ভাগ করুন।
• প্রতিটি ভাগের জন্য সজ্জিত করুন (প্রত্যেকটি অংশে আলাদাভাবে Sorting প্রয়োগ করুন)।
• সজ্জিত অংশগুলোকে একত্রিত করুন।

গতি:
\[ O(n) \]

৫. Radix Sort

বর্ণনা:
Radix Sort একটি Counting Sort-এর ভিত্তিতে কাজ করে এবং সংখ্যাগুলিকে ডিজিট অনুযায়ী সাজিয়ে দেয়। এটি সহজে Parallel করা যায়, কারণ প্রতিটি ডিজিটের জন্য আলাদাভাবে কাজ করা সম্ভব।

পদ্ধতি:

• সর্বাধিক ডিজিট সংখ্যা নির্ধারণ করুন।
• প্রতিটি ডিজিটের জন্য Counting Sort প্রয়োগ করুন।

গতি:
\[ O(d(n + k)) \] (যেখানে \(d\) হলো ডিজিট সংখ্যা এবং \(k\) হলো সংখ্যা পরিসীমা)

সারসংক্ষেপ

Parallel Sorting Algorithms বড় আকারের ডেটাসেট দ্রুত এবং কার্যকরভাবে সাজানোর জন্য বিভিন্ন পদ্ধতি ব্যবহার করে। Parallel Merge Sort, Parallel Quick Sort, Bitonic Sort, Sample Sort, এবং Radix Sort এই অ্যালগরিদমগুলোর মধ্যে অন্তর্ভুক্ত। প্রতিটি অ্যালগরিদমের নিজস্ব কার্যকারিতা এবং গতি রয়েছে, যা বিভিন্ন প্রয়োগ ক্ষেত্রে তাদের কার্যক্ষমতা বাড়ায়। Parallel Sorting Algorithms এর ব্যবহার, বিশেষ করে উচ্চ কার্যক্ষমতা সম্পন্ন কম্পিউটিং এবং বিশাল ডেটাসেট বিশ্লেষণে, অত্যন্ত গুরুত্বপূর্ণ।

Parallel Merge Sort

Parallel Merge Sort একটি উন্নত প্যারালাল অ্যালগরিদম যা ডেটাকে দ্রুত এবং কার্যকরভাবে সজ্জিত করতে ব্যবহৃত হয়। এটি ঐতিহ্যবাহী Merge Sort অ্যালগরিদমের একটি উন্নত সংস্করণ, যেখানে ডেটার বিভিন্ন অংশ সমান্তরালে প্রক্রিয়া করা হয়। এই পদ্ধতি বড় ডেটাসেটকে দ্রুত সজ্জিত করতে কার্যকরী।

১. Merge Sort এর সংক্ষিপ্ত বিবরণ

Merge Sort একটি ডিভাইড-এন্ড-কনকার অ্যালগরিদম যা একটি ডেটাসেটকে পুনরাবৃত্তিমূলকভাবে দুইটি অংশে ভাগ করে এবং পরে সেগুলোকে একত্রিত করে সজ্জিত করে। এর প্রক্রিয়া নিম্নরূপ:

1. বিভাজন: তালিকাটি দুইটি সমান বা প্রায় সমান ভাগে বিভক্ত করা হয় যতক্ষণ না প্রতিটি অংশে একটি মাত্র উপাদান থাকে।
2. মার্জিং: দুটি সজ্জিত তালিকাকে একত্রিত করে একটি নতুন সজ্জিত তালিকা তৈরি করা হয়।

২. Parallel Merge Sort এর ধারণা

Parallel Merge Sort প্রক্রিয়াটি মূলত Merge Sort এর ভিত্তিতে তৈরি করা হয়েছে, তবে এটি একাধিক প্রসেসরের সুবিধা গ্রহণ করে ডেটা শেয়ারিং এবং সমান্তরালে কাজ সম্পন্ন করে।

ধাপগুলো:

1. বিভাজন:
   • পুরো তালিকাটি দুইটি অংশে ভাগ করা হয়।
   • প্রতিটি অংশকে আলাদাভাবে পৃথক প্রসেসরে সজ্জিত করার জন্য পাঠানো হয়।
2. প্যারালাল সজ্জা:
   • প্রতিটি প্রসেসর আলাদাভাবে Merge Sort অ্যালগরিদম প্রয়োগ করে তাদের নিজস্ব অংশ সজ্জিত করে।
   • প্রতিটি অংশ দ্রুত সজ্জিত হয়।
3. মার্জিং:
   • সমস্ত সজ্জিত অংশগুলোকে একত্রিত করা হয়।
   • মার্জিং প্রক্রিয়াটিও সমান্তরালে করা যেতে পারে, যেখানে একাধিক প্রসেসর সজ্জিত অংশগুলোকে একত্রিত করে।

৩. Parallel Merge Sort এর সুবিধা

• দ্রুতগতি: Parallel Merge Sort প্যারালাল প্রসেসিংয়ের মাধ্যমে সজ্জার সময় উল্লেখযোগ্যভাবে সাশ্রয় করে, বিশেষ করে বৃহৎ ডেটাসেটের ক্ষেত্রে।
• স্কেলেবিলিটি: নতুন প্রসেসর যুক্ত করার মাধ্যমে কর্মক্ষমতা বৃদ্ধি করা সম্ভব।
• কার্যকরী ব্যবহার: বড় ডেটাসেট এবং তথ্যের জন্য কার্যকর, যেমন ডাটাবেসের তথ্য, গ্রাফিক্স ডেটা, ইত্যাদি।

৪. উদাহরণ

ধরা যাক আমাদের একটি তালিকা আছে: [38, 27, 43, 3, 9, 82, 10]। Parallel Merge Sort এর প্রক্রিয়া:

1. বিভাজন:
   • [38, 27, 43] এবং [3, 9, 82, 10] এ বিভক্ত হয়।
2. প্যারালাল সজ্জা:
   • প্রথম অংশ [38, 27, 43] কে প্রসেসর 1 এ এবং দ্বিতীয় অংশ [3, 9, 82, 10] কে প্রসেসর 2 এ পাঠানো হয়।
   • প্রতিটি প্রসেসর তাদের নিজস্ব অংশ সজ্জিত করে:
     • প্রসেসর 1: [27, 38, 43]
     • প্রসেসর 2: [3, 9, 10, 82]
3. মার্জিং:
   • দুইটি সজ্জিত অংশকে একত্রিত করা হয়:
   • মার্জিং ফলাফল: [3, 9, 10, 27, 38, 43, 82]

৫. চ্যালেঞ্জ

• সিঙ্ক্রোনাইজেশন: একাধিক প্রসেসরের মধ্যে সঠিক সিঙ্ক্রোনাইজেশন নিশ্চিত করা কঠিন হতে পারে, বিশেষ করে মার্জিং প্রক্রিয়ার সময়।
• ডেটা রেস: একাধিক প্রসেসরের একই ডেটা অ্যাক্সেস করার সময় ডেটা রেস সমস্যা দেখা দিতে পারে।

সারসংক্ষেপ

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

Parallel Quick Sort

Parallel Quick Sort একটি উন্নত এলগরিদম যা ক্লাসিকাল Quick Sort অ্যালগরিদমের কার্যকারিতা বৃদ্ধি করার জন্য সমান্তরাল প্রসেসিং ব্যবহার করে। এটি বড় ডেটাসেট দ্রুত সজ্জিত করতে সক্ষম এবং মাল্টিপ্রসেসিং বা মাল্টিকোর সিস্টেমে কার্যকরীভাবে কাজ করে। এই অ্যালগরিদমটি ডেটাকে বিভিন্ন অংশে ভাগ করে সমান্তরালে সজ্জিত করে, যার ফলে কার্যক্ষমতা এবং গতি বৃদ্ধি পায়।

Parallel Quick Sort এর ধারণা

Parallel Quick Sort সাধারণ Quick Sort এর মতো কাজ করে, কিন্তু এটি ডেটাকে বিভিন্ন অংশে ভাগ করে এবং প্রতিটি অংশের জন্য আলাদাভাবে Quick Sort প্রয়োগ করে। এর মূল পদক্ষেপগুলি নিম্নরূপ:

1. Pivot নির্বাচন: প্রথমে একটি পিভট নির্বাচন করা হয়, যা ডেটাসেটটিকে ভাগ করতে সাহায্য করবে। সাধারণত, প্রথম, শেষ, বা মাঝের উপাদানকে পিভট হিসেবে ব্যবহার করা হয়।
2. Partitioning: ডেটাসেটটিকে পিভটের ভিত্তিতে দুইটি অংশে ভাগ করা হয়: একদিকে পিভটের চেয়ে ছোট উপাদান এবং অন্যদিকে পিভটের চেয়ে বড় উপাদান।
3. Recursive Sort: প্রতিটি ভাগের উপর পুনরাবৃত্তি করা হয়, কিন্তু এখানে গুরুত্বপূর্ণ পার্থক্য হলো প্রতিটি ভাগকে আলাদাভাবে সমান্তরালভাবে সজ্জিত করা হয়।
4. Merge: বিভাজনের পর, সমস্ত ভাগ একত্রিত করে চূড়ান্ত সজ্জিত ডেটাসেট তৈরি করা হয়।

Parallel Quick Sort এর প্রয়োগ

Parallel Quick Sort বিশেষ করে বড় ডেটাসেটের জন্য কার্যকরী। এটি সাধারণত নিম্নলিখিত ক্ষেত্রে ব্যবহৃত হয়:

• ডেটাবেস সজ্জা: বড় ডেটাবেসের রেকর্ড সজ্জিত করার জন্য।
• বিজ্ঞান ও প্রকৌশল গবেষণা: গবেষণা ডেটার বিশ্লেষণ এবং সজ্জা।
• মেশিন লার্নিং: প্রশিক্ষণের জন্য বড় ডেটাসেট সজ্জিত করা।

Parallel Quick Sort এর উদাহরণ (Pseudocode)

Parallel Quick Sort এর একটি সাধারিত pseudocode নিম্নরূপ:

function parallelQuickSort(array A, int low, int high):
    if low < high:
        pivotIndex = partition(A, low, high)
        
        // Create tasks for the left and right partitions
        parallel:
            parallelQuickSort(A, low, pivotIndex - 1)  // Left partition
            parallelQuickSort(A, pivotIndex + 1, high) // Right partition

Partition Function

Partition ফাংশনটি ডেটাসেটটিকে পিভটের ভিত্তিতে বিভক্ত করে:

function partition(array A, int low, int high):
    pivot = A[high] // Choose the last element as pivot
    i = low - 1
    for j from low to high - 1:
        if A[j] < pivot:
            i = i + 1
            swap A[i] with A[j]
    swap A[i + 1] with A[high]
    return i + 1

Parallel Quick Sort এর সুবিধা

1. দ্রুততা: Parallel Quick Sort সাধারণ Quick Sort এর তুলনায় দ্রুত কাজ করে, বিশেষ করে বড় ডেটাসেটের ক্ষেত্রে।
2. দক্ষতা: এটি মাল্টিকোর প্রসেসর বা ক্লাস্টার কম্পিউটিং সিস্টেমে উচ্চ কার্যক্ষমতা প্রদান করে।
3. সম্পদ ব্যবস্থাপনা: একাধিক প্রসেসর ব্যবহারের ফলে সম্পদের সর্বাধিক ব্যবহার করা সম্ভব হয়।

চ্যালেঞ্জ

1. সিঙ্ক্রোনাইজেশন: একাধিক প্রসেসর সমান্তরালে কাজ করার সময় সঠিক সিঙ্ক্রোনাইজেশন নিশ্চিত করা গুরুত্বপূর্ণ।
2. ডেটা রেস: একই সময়ে ডেটায় কাজ করার সময় ডেটা রেসের সমস্যা হতে পারে, যা ফলাফলকে প্রভাবিত করতে পারে।
3. কমিউনিকেশন ল্যাটেন্সি: প্রসেসরগুলোর মধ্যে যোগাযোগের সময় যদি বেশি হয় তবে এটি পারফরম্যান্সে নেতিবাচক প্রভাব ফেলতে পারে।

সারসংক্ষেপ

Parallel Quick Sort একটি শক্তিশালী এবং কার্যকরী প্যারালাল সজ্জিত অ্যালগরিদম, যা দ্রুত এবং দক্ষতার সাথে বড় ডেটাসেট সজ্জিত করতে সক্ষম। এটি মাল্টিকোর প্রসেসিং ক্ষমতা ব্যবহার করে এবং বিভিন্ন ক্ষেত্রে কার্যকরী, যেমন ডেটাবেস সজ্জা, বিজ্ঞান ও প্রকৌশল গবেষণা, এবং মেশিন লার্নিং। তবে, সঠিক সিঙ্ক্রোনাইজেশন এবং যোগাযোগ ব্যবস্থাপনা নিশ্চিত করা গুরুত্বপূর্ণ যাতে অ্যালগরিদমটি কার্যকরভাবে কাজ করতে পারে।

Bitonic Sort

Bitonic Sort একটি প্যারালাল সার্টিং অ্যালগরিদম যা মূলত প্যারালাল কম্পিউটিংয়ে ব্যবহৃত হয়। এটি একটি বিশেষ ধরনের সার্টিং অ্যালগরিদম যা বিটোনিক সিকোয়েন্সের উপর ভিত্তি করে তৈরি। বিটোনিক সিকোয়েন্স হল এমন একটি সিকোয়েন্স যা কিছু উপাদান বাড়তে বাড়তে এবং পরে কমতে কমতে থাকে।

Bitonic Sort সাধারণত উচ্চ কার্যক্ষমতা সম্পন্ন কম্পিউটার আর্কিটেকচারে কার্যকর, যেখানে একাধিক প্রসেসর সমান্তরালে কাজ করতে পারে।

Bitonic Sort এর কাজের পদ্ধতি

Bitonic Sort এর মূল কাজের প্রক্রিয়া দুইটি প্রধান ধাপে বিভক্ত:

1. বিটোনিক সিকোয়েন্স তৈরি:
   • প্রথমে একটি বিটোনিক সিকোয়েন্স তৈরি করা হয়। বিটোনিক সিকোয়েন্সে উপাদানগুলির একটি অংশ বৃদ্ধি পায় এবং পরবর্তী অংশ হ্রাস পায়।
   • উদাহরণস্বরূপ, একটি বিটোনিক সিকোয়েন্স হতে পারে: [1, 3, 5, 4, 2].
2. বিটোনিক মার্জ (Bitonic Merge):
   • বিটোনিক সিকোয়েন্স তৈরি করার পরে, এই সিকোয়েন্সকে সাজানো হয়। এটি Bitonic Merge অপারেশন দ্বারা করা হয়।
   • Bitonic Merge একটি রিকার্সিভ ফাংশন, যা সিকোয়েন্সের উপাদানগুলোকে বিভিন্ন জোড়ে ভাগ করে সঠিকভাবে সাজায়।
   • দুটি বিটোনিক সিকোয়েন্সকে একত্র করে একটি Sorted Sequence তৈরি করা হয়।

কাজের পদ্ধতি উদাহরণ

ধরা যাক, আমাদের একটি অ্যারে [3, 7, 2, 5, 8, 1, 4, 6] সাজাতে হবে।

1. বিটোনিক সিকোয়েন্স তৈরি:
   • প্রথমে আমরা একটি বিটোনিক সিকোয়েন্স তৈরি করব। উদাহরণস্বরূপ, [3, 7, 2, 5] এবং [8, 1, 4, 6]।
2. Bitonic Merge:
   • প্রথম সিকোয়েন্সে Bitonic Merge অপারেশন প্রয়োগ:
     • [3, 7, 2, 5] থেকে 3 এবং 2 এর মধ্যে তুলনা করে স্থান পরিবর্তন করব => [2, 7, 3, 5]।
     • তারপর 7 এবং 5 এর মধ্যে তুলনা করব => [2, 5, 3, 7]।
   • দ্বিতীয় সিকোয়েন্সে Bitonic Merge অপারেশন প্রয়োগ:
     • [8, 1, 4, 6] থেকে 8 এবং 4 এর মধ্যে তুলনা => [4, 1, 8, 6]।
     • 1 এবং 6 এর মধ্যে তুলনা => [4, 1, 6, 8]।
3. শেষ মার্জ:
   • এখন আমরা দুইটি বিটোনিক সিকোয়েন্স মার্জ করব:
     • [2, 5, 3, 7] এবং [4, 1, 6, 8] একত্র করে একটি সম্পূর্ণ সাজানো অ্যারে তৈরি করব।

সময় জটিলতা

Bitonic Sort এর সময় জটিলতা O(log² n), যেখানে n হলো অ্যারের আকার। এটি Pipelining এবং Parallel Processing এ কার্যকর।

Bitonic Sort এর সুবিধা ও অসুবিধা

সুবিধা:

• প্যারালাল প্রসেসিং: Bitonic Sort অনেক প্রসেসরের সাথে কাজ করতে পারে, যা উচ্চ কার্যক্ষমতা নিশ্চিত করে।
• বৃহৎ ডেটাসেট: এটি বড় ডেটাসেটের জন্য কার্যকরী এবং দ্রুত।

অসুবিধা:

• সামান্য মেমরি ব্যবহার: এটি কিছু অতিরিক্ত মেমরি ব্যবহার করতে পারে, যা ছোট সিস্টেমে সমস্যা সৃষ্টি করতে পারে।
• সময় জটিলতা: অন্যান্য অ্যালগরিদমের তুলনায় সময় জটিলতা কিছুটা বেশি।

সারসংক্ষেপ

Bitonic Sort হল একটি প্যারালাল সার্টিং অ্যালগরিদম যা বিটোনিক সিকোয়েন্সের উপর ভিত্তি করে কাজ করে। এটি সমান্তরালে কাজ করার জন্য ডিজাইন করা হয়েছে এবং বড় আকারের ডেটাসেটের দ্রুত সমাধানে কার্যকর। যদিও এটি কিছু অতিরিক্ত মেমরি ব্যবহার করতে পারে এবং সময় জটিলতা O(log² n), তবে প্যারালাল কম্পিউটিংয়ে এর ব্যবহার উল্লেখযোগ্য।

Odd-Even Transposition Sort

Odd-Even Transposition Sort হল একটি সোজা প্যারালাল সার্টিং অ্যালগরিদম যা সমান্তরালভাবে কাজ করে। এটি এক ধরনের বুদ্বুদ সাজানোর অ্যালগরিদমের উপর ভিত্তি করে তৈরি এবং এটি প্যারালাল প্রসেসিংয়ের জন্য উপযুক্ত। এই অ্যালগরিদমের মূল উদ্দেশ্য হলো একটি অ্যালগরিদমের সাহায্যে একটি অ্যারের উপাদানগুলোকে সঠিকভাবে সাজানো।

কাজের পদ্ধতি

Odd-Even Transposition Sort কাজ করে দুটি পর্যায়ে:

1. Odd Phase: এই পর্যায়ে, প্রতিটি অপরিবর্তনীয় পার্শ্ববর্তী উপাদানগুলি একে অপরের তুলনায় স্থান পরিবর্তন করে। অর্থাৎ, প্রতিটি অদ্ভুত অবস্থানে থাকা উপাদান এবং তার পরবর্তী যোজক উপাদানগুলির মধ্যে তুলনা করা হয় এবং প্রয়োজন হলে তাদের স্থান পরিবর্তন করা হয়।
2. Even Phase: এই পর্যায়ে, প্রতিটি জোড় অবস্থানে থাকা উপাদান এবং তার পরবর্তী অবস্থানের উপাদানগুলির মধ্যে তুলনা করা হয় এবং প্রয়োজন হলে তাদের স্থান পরিবর্তন করা হয়।

এই দুটি পর্যায় বারবার চলতে থাকে যতক্ষণ না পুরো অ্যারেটি সাজানো হয়।

অ্যালগরিদমের পদক্ষেপ

Odd-Even Transposition Sort এর প্রক্রিয়া নিম্নরূপ:

1. অ্যারেটির দৈর্ঘ্য n ধরুন।
2. Odd Phase সম্পাদন করুন:
   • i = 1 থেকে n-1 (একটির সময়)
   • যদি A[i] > A[i+1] হয়, তাহলে A[i] এবং A[i+1] এর মানগুলি পরিবর্তন করুন।
3. Even Phase সম্পাদন করুন:
   • i = 0 থেকে n-2 (একটির সময়)
   • যদি A[i] > A[i+1] হয়, তাহলে A[i] এবং A[i+1] এর মানগুলি পরিবর্তন করুন।
4. উপরের দুটি ধাপ পুনরাবৃত্তি করুন যতক্ষণ না আর কোনও পরিবর্তন না হয়।

উদাহরণ

ধরা যাক, আমাদের অ্যারেটি [34, 23, 45, 12, 5] সাজানো দরকার।

1. Odd Phase:
   • 34 এবং 23 তুলনা: পরিবর্তন => [23, 34, 45, 12, 5]
   • 34 এবং 45 তুলনা: কোনও পরিবর্তন নেই।
   • 45 এবং 12 তুলনা: পরিবর্তন => [23, 34, 12, 45, 5]
   • 45 এবং 5 তুলনা: পরিবর্তন => [23, 34, 12, 5, 45]
2. Even Phase:
   • 23 এবং 34 তুলনা: কোনও পরিবর্তন নেই।
   • 34 এবং 12 তুলনা: পরিবর্তন => [23, 12, 34, 5, 45]
   • 34 এবং 5 তুলনা: পরিবর্তন => [23, 12, 5, 34, 45]
3. পুনরাবৃত্তি করে, এই প্রক্রিয়া চলতে থাকে যতক্ষণ না অ্যারেটি সম্পূর্ণরূপে সাজানো হয়।

সময় জটিলতা

Odd-Even Transposition Sort এর সময় জটিলতা O(n^2) যেখানে n অ্যারের আকার। তবে, এটি একটি সহজ ও সরল অ্যালগরিদম যা বিশেষ করে প্যারালাল পরিবেশে কার্যকরী।

সারসংক্ষেপ

Odd-Even Transposition Sort হল একটি প্যারালাল সার্টিং অ্যালগরিদম যা দুইটি পর্যায়ে কাজ করে—Odd Phase এবং Even Phase। এটি একটি সোজা অ্যালগরিদম, যা দুটি পার্শ্ববর্তী উপাদানগুলির মধ্যে তুলনা করে তাদের স্থান পরিবর্তন করে। যদিও সময় জটিলতা O(n^2) হওয়ায় এটি বড় ডেটাসেটের জন্য সর্বদা কার্যকর নয়, তবে প্যারালাল প্রসেসিংয়ের জন্য এটি একটি সহজ এবং কার্যকরী পদ্ধতি।