Implementation (Part 1)
الدرس 5 من 9 في دورة Radix Sort - سلسلة DSA على Coddy.
سنقوم ببناء خوارزمية Radix Sort بدءاً من عمليتها الأساسية.
التحدي
متوسطكل تمريرة في خوارزمية Radix Sort هي عبارة عن stable counting sort (فرز بالعد مستقر) على خانة واحدة. لنقم ببناء ذلك أولاً.
اكتب دالة باسم countingSortByDigit تأخذ مصفوفة من الأعداد الصحيحة غير السالبة arr وقيمة مكانية exp (1 للآحاد، 10 للعشرات، 100 للمئات، ...)، وتعيد مصفوفة جديدة مرتبة حسب الرقم (x / exp) % 10. يجب أن يكون الفرز مستقراً (stable): أي أن العناصر التي لها نفس الرقم تحافظ على ترتيبها الأصلي.
على سبيل المثال، countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) تعيد [170, 90, 2, 802, 24, 45, 75, 66] (مرتبة حسب خانة الآحاد).
جرّب بنفسك
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, int* returnSize) {
// اكتب الكود هنا
*returnSize = arr_size;
return arr;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس Radix Sort - سلسلة DSA
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity