বাছাই হল একটি মৌলিক ক্রিয়াকলাপ যা আমরা বস্তুতে সম্পাদন করি। এমনকি শৈশবকালে, শিশুদের তাদের চিন্তার দক্ষতা বিকাশের সাথে সাথে সাজাতে শেখানো হয়। কম্পিউটার এবং সফটওয়্যার এর ব্যতিক্রম নয়। জাভাতে বিভিন্ন ধরণের সাজানোর অ্যালগরিদম রয়েছে । আমি আপনাকে সেগুলি কী এবং কীভাবে কাজ করে তা পরীক্ষা করে দেখার পরামর্শ দিচ্ছি। যদি কোন দিন একটি সাক্ষাত্কারে আপনাকে তাদের একজন সম্পর্কে জিজ্ঞাসা করা হয়?
ভূমিকা
অ্যালগরিদমগুলির একটি বিভাগ যা একজন বিকাশকারীকে অবশ্যই জানতে হবে। আমি যখন স্কুলে ছিলাম তখন কম্পিউটার বিজ্ঞানকে একবার গুরুত্বের সাথে না নেওয়া হলে, আজকের ছাত্ররা অবশ্যই সাজানোর অ্যালগরিদমগুলি বাস্তবায়ন করতে এবং বুঝতে সক্ষম হবে। মৌলিক অ্যালগরিদম, সবচেয়ে সহজ, একটি লুপ ব্যবহার করে প্রয়োগ করা হয় । স্বাভাবিকভাবেই, উপাদানগুলির একটি সংগ্রহ বাছাই করার জন্য, যেমন একটি অ্যারের, আপনাকে কোনওভাবে সংগ্রহের মধ্য দিয়ে যেতে হবে। উদাহরণ স্বরূপ:
int[] array = {10, 2, 10, 3, 1, 2, 5};
for (int i = 0; i < array.length; i++) {
System.out.println(array[i]);
}
কোড এই সেগমেন্ট সম্পর্কে কি বলা যেতে পারে? আমাদের একটি লুপ আছে যেখানে আমরা সূচক ( int i) 0 থেকে অ্যারের শেষ উপাদানে পরিবর্তন করি। আসলে, আমরা কেবল অ্যারের প্রতিটি উপাদান নিচ্ছি এবং এর বিষয়বস্তু মুদ্রণ করছি। অ্যারেতে যত বেশি উপাদান থাকবে, কোডটি শেষ হতে তত বেশি সময় লাগবে। অর্থাৎ, যদি nউপাদানের সংখ্যা হয়, কখন n = 10প্রোগ্রামটি রান করতে দ্বিগুণ সময় নেবে কখন থেকে n = 5। যদি আমাদের প্রোগ্রামের একটি একক লুপ থাকে, তাহলে এক্সিকিউশনের সময় রৈখিকভাবে বৃদ্ধি পায়: যত বেশি উপাদান থাকবে, এক্সিকিউশনের সময় তত বেশি হবে। দেখা যাচ্ছে যে উপরের অ্যালগরিদমটি লিনিয়ার টাইমে কাজ করে (n এর লিনিয়ার ফাংশন)। এই ধরনের ক্ষেত্রে, আমরা বলি যে অ্যালগরিদমের জটিলতা হল "O(n)"। এই স্বরলিপিকে "বিগ ও" বা "অ্যাসিম্পোটিক আচরণ"ও বলা হয়। কিন্তু তুমি শুধু মনে রাখতে পারো"
সবচেয়ে সহজ বাছাই অ্যালগরিদম (বাবল বাছাই)
ধরুন আমাদের একটি অ্যারে আছে এবং আমরা এটির মাধ্যমে পুনরাবৃত্তি করতে পারি। দারুণ। এখন এটিকে ক্রমবর্ধমান ক্রমে সাজানোর চেষ্টা করা যাক। এটার মানে কি? এর মানে হল যে দুটি উপাদান দেওয়া হয়েছে (উদাহরণস্বরূপ, a = 6, b = 5), আমাদের অবশ্যই পুনর্বিন্যাস করতে হবে aএবং bযদি (যদি ) aএর থেকে বড় হয় । যখন আমরা একটি সংগ্রহের সাথে কাজ করার জন্য একটি সূচক ব্যবহার করছি (যেমন একটি অ্যারের ক্ষেত্রে) তখন এর অর্থ কী? এর মানে হল যে যদি সূচী a সহ উপাদানটি সূচক ( ) সহ উপাদানটির চেয়ে বড় হয় তবে উপাদানগুলিকে অদলবদল করতে হবে। স্থান পরিবর্তন করার বিভিন্ন উপায় আছে। কিন্তু আমরা এমন একটি কৌশল ব্যবহার করব যা সহজ, বোধগম্য এবং মনে রাখা সহজ: ba > bbarray[a] > array[b]
private void swap(int[] array, int ind1, int ind2) {
int tmp = array[ind1];
array[ind1] = array[ind2];
array[ind2] = tmp;
}
এখন আমরা নিম্নলিখিত লিখতে পারি:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
}
}
System.out.println(Arrays.toString(array));
আপনি দেখতে পাচ্ছেন, উপাদানগুলি সত্যিই অদলবদল করা হয়েছিল। আমরা সূচী 1 দিয়ে শুরু করেছি, কারণ অ্যারেতে যদি শুধুমাত্র একটি উপাদান থাকে তবে অভিব্যক্তিটি array[i] < array[i-1]index এর জন্য অবৈধ 0। এটি করা আমাদেরকে এমন ক্ষেত্রে থেকেও রক্ষা করে যেখানে অ্যারের কোনও উপাদান নেই বা শুধুমাত্র একটি উপাদান নেই এবং এটি কোডটিকে আরও ভাল দেখায়। কিন্তু ফলাফলের অ্যারেটি এখনও সাজানো হয়নি, কারণ বাছাই করার জন্য একটি পাস যথেষ্ট নয়। আমাদের আরেকটি লুপ যোগ করতে হবে যেখানে আমরা একটি সাজানো অ্যারে না পাওয়া পর্যন্ত আমরা বারবার পাস সম্পাদন করব:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
boolean needIteration = true;
while (needIteration) {
needIteration = false;
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i-1);
needIteration = true;
}
}
}
System.out.println(Arrays.toString(array));
তাই আমরা আমাদের প্রথম সাজানোর অ্যালগরিদম শেষ করেছি। আমরা বাইরের লুপ ( while) পুনরাবৃত্তি করি যতক্ষণ না আমরা সিদ্ধান্ত নিই যে আর কোনো পুনরাবৃত্তির প্রয়োজন নেই। ডিফল্টরূপে, প্রতিটি নতুন পুনরাবৃত্তির আগে, আমরা ধরে নিই যে আমাদের অ্যারে সাজানো হয়েছে এবং আমাদের আর লুপ করার দরকার নেই। তদনুসারে, আমরা উপাদানগুলির মাধ্যমে ক্রমানুসারে সরে যাই এবং এই অনুমানটি পরীক্ষা করি। কিন্তু যদি উপাদানগুলি ক্রমানুসারে না থাকে, তাহলে আমরা উপাদানগুলিকে অদলবদল করি এবং বুঝতে পারি যে উপাদানগুলি সঠিক ক্রমে রয়েছে কিনা তা আমাদের এখন কোন গ্যারান্টি নেই। এর মানে হল যে আমাদের আরেকটি পুনরাবৃত্তি করতে হবে। উদাহরণস্বরূপ, ধরুন আমাদের আছে [3, 5, 2]। 5এর চেয়ে বেশি 3- সব ঠিক আছে। কিন্তু 2এর চেয়ে কম 5। যাইহোক, [3, 2, 5]অন্য পাস প্রয়োজন, যেহেতু3 > 2এবং তাদের অদলবদল করা দরকার। যেহেতু আমরা একটি লুপের মধ্যে একটি লুপ ব্যবহার করছি, আমাদের অ্যালগরিদমের জটিলতা বৃদ্ধি পায়। nউপাদান দেওয়া হলে , এটি হয়ে যায় n * n, অর্থাৎ, O(n^2). একে বলা হয় দ্বিঘাত জটিলতা। সাধারণভাবে, আমরা ঠিক কতগুলি পুনরাবৃত্তির প্রয়োজন হবে তা জানতে পারি না। একটি অ্যালগরিদমের জটিলতার অভিব্যক্তি দেখায় কিভাবে জটিলতা সবচেয়ে খারাপ ক্ষেত্রে বৃদ্ধি পায়। nঅর্থাৎ, এটি নির্দেশ করে যে উপাদানের সংখ্যা পরিবর্তনের সাথে সাথে কার্যকর করার সময় কতটা বাড়বে । বুদ্বুদ সাজানোর সহজতম এবং সবচেয়ে অদক্ষ বাছাই অ্যালগরিদম এক. একে কখনো কখনো "স্টুপিড সর্ট"ও বলা হয়। এই বিষয়ে উপাদান:
আরেকটি সাজানোর অ্যালগরিদম হল নির্বাচন সাজানো। এটিতে চতুর্মুখী জটিলতাও রয়েছে, তবে আরও পরে। তাই ধারণা সহজ. প্রতিটি পাসে, আমরা ক্ষুদ্রতম উপাদান নির্বাচন করি এবং এটিকে শুরুতে স্থানান্তর করি। উপরন্তু, প্রতিটি পাস ডানদিকে এক ধাপ শুরু হয়। অন্য কথায়, প্রথম পাসটি জিরোথ উপাদান থেকে শুরু হয়, দ্বিতীয় পাসটি প্রথম থেকে ইত্যাদি। এটি দেখতে এরকম হবে:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
int minInd = left;
for (int i = left; i < array.length; i++) {
if (array[i] < array[minInd]) {
minInd = i;
}
}
swap(array, left, minInd);
}
System.out.println(Arrays.toString(array));
এই বাছাইটি অস্থির, কারণ অভিন্ন উপাদানগুলি (আমরা উপাদানগুলিকে সাজানোর জন্য যে কোনও বৈশিষ্ট্যের পরিপ্রেক্ষিতে ব্যবহার করছি) তাদের আপেক্ষিক অবস্থান পরিবর্তন করতে পারে। একটি ভাল উদাহরণ আছে উইকিপিডিয়া নিবন্ধে নির্বাচন সাজানোর বিষয়ে । এই বিষয়ে উপাদান:
সন্নিবেশ বাছাই এছাড়াও দ্বিঘাত জটিলতা আছে, যেহেতু আমরা আবার একটি লুপের মধ্যে একটি লুপ আছে. কি সন্নিবেশ সাজানোর ভিন্ন করে তোলে? এই বাছাই অ্যালগরিদম "স্থিতিশীল।" এর মানে হল যে অভিন্ন উপাদানগুলি তাদের আপেক্ষিক ক্রম পরিবর্তন করবে না। আবার, আমরা যে বৈশিষ্ট্যগুলি দ্বারা বাছাই করছি তার পরিপ্রেক্ষিতে অভিন্ন মানে।
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int left = 0; left < array.length; left++) {
// Get an element
int value = array[left];
// Iterate through the elements that are in front of this element
int i = left - 1;
for (; i >= 0; i--) {
// If the current element is smaller, then move the larger element to the right.
if (value < array[i]) {
array[i + 1] = array[i];
} else {
// If the current element is larger, we stop
break;
}
}
// Insert the current value in the empty space
array[i + 1] = value;
}
System.out.println(Arrays.toString(array));
শাটল সাজানোর
আরেকটি সহজ বাছাই অ্যালগরিদম আছে: শাটল সাজানোর। এটি একটি দ্বিমুখী বুদবুদ বা ককটেল শেকার সাজানোর নামেও পরিচিত। এই বিকল্প নামগুলি আমাদের বলে যে শাটল সাজানোর স্পেস শাটল সম্পর্কে নয়। এটি এমন কিছু সম্পর্কে যা সামনে পিছনে চলে যায়। আপনি যখন এই অ্যালগরিদমটি মনে করেন তখন আপনি এটি ভাবতে পারেন। অ্যালগরিদম সারাংশ কি? অ্যালগরিদমের সারমর্ম হল যে আমরা বাম থেকে ডানে পুনরাবৃত্তি করি, উপাদানগুলিকে অদলবদল করি এবং অন্য দিকে অবশিষ্ট উপাদানগুলির মধ্যে কোনটি অদলবদল করা দরকার কিনা তা পরীক্ষা করি।
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
swap(array, i, i - 1);
for (int z = i - 1; (z - 1) >= 0; z--) {
if (array[z] < array[z - 1]) {
swap(array, z, z - 1);
} else {
break;
}
}
}
}
System.out.println(Arrays.toString(array));
আরেকটি সহজ বাছাই অ্যালগরিদম হল শেল সাজানো। এর সারাংশটি বুদবুদ সাজানোর অনুরূপ, তবে প্রতিটি পুনরাবৃত্তিতে আমাদের তুলনামূলক উপাদানগুলির মধ্যে একটি আলাদা ব্যবধান রয়েছে। এটি প্রতিটি পুনরাবৃত্তির সাথে অর্ধেক কাটা হয়। এখানে একটি বাস্তবায়ন আছে:
int[] array = {10, 2, 10, 3, 1, 2, 5};
System.out.println(Arrays.toString(array));
// Calculate the gap between the checked elements
int gap = array.length / 2;
// As long as there is a gap between the elements
while (gap >= 1) {
for (int right = 0; right < array.length; right++) {
// Shift the right index until we find one for which
// there is the necessary gap between it and the element before it
for (int c = right - gap; c >= 0; c -= gap) {
if (array[c] > array[c + gap]) {
swap(array, c, c + gap);
}
}
}
// Recalculate the gap
gap = gap / 2;
}
System.out.println(Arrays.toString(array));
এই সহজ বাছাই অ্যালগরিদমগুলি ছাড়াও, আরও জটিল বাছাই অ্যালগরিদম রয়েছে। উদাহরণস্বরূপ, সাজান মার্জ. দুটি বিষয় লক্ষনীয়। প্রথমত, পুনরাবৃত্তি এখানে আমাদের উদ্ধারে আসে। দ্বিতীয়ত, অ্যালগরিদমের জটিলতা আর দ্বিঘাত নয়, যেমনটা আমরা অভ্যস্ত। এই অ্যালগরিদমের জটিলতা লগারিদমিক। এই হিসাবে লেখা হয় O(n log n). তাই এর বাস্তবায়ন করা যাক. প্রথমে, আমরা সাজানোর পদ্ধতিতে একটি পুনরাবৃত্ত কল লিখব:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
}
এখন, আমাদের বাস্তবায়নে মূল ক্রিয়া যোগ করা যাক। এখানে আমাদের সুপার পদ্ধতি:
public static void mergeSort(int[] source, int left, int right) {
// Select the delimiter, i.e. split the input array in half
int delimiter = left + ((right - left) / 2) + 1;
// Recursively execute this function on the two halves (if we can split the input array)
if (delimiter > 0 && right > (left + 1)) {
mergeSort(source, left, delimiter - 1);
mergeSort(source, delimiter, right);
}
// Create a temporary array with the required size
int[] buffer = new int[right - left + 1];
// Starting from the specified left index, go through each element.
int cursor = left;
for (int i = 0; i < buffer.length; i++) {
// We use delimeter to point to the element on the right half
// If delimeter> right, then the right half has no elements that haven't been added
if (delimiter > right || source[cursor] > source[delimiter]) {
buffer[i] = source[cursor];
cursor++;
} else {
buffer[i] = source[delimiter];
delimiter++;
}
}
System.arraycopy(buffer, 0, source, left, buffer.length);
}
আমরা কল করে আমাদের উদাহরণ চালাতে পারিmergeSort(array, 0, array.length-1). যেমন আপনি দেখতে পাচ্ছেন, প্রক্রিয়াটি একটি ইনপুট অ্যারে গ্রহণ করার জন্য ফুটে ওঠে এবং সেই বিভাগের শুরু এবং শেষের ইঙ্গিত দেয় যা সাজানো দরকার। বাছাই শুরু হলে, এই অ্যারের শুরু এবং শেষ হয়. তারপর আমরা ডিলিমিটার গণনা করি, যেটি সূচক যেখানে আমরা অ্যারেকে বিভক্ত করব। যদি অ্যারেটিকে 2 ভাগে ভাগ করা যায়, তবে আমরা অ্যারের দুটি অর্ধেকের জন্য বারবার সাজানোর পদ্ধতিটিকে বলি। আমরা একটি অক্জিলিয়ারী বাফার প্রস্তুত করি যেখানে আমরা সাজানো বিভাগটি সন্নিবেশ করব। এরপরে, সাজানোর জন্য বিভাগের শুরুতে সূচী সেট করুন এবং খালি বাফারের প্রতিটি উপাদানের মধ্য দিয়ে হাঁটা শুরু করুন, এটি ক্ষুদ্রতম উপাদান দিয়ে পূরণ করুন। যদি সূচক দ্বারা নির্দেশিত উপাদানটি বিভাজনকারী দ্বারা নির্দেশিত উপাদানের চেয়ে কম হয়, আমরা উপাদানটিকে বাফারে রাখি এবং সূচকটি স্থানান্তর করি। অন্যথায়, আমরা ডিলিমিটার দ্বারা নির্দেশিত উপাদানটিকে বাফারে রাখি এবং বিভাজনকারী স্থানান্তর করি। যত তাড়াতাড়ি ডিলিমিটার বাছাই করা বিভাগের সীমানা অতিক্রম করে বা আমরা সম্পূর্ণ অ্যারে পূরণ করি, নির্দিষ্ট পরিসরটি সাজানো বলে মনে করা হয়।এই বিষয়ে উপাদান:
আরেকটি আকর্ষণীয় সাজানোর অ্যালগরিদম হল গণনা সাজানো। এখানে অ্যালগরিদমিক জটিলতা হল O(n+k), যেখানে nউপাদানের সংখ্যা এবং kএকটি উপাদানের সর্বোচ্চ মান। এই অ্যালগরিদমের একটি ত্রুটি রয়েছে: আমাদের অ্যারের সর্বনিম্ন এবং সর্বাধিক মানগুলি জানতে হবে। এখানে গণনা সাজানোর একটি উদাহরণ:
public static int[] countingSort(int[] theArray, int maxValue) {
// An array of "counters", ranging from 0 to the maximum value
int numCounts[] = new int[maxValue + 1];
// We increase the counter in the corresponding cell (index = value)
for (int num : theArray) {
numCounts[num]++;
}
// Create an array to hold the sorted result
int[] sortedArray = new int[theArray.length];
int currentSortedIndex = 0;
// Run through the array of "counters"
for (int n = 0; n < numCounts.length; n++) {
int count = numCounts[n];
// Run through the number of values
for (int k = 0; k < count; k++) {
sortedArray[currentSortedIndex] = n;
currentSortedIndex++;
}
}
return sortedArray;
}
আপনি বুঝতে পারেন যে এটি খুব অসুবিধাজনক যখন আমাদের সর্বনিম্ন এবং সর্বাধিক মানগুলি আগে থেকে জানতে হবে। এবং আমরা এখানে আরেকটি অ্যালগরিদম পেয়েছি: রেডিক্স সর্ট। আমি এখানে শুধুমাত্র দৃশ্যত অ্যালগরিদম উপস্থাপন করব। বাস্তবায়নের জন্য সম্পূরক উপকরণ দেখুন: উপকরণ:
ঠিক আছে, এটি ডেজার্টের জন্য সময় - দ্রুত বাছাই, সবচেয়ে বিখ্যাত সাজানোর অ্যালগরিদমগুলির মধ্যে একটি৷ এর লগারিদমিক জটিলতা রয়েছে O(n log n): এই সাজানোর অ্যালগরিদম টনি হোয়ার দ্বারা তৈরি করা হয়েছিল। মজার বিষয় হল, তিনি সোভিয়েত ইউনিয়নে থাকার সময় এটি আবিষ্কার করেছিলেন, যেখানে তিনি মস্কো বিশ্ববিদ্যালয়ে মেশিন অনুবাদ অধ্যয়ন করেছিলেন এবং একটি রাশিয়ান-ইংরেজি শব্দগুচ্ছ বই তৈরি করেছিলেন। আরও কি, জাভা এই অ্যালগরিদমের আরও জটিল সংস্করণ ব্যবহার করে Arrays.sort। কি সম্পর্কে Collections.sort? কেন জিনিসগুলি "হুডের নীচে" সাজানো হয় তা দেখে নিন না? এখানে কোড আছে:
public static void quickSort(int[] source, int leftBorder, int rightBorder) {
int leftMarker = leftBorder;
int rightMarker = rightBorder;
int pivot = source[(leftMarker + rightMarker) / 2];
do {
// Move the left marker from left to right as long as the element is less than pivot
while (source[leftMarker] < pivot) {
leftMarker++;
}
// Move the right marker as long as the element is greater than pivot
while (source[rightMarker] > pivot) {
rightMarker--;
}
// Check whether we need to swap the elements pointed to by the markers
if (leftMarker <= rightMarker) {
// The left marker will be less than the right one only if we need to do a swap
if (leftMarker < rightMarker) {
int tmp = source[leftMarker];
source[leftMarker] = source[rightMarker];
source[rightMarker] = tmp;
}
// Shift the markers to get new borders
leftMarker++;
rightMarker--;
}
} while (leftMarker <= rightMarker);
// Execute recursively on the parts
if (leftMarker < rightBorder) {
quickSort(source, leftMarker, rightBorder);
}
if (leftBorder < rightMarker) {
quickSort(source, leftBorder, rightMarker);
}
}
এই সব খুব ভীতিকর উপাদান, তাই এটি খনন করা যাক. ইনপুট অ্যারের জন্য ( int[]উত্স), আমরা দুটি মার্কার তৈরি করি: বাম ( L) এবং ডান ( R)। প্রথম পদ্ধতি কলের সময়, তারা অ্যারের শুরু এবং শেষের সাথে সঙ্গতিপূর্ণ। তারপর আমরা পিভট উপাদান সনাক্ত করি, যা যথাযথভাবে নামকরণ করা হয় pivot। pivotএর পরে, আমাদের কাজ হল -এর থেকে ছোট মানগুলিকে বাম দিকে pivotএবং বড়গুলিকে — ডানদিকে সরানো ৷ এটি করার জন্য, আমরা প্রথমে Lমার্কারটি সরাতে থাকি যতক্ষণ না আমরা এর থেকে বড় একটি মান খুঁজে পাই pivot। যদি কোন ছোট মান পাওয়া যায় না, তাহলে
L এর সমান হয়ে যায়
pivot। তারপরে আমরা
Rমার্কারটি সরাতে থাকি যতক্ষণ না আমরা এর থেকে ছোট একটি মান খুঁজে পাই
pivot। যদি কোন বড় মান পাওয়া না যায়, তাহলে
Rসমান হয়ে যায়
pivot। এর পরে, যদি
Lমার্কারটি মার্কারের আগে থাকে
Rবা এটির সাথে মিলে যায়, তাহলে আমরা উপাদানগুলিকে অদলবদল করার চেষ্টা করি যদি উপাদানটি
Lউপাদানটির চেয়ে কম হয়
R। তারপরে আমরা
L1 দ্বারা ডানদিকে সরে যাই, এবং আমরা
R1 দ্বারা বামে স্থানান্তরিত হই। যখন
Lমার্কারটি মার্কারের বাইরে চলে যায়
R, তখন এর অর্থ হল অদলবদল সম্পূর্ণ হয়েছে: ছোট মানগুলি এর বাম দিকে
pivot, বড় মানগুলি ডানদিকে রয়েছে
pivot. এর পরে, আমরা একই সাজানোর পদ্ধতিকে সাবঅ্যারেতে পুনরাবৃত্তিমূলকভাবে বলি — সেকশনের শুরু থেকে ডান মার্কারে সাজানো হবে এবং বাম মার্কার থেকে সেকশনের শেষ পর্যন্ত সাজানো হবে। কেন শুরু থেকে ডান মার্কার? কারণ একটি পুনরাবৃত্তির শেষে, এটি দেখা যাচ্ছে যে ডান মার্কারটি বাম অংশের সীমানা হওয়ার জন্য যথেষ্ট সরে যায়। এই অ্যালগরিদমটি সহজ বাছাইয়ের চেয়ে আরও জটিল, তাই এটি স্কেচ করা ভাল। একটি সাদা কাগজ নিন এবং লিখুন: 4 2 6 7 3। তারপর
pivotমাঝখানে লিখুন, অর্থাৎ 6 নম্বরের নিচে। এটিকে বৃত্ত করুন। 4 এর নিচে লিখুন
Lএবং 3 এর নিচে লিখুন
R।
L6 থেকে 4 কম, 6 থেকে 2 কম। আমরা পজিশনে চলে যাই
pivot, কারণ
Lঅতীতে যেতে পারি না
pivot, শর্ত অনুযায়ী। আবার লিখুন 4 2 6 7 3. বৃত্ত 6 (
pivot) এবং
Lএটির নীচে রাখুন। এখন মার্কার সরান
R। 3 6 এর থেকে কম, তাই
R3 এর উপর মার্কার রাখুন। যেহেতু 3 6 এর থেকে কম (
pivot), আমরা একটি সম্পাদন করি
swap। ফলাফল লিখুন: 4 2 3 7 6. সার্কেল 6, কারণ এটি এখনও
pivot. মার্কারটি
L3-এ রয়েছে৷
Rমার্কারটি 6-
Lএ
R৷
Lপরবর্তী নম্বরে যান । এখানে আমি দুটি সম্ভাবনা অন্বেষণ করতে চাই: 1) যেখানে উপান্তর সংখ্যা 7 এবং 2) ক্ষেত্রে যেখানে এটি 1, 7 নয়।
যদি উপান্তর সংখ্যা 1 হয়: মার্কারটিকে 1 এ সরান
L, কারণ আমরা সরাতে পারি
Lযতক্ষণ পর্যন্ত
Lমার্কার এর থেকে ছোট একটি সংখ্যাকে নির্দেশ করে
pivot। কিন্তু আমরা 6 থেকে সরে যেতে পারি না
R, কারণ আমরা কেবল তখনই R সরাতে পারি যদি
Rমার্কার একটি সংখ্যাকে নির্দেশ করে যা এর থেকে বড়
pivot। আমরা একটি সম্পাদন করি না
swap, কারণ 1টি 6-এর চেয়ে কম। বর্তমান পরিস্থিতি লিখুন: 4 2 3 1 6। বৃত্ত 6 (
pivot)।
Lস্থানান্তরিত হয়
pivotএবং নড়াচড়া বন্ধ করে।
Rনড়াচড়া করে না আমরা একটি অদলবদল সঞ্চালন না. শিফট
Lএবং
Rএকটি অবস্থান দ্বারা.
R1 এর নিচে মার্কার লিখুন।
Lমার্কারটি সীমার বাইরে। কারণ
Lসীমার বাইরে, আমরা কিছুই করি না। কিন্তু, আমরা আবার 4 2 3 1 লিখি, কারণ এটি আমাদের বাম দিক, যা
pivot(6) এর চেয়ে কম। নতুন নির্বাচন করুন
pivotএবং সবকিছু আবার শুরু করুন :)
যদি শেষ সংখ্যা 7 হয়:মার্কারটিকে 7 এ সরান।
Lআমরা সঠিক মার্কারটি সরাতে পারছি না, কারণ এটি ইতিমধ্যেই পিভটের দিকে নির্দেশ করছে। 7 এর থেকে বড়
pivot, তাই আমরা একটি সম্পাদন করি
swap। ফলাফল লিখুন: 4 2 3 6 7. বৃত্ত 6, কারণ এটি হল
pivot. মার্কারটি
Lএখন 7-এ স্থানান্তরিত হয়েছে, এবং মার্কারটি 3-এ স্থানান্তরিত হয়েছে। অংশ থেকে শেষ পর্যন্ত
Rসাজানোর কোনো মানে হয় না , কারণ এখানে শুধুমাত্র 1টি উপাদান রয়েছে। যাইহোক, আমরা সাজানোর জন্য
L4 থেকে অংশটি মার্কারে পাঠাই ।
Rআমরা একটি নির্বাচন করি
pivotএবং আবার শুরু করি :) প্রথম নজরে, মনে হতে পারে যদি আপনি এর সমান অনেক মান যোগ করেন
pivot, তাহলে আপনি অ্যালগরিদম ভঙ্গ করবেন। কিন্তু এই ঘটনা নয়. আপনি চতুর সংমিশ্রণ সম্পর্কে চিন্তা করতে পারেন এবং কাগজে নিজেকে বোঝাতে পারেন যে সবকিছুই সঠিক এবং আশ্চর্যজনক যে এই ধরনের সহজ ক্রিয়াগুলি এমন একটি নির্ভরযোগ্য বাছাই প্রক্রিয়া বাস্তবায়ন করে। একমাত্র নেতিবাচক দিক হল এই সাজানোর অ্যালগরিদম স্থিতিশীল নয়। কারণ একটি অদলবদল অভিন্ন উপাদানগুলির আপেক্ষিক ক্রম পরিবর্তন করতে পারে যদি তাদের একটির আগে
pivotঅন্য উপাদানটি আগে অংশে অদলবদল করার আগে সম্মুখীন হয়
pivot।
তলদেশের সরুরেখা
উপরে, আমরা জাভাতে বাস্তবায়িত বাছাই অ্যালগরিদমের একটি "ভদ্রলোকের" সেট দেখেছি। অ্যালগরিদমগুলি সাধারণত কার্যকর হয়, উভয়ই একটি প্রয়োগের দৃষ্টিকোণ থেকে এবং কীভাবে চিন্তা করতে হয় তা শেখার ক্ষেত্রে। কিছু সহজ, কিছু আরও জটিল। স্মার্ট মানুষ কিছু জন্য তাদের গবেষণার রক্ষা. অন্যদের জন্য, তারা সুপার মোটা বই লিখেছেন। আমি আশা করি পরিপূরক উপকরণগুলি আপনাকে আরও শিখতে সাহায্য করবে, যেহেতু এই নিবন্ধটি শুধুমাত্র একটি সংক্ষিপ্ত বিবরণ যা ইতিমধ্যেই ওজনদার হয়ে উঠেছে। এবং এর উদ্দেশ্য একটি ছোট ভূমিকা প্রদান করা হয়.
আপনি যদি "গ্রোকিং অ্যালগরিদম " পড়েন তাহলে আপনি অ্যালগরিদমগুলির একটি ভূমিকাও খুঁজে পেতে পারেন ৷ আমি জ্যাক ব্রাউনের প্লেলিস্টটিও পছন্দ করি:
AQA সিদ্ধান্ত 1 1.01 একটি অ্যালগরিদম ট্রেসিং । মজার জন্য, আপনি
সাজানোর সময় অ্যালগরিদম ভিজ্যুয়ালাইজেশন দেখতে পারেন।visualgo.net ।
GO TO FULL VERSION