Odd-Even Transposition Sort

Computer Science - প্যারালাল অ্যালগরিদম (Parallel Algorithm) Parallel Sorting Algorithms (Parallel Sorting Algorithms) |

122

Odd-Even Transposition Sort

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

কাজের পদ্ধতি

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

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

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

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

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

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

উদাহরণ

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

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]
Even Phase:
- 23 এবং 34 তুলনা: কোনও পরিবর্তন নেই।
- 34 এবং 12 তুলনা: পরিবর্তন => [23, 12, 34, 5, 45]
- 34 এবং 5 তুলনা: পরিবর্তন => [23, 12, 5, 34, 45]
পুনরাবৃত্তি করে, এই প্রক্রিয়া চলতে থাকে যতক্ষণ না অ্যারেটি সম্পূর্ণরূপে সাজানো হয়।

সময় জটিলতা

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

সারসংক্ষেপ

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

Content added By

Md Azizur Rahman

Parallel Merge Sort Parallel Quick Sort Bitonic Sort

Odd-Even Transposition Sort