كل ما تحتاج لمعرفته حول Quicksort في C ++

هناك عدد كبير من خوارزميات الفرز. إن العثور على الخيار المناسب لتطبيقك هو مهمة تتطلب فهمًا موجزًا ​​لعوامل مثل الأداء ، وتعقيد الوقت ، وطول الكود ، وما إلى ذلك ، لخوارزمية معينة. في هذا المنشور ، سنلقي نظرة على جميع المفاهيم الأساسية المطلوبة لتنفيذ Quicksort في C ++ بالترتيب التالي:

• فهم خوارزمية الترتيب السريع
• الكود الزائف للفرز السريع
• برنامج Quicksort في C ++
• وقت تعقيد الترتيب السريع

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

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

1. أولاً ، سنطلب المصفوفة التي لم يتم فرزها من المستخدم.

2. بمجرد أن نحصل على المصفوفة غير المفرزة ، نحتاج إلى تحديد قيمة محورية من المصفوفة. يمكننا اختيار أي قيمة.

   
   
   

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

4. نقوم بالخطوة 3 حتى نحصل على مصفوفة مرتبة.

الآن ، دعنا نفكر في مثال وننفذ الخوارزمية ونرى كيف تعمل.

مرحبًا [5 ، 4 ، 1 ، 11 ، 9 ، 6 ، 2 ، 3] في هذا المثال ، سننظر دائمًا إلى المحور باعتباره العنصر الموجود في أقصى اليمين من القائمة.

لنستعرض كل خطوة ونفهم المنطق الذي استخدمناه لحل المشكلة.

• أولاً ، اخترنا '3' كمحور لدينا ورتبنا جميع العناصر الأقل من '3' في اليمين وجميع العناصر الأكبر من '3' على اليمين.

• في هذه المرحلة ، لدينا مشكلتان فرعيتان. دعنا نحل المشكلة الفرعية الموجودة على اليمين أولاً. اخترنا واحدًا كمحور لدينا ووضعنا '2' على اليمين.

• لحل المشكلة الفرعية الثانية ، نختار '6' كمحور لدينا ونضع العناصر كما ناقشناها سابقًا.

• لدينا 2 مشاكل فرعية أخرى. الأول يتم حله باختيار 4 كمحور والثاني يتم حله باختيار 9 كمحور. أخيرًا ، لدينا مصفوفة مرتبة مع العناصر الموضوعة في فهرس التسطير.

ملحوظة- النقطة المهمة التي يجب فهمها هنا هي أن جميع العمليات تتم في نفس المصفوفة. لم يتم إنشاء المصفوفات الجديدة.

الكود الزائف لـ Quicksort في C ++

QuickSort (مصفوفة [] ، فهرس_بداية ، نهاية_فهرسة) {if (start_index
 برنامج Quicksort في C ++ 
لقد فهمنا الخوارزمية وطورنا فهمًا عميقًا لعمل الخوارزمية. دعونا ننفذ Quicksort في C ++ ونكتب برنامجًا لفرز مصفوفة.
# تضمين باستخدام مساحة الاسم std void swap_elements (int * a، int * b) {int temp = * a * a = * b * b = temp} قسم int (مصفوفة int [] ، int start_index ، int end_index) {int pivot = المصفوفة [end_index] int i = (start_index - 1) لـ (int j = start_index j<= end_index- 1 j++) { if (array[j] <= pivot) { i++ swap_elements(&array[i], &array[j]) } } swap_elements(&array[i + 1], &array[end_index]) return (i + 1) } void quickSort(int array[], int start_index, int end_index) { if (start_index < end_index) { int partition_index = partition(array, start_index, end_index) quickSort(array, start_index, partition_index - 1) quickSort(array, partition_index + 1, end_index) } } void printArray(int array[], int number) { int i cout<<'Sorted Array: ' for (i = 0 i < number i++) cout << array[i] << ' ' cout << endl } int main() { int Hello[30] int i int NumberofElements cout<>تكلفة NumberofElements<<'Enter the elements one by one: ' for(i=0i>مرحبًا [i]} الترتيب السريع (مرحبًا ، 0 ، NumberofElements-1) printArray (مرحبًا ، NumberofElements) إرجاع 0}
 انتاج: 
c ++ دمج خوارزمية الفرز
 تعقيد الوقت 
فلنتحدث عن الجانب الأكثر أهمية في أي خوارزمية فرز ، مثل تعقيد الوقت. يخبرنا عن أداء الخوارزمية في سيناريوهات مختلفة. يمكن أن تساعدنا هذه القيم في تحديد ما إذا كان بإمكاننا استخدام هذه الخوارزمية لتطبيقنا.
 أفضل حالة- على)
 متوسط ​​الحالة- (نلوجن)
 الحالة الأسوأ- على2)
بهذا ، نصل إلى نهاية هذا Quicksort في مقالة C ++. إذا كنت ترغب في معرفة المزيد ، تحقق من   بواسطة Edureka ، شركة تعليمية موثوقة عبر الإنترنت. تم تصميم دورة تدريب وإصدار شهادات Java J2EE و SOA من Edureka لتدريبك على مفاهيم Java الأساسية والمتقدمة جنبًا إلى جنب مع العديد من أطر Java مثل Hibernate & Spring.
 لديك سؤال لنا؟ يرجى ذكر ذلك في قسم التعليقات في هذه المدونة وسنعاود الاتصال بك في أقرب وقت ممكن.