اذا كنت راغبا في تعلم البرمجة بشكل عام، فلا مفر من تعلم الخوارزميات. الخوارزميات تعتبر اساس معظم التقنيات الحديثة ان لم تكن اهم اساسها. ويعتبر حجر البناء الاساسي للخوارزميات هي خوارزميات البحث والترتيب – Sorting and Searching – في هذا المقال سنناقش باختصار خوارزمية الترتيب وانواعها ومميزاتها ومتى تصلح للاستخدام.
تحدثنا في مناسبة سابقة عن خوارزميات البحث، يمكنك الاطلاع من هنا
تعقيد الوقت – Time Complexity
قبل مناقشة اي نوع من انواع الخوارزميات، يجب ان تكون ملم ببعض مفاهيم الخاصة بالخوارزميات. كنا قد تحدثنا في مناسبة لاحقة عن مفهوم Time Complexity، ولكن باختصار، هو كمية الوقت التي يحتاجها الكود للمعالجة او التشغيل، ويعتبر هو احد اهم المقاييس التي تقاس بها مدى جودة الكود الخاص بك.
يمكننا تطبيق مفهوم تعقيد الوقت بشكل عام على اي نوع من انواع الكود، لأن – بشكل ما – كل كود هو خوارزمية خاصة. ولكن عندما نذكر الخوارزميات على وجه الخصوص، فيجب عليك معرفة تعقيد الوقت لكل خوارزمية ما ستستخدمها. وكيفية قياسها وكيف تعمل.
خوارزمية الترتيب
اكبر تحديان يواجها المبرمج اثناء كتابته للكود هما الذاكرة العشوائية RAM والوقت الذي سينفذ فيه الكود. يهتم فرع هيكلة البيانات Data Structures بترتيب الذاكرة ويبحث دائما عن الطرق الامثل لاستخدامها. اما الخوارزميات فتهتم بتعقيد الوقت الذي يحدد بشكل عام كفاءة الكود. في حالة استخدام خوارزمية الترتيب، فالفكرة ببساطة هي كيفية ترتيب البيانات في الذاكرة العشوائية في اقل وقت ممكن لضمان كفاءة الكود.
تخيل معي الاتي، مدير شركة ما قرر فحص مرتبات 500 موظف يعمل بشركته. فكر بتلك المشكلة من جانب تقني، وبدون استخدام خوارزميات، كيف يمكنني ترتيب مرتبات 500 موظف ليظهروا بشكل تنازلي او تصاعدي؟ قد يبدو الحل المنطقي وللوهلة الاولى هو البحث خلال مرتبات الموظفين ومقارنتهم ببعضهم البعض للحصول على اعلى مرتب، ثم وضعه في اول المصفوفة، واستكمال هذه العملية حتى تترتب جميع المرتبات.
هنا يظهر احد اهم اساسيات تصميم الخوارزميات، مصطلح سيناريو الحالة الاسوأ وسيناريو الحالة الاحسن. ماذا لو كان اعلى مرتب هو اخر عنصر في المصفوفة؟ وماذا لو كان اقل مرتب هو اخر عنصر بالمصفوفة؟
انواع خوارزميات الترتيب وتعقيد الوقت لكل منهم
| Algorithm | Best | Average | Worst |
|---|---|---|---|
| Quick Sort | Ω(n log(n)) | Θ(n log(n)) | O(n^2) |
| Bubble Sort | Ω(n) | Θ(n^2) | O(n^2) |
| Merge Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) |
| Insertion Sort | Ω(n) | Θ(n^2) | O(n^2) |
| Selection Sort | Ω(n^2) | Θ(n^2) | O(n^2) |
| Heap Sort | Ω(n log(n)) | Θ(n log(n)) | O(n log(n)) |
| Radix Sort | Ω(nk) | Θ(nk) | O(nk) |
| Bucket Sort | Ω(n+k) | Θ(n+k) | O(n^2) |
