5 सॉर्टिंग अल्गोरिथम बच्चों को समझाया गए

This post is also available in: English العربية (Arabic)

कंप्यूटर विज्ञान में, सॉर्टिंग और सर्चिंग दो सबसे महत्वपूर्ण प्रक्रियाएं हैं जो लगभग हर कंप्यूटर एप्लीकेशन का हिस्सा होते हैं। यह लेख बच्चों को आसान और सरल तरीके से समझाए गए 5 सर्वश्रेष्ठ सॉर्टिंग एल्गोरिदम के बारे में है।

सॉर्टिंग क्या होती है?

सॉर्टिंग का अर्थ है कि किसी सूची में वस्तुओं को क्रम में व्यवस्थित करना। किसी सूची में आइटम संख्यात्मक, अल्फाबेटिक या लेक्सिकोग्राफ़िक हो सकते हैं। यह क्रम या तो आरोही या अवरोही हो सकता है।

• आरोहीक्रम निम्नतम से उच्चतम तक वस्तुओं का क्रम होता है। संख्या के सन्दर्भ में 0 से 9 और अक्षर के सन्दर्भ में ए(A) से जेड(Z)।
• अवरोही क्रम उच्चतम से निम्नतम तक वस्तुओं की व्यवस्था करना होता है। संख्याओं के सन्दर्भ में 9 से 0 और वर्णमाला के सन्दर्भ में Z से A।

लेक्सिकोग्राफिक ऑर्डर (ए, बी) के सन्दर्भ में d।

कंप्यूटरों में, नाम, संख्या और रिकॉर्ड पर सॉर्टिंग की जा सकती है।

सॉर्टिंग एल्गोरिथ्म क्या होता है?

एलिमेंट्स पर एक तुलना ऑपरेटर के अनुसार किसी दिए गए सरणी या सूची एलिमेंट्स को पुनर्व्यवस्थित करने के लिए एक सॉर्टिंग एल्गोरिथ्म का उपयोग किया जाता है। तुलना ऑपरेटर का उपयोग संबंधित डेटा संरचना में एलिमेंट्स के नए क्रम को तय करने के लिए किया जाता है। तुलना क्रम < (less than) या > (greater than) हो सकता है।

उदाहरण के लिए, यदि हम आरोही क्रम में 45 और 23 को व्यवस्थित करना चाहते हैं, तो प्रक्रिया होगी

यदि 45> 23 है तो पदों को इंटरचेंज करें अन्यथा कुछ न करें।

इसी प्रकार, हम 45 और 23 को अवरोही क्रम में व्यवस्थित करना चाहते हैं, तो यह प्रक्रिया होगी

यदि 45 <23 तो पदों को इंटरचेंज करें अन्यथा कुछ न करें।

हमें सॉर्टिंग एल्गोरिदम की आवश्यकता क्यों होती है?

सॉर्ट करने से डेटा को संसाधित करने और जानकारी प्राप्त करने के लिए आवश्यक समय कम हो जाता है। उदाहरण के लिए, किसी टेलीफ़ोन डायरेक्टरी से किसी मित्र का फ़ोन नंबर देखना अपेक्षाकृत आसान है क्योंकि इसमें नामों को वर्णानुक्रम में क्रमबद्ध किया जाता है।

This example clearly illustrates one of the main reasons that sorting large quantities of information is desirable. That is, sorting greatly improves the efficiency of searching. This considerably decreases the computer’s processing time. Efficient sorting is important to optimize the use of other algorithms!

Types of Sorting

Classification of sorting algorithms is done on the basis of the following parameters:

• Computational complexity (worst, average and best behaviour) in terms of the size of the list (n). Typically, good behaviour is O(n log n) and bad behaviour is Ω(n²). Ideal behaviour for a sort is O(n).
• Memory usage (and use of other computer resources). Algorithms using less memory space usually run faster than those using more memory.
• Stability: Stable sorting algorithms maintain the relative order of records with equal keys (i.e. values). That is, a sorting algorithm is stable if whenever there are two records R and S with the same key and with R appearing before S in the original list, R will appear before S in the sorted list.
• The general method used to perform the sorting like Insertion, Exchange, Selection, Merging, etc.

5 सॉर्टिंग अल्गोरिथम बच्चों को समझाया गए

Depending on the method used in sorting, these algorithms are of the following types:

• Bubble Sort
• Insertion Sort
• Selection Sort
• Quick Sort
• Merge Sort

To understand the working of these algorithms, let’s consider arranging numbered cards in ascending order.

Bubble Sort

You lay all the cards in a line. Now, start from one end. Is the first card of a smaller value than the second? Then leave them as it is. If not, interchange their positions.

Next look at the second and the third card. Here also repeat the previous process. Is the second card of a smaller value than the third? Then leave them as it is. If not, interchange their positions.

Repeat the process with the next pair of cards. When you hit the end of the line, go back to the beginning and repeat the process. Keep doing this until you go through the line and never interchange two cards. In this process, the maximum number of times you repeat the process is equal to the number of cards.

Algorithm for Bubble Sort

Step 1: Starting with the first element(index = 0), compare the current element with the next element of the array.

Step 2: If the current element is greater than the next element of the array, swap them.

Step 3: If the current element is less than the next element, move to the next element. Repeat Step 1.

Code for Bubble Sort in C++

void swapping(int &a, int &b) {     
   int temp;
   temp = a;
   a = b;
   b = temp;
}
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void bubbleSort(int *array, int size) {
   for(int i = 0; i<size; i++) {
      int swaps = 0;         
      for(int j = 0; j<size-i-1; j++) {
         if(array[j] > array[j+1]) {       
            swapping(array[j], array[j+1]);
            swaps = 1;    
         }
      }
      if(!swaps)
         break;    
   }
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n];     
   cout << "Enter elements:" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   bubbleSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

Insertion Sort

Imagine you are holding the cards in your hand, and these cards are sorted. The dealer hands you exactly one new card. The new card could be smaller than some cards you are already holding, and so you go down the line, comparing the new card against each card in your hand until you find the place to put it. You insert the new card in the right place, and once again, your hand holds a fully sorted card.

Then the dealer gives you another card, and you repeat the same procedure. Then another card, and so on, until the dealer stops giving you cards.

Algorithm for Insertion Sort

Step 1: Iterate from arr[1] to arr[n] over the array.

Step 2: Compare the current element (key) to its predecessor.

Step 3: If the key element is smaller than its predecessor, compare it to the elements before. Move the greater elements one position up to make space for the swapped element.

Code for Insertion Sort in C++

void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void insertionSort(int *array, int size) {
   int key, j;
   for(int i = 1; i<size; i++) {
      key = array[i];
      j = i;
      while(j > 0 && array[j-1]>key) {
         array[j] = array[j-1];
         j--;
      }
      array[j] = key;   
   }
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n];    
   cout << "Enter elements:" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   insertionSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);
}

Selection Sort

Lay the cards again. Start at one end. Look at the first card. Remember that number.

Now, look at the second card. Does it have a smaller number? Then start remembering the second number instead of the first number. Otherwise, just remember the first number.

After that go to the third card. Does it have a smaller value? If so, remember this value instead. If not, remember the old value. Keep doing this until you reach the end of the line. Now you have the smallest value card. Put the card first. Now do this again, but instead of starting from the first position, start from the second.

Repeat this process until you are starting with the last card in the line. At this point, you have sorted the cards in ascending order.

Algorithm for Selection Sort

Step 1: Set MIN to location 0

Step 2: Search the minimum element in the list

Step 3: Swap with value at location MIN

Step 4: Increment MIN by 1 and Goto Step 2

Step 5: Exit

Code for Selection Sort in C++

void swapping(int &a, int &b) {         
   int temp;
   temp = a;
   a = b;
   b = temp;
}
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void selectionSort(int *array, int size) {
   int i, j, imin;
   for(i = 0; i<size-1; i++) {
      imin = i;   
      for(j = i+1; j<size; j++)
         if(array[j] < array[imin])
            imin = j;
         swap(array[i], array[imin]);
   }
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n];           
   cout << "Enter elements:" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   selectionSort(arr, n);
   cout << "Array after Sorting: ";
   display(arr, n);

Quick Sort

Lay out the cards in a line. Pick a card at random. Now place all cards with a value greater than the randomly selected card to the right side and place all cards with a value lesser than the randomly selected card to the left side.

Now go to one of the sides and pick a card at random and place all the cards with a greater value than the randomly selected card to the right side and place all cards with value lesser than the randomly selected card to the left side.

Continue doing this until all the cards are sorted.

Algorithm for Quick Sort

Step 1: Make any element as pivot

Step 2: Partition the array on the basis of pivot

Step 3: Apply quick sort on left partition recursively

Step 4: Apply quick sort on right partition recursively

Code for Quick Sort in C++

void swap(int *a, int *b) {
   int temp;
   temp = *a;
   *a = *b;
   *b = temp;
}

int Partition(int a[], int l, int h) {
   int pivot, index, i;
   index = l;
   pivot = h;
   for(i = l; i < h; i++) {
      if(a[i] < a[pivot]) {
         swap(&a[i], &a[index]);
         index++;
      }
   }
   swap(&a[pivot], &a[index]);
   return index;
}
int RandomPivotPartition(int a[], int l, int h) {
   int pvt, n, temp;
   n = rand();
   pvt = l + n%(h-l+1);
   swap(&a[h], &a[pvt]);
   return Partition(a, l, h);
}
int QuickSort(int a[], int l, int h) {
   int pindex;
   if(l < h) {
      pindex = RandomPivotPartition(a, l, h);
      QuickSort(a, l, pindex-1);
      QuickSort(a, pindex+1, h);
   }
   return 0;
}
int main() {
   int n, i;
   cout<<"\nEnter the number of data element to be sorted: ";
   cin>>n;
   int arr[n];
   for(i = 0; i < n; i++) {
      cout<<"Enter element "<<i+1<<": ";
      cin>>arr[i];
   }
   QuickSort(arr, 0, n-1);
   cout<<"\nSorted Data ";
   for (i = 0; i < n; i++)
      cout<<"->"<<arr[i];
   return 0;
}

Merge Sort

Lay out the cards in a line. Split the line in half. Then each half in half. Keep doing this until you have only pairs of cards. Sort the pairs. Then group two pairs together into groups of four. Sort the group of four. Keep doing this until you are back to the full length of cards.

Algorithm for Merge Sort

Step 1: If it is only one element in the list it is already sorted, return

Step 2: Divide the list recursively into two halves until it can no more be divided

Step 3: Merge the smaller lists into a new list in sorted order

Code for Merge Sort in C++

void swapping(int &a, int &b) {     
   int temp;
   temp = a;
   a = b;
   b = temp;
}
void display(int *array, int size) {
   for(int i = 0; i<size; i++)
      cout << array[i] << " ";
   cout << endl;
}
void merge(int *array, int l, int m, int r) {
   int i, j, k, nl, nr;
   nl = m-l+1; nr = r-m;
   int larr[nl], rarr[nr];
   for(i = 0; i<nl; i++)
      larr[i] = array[l+i];
   for(j = 0; j<nr; j++)
      rarr[j] = array[m+1+j];
   i = 0; j = 0; k = l;
   while(i < nl && j<nr) {
      if(larr[i] <= rarr[j]) {
         array[k] = larr[i];
         i++;
      }else{
         array[k] = rarr[j];
         j++;
      }
      k++;
   }
   while(i<nl) {     
      array[k] = larr[i];
      i++; k++;
   }
   while(j<nr) {     
      array[k] = rarr[j];
      j++; k++;
   }
}
void mergeSort(int *array, int l, int r) {
   int m;
   if(l < r) {
      int m = l+(r-l)/2;
      mergeSort(array, l, m);
      mergeSort(array, m+1, r);
      merge(array, l, m, r);
   }
}
int main() {
   int n;
   cout << "Enter the number of elements: ";
   cin >> n;
   int arr[n];     
   cout << "Enter elements:" << endl;
   for(int i = 0; i<n; i++) {
      cin >> arr[i];
   }
   cout << "Array before Sorting: ";
   display(arr, n);
   mergeSort(arr, 0, n-1);     
   cout << "Array after Sorting: ";
   display(arr, n);
}