شرح 5 خوارزميات الفرز للأطفال

This post is also available in: English (الإنجليزية) हिन्दी (الهندية)

في أي علم كمبيوتر ، يعد الفرز والبحث من أهم العمليات التي تعد جزءًا من كل تطبيق كمبيوتر تقريبًا. تتناول هذه المقالة أفضل 5 خوارزميات فرز موضحة للأطفال بطريقة سهلة وبسيطة.

ما هو الفرز؟

الفرز يعني ترتيب العناصر في قائمة بالترتيب. يمكن أن تكون العناصر الموجودة في القائمة رقمية أو أبجدية أومعجمية. يمكن أن يكون هذا الترتيب تصاعديًا أو تنازليًا.

• الترتيب التصاعدي هو ترتيب العناصر من الأدنى إلى الأعلى. من 0 إلى 9 في حالة الأرقام ومن الألف إلى الياء في حالة الحروف الهجائية.
• الترتيب التنازلي هو ترتيب العناصر من الأعلى إلى الأعلى. 9 إلى 0 في حالة الأرقام و Z إلى A في حالة الحروف الهجائية.

في حالة الترتيب المعجمي (أ ، ب) د.

في أجهزة الكمبيوتر ، يمكن إجراء الفرز على الأسماء والأرقام والسجلات.

ما هي خوارزمية الفرز؟

يتم استخدام خوارزميةالفرز لإعادة ترتيب مصفوفة معينة أو قائمة عناصر وفقًا لعامل مقارنة على العناصر. يتم استخدام عامل المقارنة لتحديد الترتيب الجديد للعنصر في بنية البيانات المعنية. يمكن أن يكون ترتيب المقارنة < (أقل من) أو > (أكبر من).

على سبيل المثال ، إذا أردنا ترتيب 45 و 23 بترتيب تصاعدي ، فستكون العملية

إذا كان 45> 23 ثم قم بتبديل المواقف الأخرى لا تفعل شيئًا

وبالمثل ، نريد ترتيب 45 و 23 بترتيب تنازلي ، ستكون العملية

إذا كان 45 أقل من 23 ، فتبادل المواقف الأخرى لا تفعل شيئًا

لماذا نحتاج فرز الخوارزميات؟

يقلل الفرز من الوقت اللازم لمعالجة البيانات والحصول على المعلومات. على سبيل المثال ، من السهل نسبيًا البحث عن رقم هاتف صديق من دليل الهاتف لأن الأسماء الموجودة فيه مرتبة حسب الترتيب الأبجدي.

يوضح هذا المثال بوضوح أحد الأسباب الرئيسية التي تجعل فرز كميات كبيرة من المعلومات أمرًا مرغوبًا فيه. أي أن الفرز يحسن بشكل كبير من كفاءة البحث. هذا يقلل بشكل كبير من وقت معالجة الكمبيوتر. الفرز الفعال مهم لتحسين استخدام الخوارزميات الأخرى!

أنواع الفرز

يتم تصنيف خوارزميات الفرز على أساس المعلمات التالية:

• التعقيد الحسابي (السلوك الأسوأ والمتوسط ​​والأفضل) من حيث حجم القائمة (ن). عادةً ما يكون السلوك الجيد هو O (n log n) والسلوك السيئ هو Ω (n²). السلوك المثالي لنوع ما هو O (n).
• استخدام الذاكرة (واستخدام موارد الكمبيوتر الأخرى). عادةً ما تعمل الخوارزميات التي تستخدم مساحة ذاكرة أقل بشكل أسرع من تلك التي تستخدم ذاكرة أكبر.
• الاستقرار: تحافظ خوارزميات الفرز المستقرة على الترتيب النسبي للسجلات بمفاتيح متساوية (أي القيم). أي أن خوارزمية الفرز تكون مستقرة إذا كان هناك سجلين R و S بنفس المفتاح ومع ظهور R قبل S في القائمة الأصلية ، سيظهر R قبل S في القائمة المصنفة.
• الطريقة العامة المستخدمة لإجراء الفرز مثل الإدراج والتبادل والتحديد والدمج وما إلى ذلك.

شرح أفضل 5 خوارزميات فرز للأطفال

اعتمادًا على الطريقة المستخدمة في الفرز ، تكون هذه الخوارزميات من الأنواع التالية:

• فقاعة الفرز
• ترتيب بالإدراج
• اختيار نوع
• فرز سريع
• دمج الفرز

لفهم طريقة عمل هذه الخوارزميات ، دعنا نفكر في ترتيب البطاقات المرقمة بترتيب تصاعدي.

فقاعة الفرز

أنت تضع كل الأوراق في خط. الآن ، ابدأ من نهاية واحدة. هل البطاقة الأولى أصغر من الثانية؟ ثم اتركهم كما هو. إذا لم يكن كذلك ، قم بتبديل مواقفهم.

انظر بعد ذلك إلى البطاقة الثانية والثالثة. هنا أيضًا كرر العملية السابقة. هل البطاقة الثانية أصغر من الثالثة؟ ثم اتركهم كما هو. إذا لم يكن كذلك ، قم بتبديل مواقفهم.

كرر العملية مع الزوجين التاليين من البطاقات. عندما تضغط على نهاية السطر ، عد إلى البداية وكرر العملية. استمر في القيام بذلك حتى تمر عبر الخط ولا تقم أبدًا بتبادل بطاقتين. في هذه العملية ، يكون الحد الأقصى لعدد مرات تكرار العملية مساويًا لعدد البطاقات.

خوارزمية لفرز الفقاعة

الخطوة 1: بدءًا من العنصر الأول (الفهرس = 0) ، قارن العنصر الحالي بالعنصر التالي من المصفوفة.

الخطوة 2: إذا كان العنصر الحالي أكبر من العنصر التالي في المصفوفة ، فقم بتبديله.

الخطوة 3: إذا كان العنصر الحالي أقل من العنصر التالي ، فانتقل إلى العنصر التالي. كرر الخطوة 1.

رمز لفرز الفقاعات في 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);
}

ترتيب بالإدراج

تخيل أنك تمسك الأوراق في يدك ، وهذه البطاقات مرتبة. يمنحك الموزع بطاقة واحدة جديدة تمامًا. يمكن أن تكون البطاقة الجديدة أصغر من بعض البطاقات التي تمتلكها بالفعل ، وهكذا تنزل أسفل الخط ، وتقارن البطاقة الجديدة بكل بطاقة في يدك حتى تجد المكان المناسب لوضعها. تقوم بإدخال البطاقة الجديدة في المكان الصحيح ، ومرة ​​أخرى ، تمسك يدك ببطاقة مرتبة بالكامل.

ثم يعطيك الموزع بطاقة أخرى ، وتكرر نفس الإجراء. ثم بطاقة أخرى ، وهكذا ، حتى يتوقف التاجر عن إعطائك البطاقات.

خوارزمية لفرز الإدراج

الخطوة 1: كرر من arr [1] إلى arr [n] عبر المصفوفة.

الخطوة 2: قارن العنصر الحالي (المفتاح) بسابقه.

الخطوة 3: إذا كان العنصر الرئيسي أصغر من العنصر السابق ، فقارنه بالعناصر السابقة. حرك العناصر الأكبر في موضع واحد لأعلى لتوفير مساحة للعنصر الذي تم تبديله.

رمز لفرز الإدراج في ++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);
}

اختيار نوع

ضع البطاقات مرة أخرى. ابدأ من طرف واحد. انظر إلى البطاقة الأولى. تذكر هذا الرقم.

الآن ، انظر إلى البطاقة الثانية. هل لديها رقم أصغر؟ ثم ابدأ في تذكر الرقم الثاني بدلاً من الرقم الأول. خلاف ذلك ، فقط تذكر الرقم الأول.

بعد ذلك انتقل إلى البطاقة الثالثة. هل لها قيمة أصغر؟ إذا كان الأمر كذلك ، فتذكر هذه القيمة بدلاً من ذلك. إذا لم يكن كذلك ، فتذكر القيمة القديمة. استمر في فعل هذا حتى تصل إلى نهاية الخط. الآن لديك بطاقة أصغر قيمة. ضع البطاقة أولاً. افعل هذا مرة أخرى ، ولكن بدلاً من البدء من الموضع الأول ، ابدأ من المركز الثاني.

كرر هذه العملية حتى تبدأ بالبطاقة الأخيرة في السطر. في هذه المرحلة ، قمت بفرز البطاقات بترتيب تصاعدي.

خوارزمية لفرز التحديد

الخطوة 1: اضبط MIN على الموقع 0

الخطوة 2: ابحث عن الحد الأدنى للعنصر في القائمة

الخطوة 3: استبدل بالقيمة في الموقع MIN

الخطوة 4: زيادة MIN بمقدار 1 والانتقال إلى الخطوة 2

الخطوة 5: الخروج

رمز لفرز التحديد في ++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);

فرز سريع

ضع البطاقات في خط. اختر بطاقة بشكل عشوائي. الآن ضع جميع البطاقات التي تحتوي على قيمة أكبر من البطاقة المختارة عشوائيًا على الجانب الأيمن وضع جميع البطاقات ذات القيمة الأقل من البطاقة المختارة عشوائيًا على الجانب الأيسر.

انتقل الآن إلى أحد الجوانب واختر بطاقة عشوائيًا وضع جميع البطاقات ذات القيمة الأكبر من البطاقة المختارة عشوائيًا على الجانب الأيمن وضع جميع البطاقات ذات القيمة الأقل من البطاقة المختارة عشوائيًا على الجانب الأيسر.

استمر في القيام بذلك حتى يتم فرز جميع البطاقات.

خوارزمية الفرز السريع

خوارزمية الفرز السريع

الخطوة 2: قسم المصفوفة على أساس المحور

الخطوة 3: قم بتطبيق الفرز السريع على القسم الأيسر بشكل متكرر

الخطوة 4: قم بتطبيق التصنيف السريع على القسم الأيمن بشكل متكرر

رمز الفرز السريع في ++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;
}

دمج الفرز

ضع البطاقات في خط. اقسم الخط إلى نصفين. ثم كل نصف في النصف. استمر في القيام بذلك حتى يكون لديك أزواج فقط من البطاقات. رتب الأزواج. ثم جمِّع زوجين معًا في مجموعات من أربعة. افرز المجموعة المكونة من أربعة أفراد. استمر في القيام بذلك حتى تعود إلى الطول الكامل للبطاقات.

خوارزمية لدمج الفرز

الخطوة 1: إذا كان عنصرًا واحدًا فقط في القائمة ، فقد تم فرزه بالفعل ، فارجع

الخطوة 2: قسّم القائمة بشكل متكرر إلى نصفين حتى لا يمكن تقسيمها

الخطوة 3: دمج القوائم الأصغر في قائمة جديدة بالترتيب الفرز

رمز لدمج الفرز في ++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);
}