خوارزميات تمهيدية
في هذه الصفحة 8 موضوعات
نص الدروس والتمارين باللغة الإنجليزية، بينما تبقى واجهة الموقع وعناوين الدروس بالعربية.
نظرة عامة
الموضوعات
- البحث الخطي
- البحث الثنائي
- الترتيب الفقاعي (bubble sort)
- الترتيب بالاختيار (selection sort)
- أساسيات التعقيد الزمني
تعلّم أولًا
73 دقيقة قراءة · 4 ساعة تدريب (تقدير)
مخرجات التعلم
- Implement linear search and binary search and state when binary search applies.
- Implement bubble sort and selection sort and trace them on a small array.
- Count the operations of each algorithm for small inputs and compare growth informally.
الدروس
المختبر والتمارين
Lab
BEG-017-LAB1 · Race the algorithms
Outcomes: 1–3 · Time: ~2 h
- Implement
linearSearchandbinarySearch. - Build sorted arrays of 1,000, 100,000, and 10,000,000 elements.
- Time both searches (target missing, worst case) with
System.nanoTime(); repeat a few times. - Present a results table and write a short explanation of the trend.
Acceptance: correct implementations; written explanation of the trend.
Exercises (assessment: five exercises including tracing a sort by hand)
| ID | Outcome | Task |
|---|---|---|
| BEG-017-EX01 | 1 | Implement linearSearch(int[] a, int target) returning the index or -1. |
| BEG-017-EX02 | 1 | Trace binary search for 23 in [2, 5, 8, 12, 16, 23, 38]; state when binary search applies. |
| BEG-017-EX03 | 2 | Trace bubble sort by hand on [5, 1, 4, 2], showing the array after each pass. |
| BEG-017-EX04 | 2 | Implement selection sort and test it on an empty and a one-element array. |
| BEG-017-EX05 | 3 | Add a comparison counter to linear search and bubble sort; report counts for n = 10, 20, 40 and describe the growth. |
أظهر الحلول
- EX01 The loop from L02.
- EX02 low 0, high 6, mid 3 (12 < 23) so low 4; mid 5 (23) found at index 5. It applies only when the data is sorted.
- EX03 After pass 1:
[1, 4, 2, 5]; pass 2:[1, 2, 4, 5]; pass 3: no swaps, sorted. - EX04 Code from L05; for empty and one-element input the loops do not run, which is correct.
- EX05 Linear worst case: 10, 20, 40 (doubles). Bubble: 45, 190, 780 (about four times when n doubles).
- The informal growth comparison is also in the lab explanation.
الاختبار
Outcomes: O1 searching · O2 sorting · O3 counting steps.
اختبار ذاتي لك: لا توجد درجات، ولا يُحفظ أو يُرسل أي شيء. اختر إجابة ثم تحقق منها، ويمكنك المحاولة مرة أخرى كما تشاء.
الجزء العملي
Five exercises BEG-017-EX01 to EX05 (including the hand trace of a sort) plus the race lab. Pass: at least four exercises correct, correct implementations, and a written trend explanation.
أخطاء شائعة
Binary search on unsorted data; integer overflow in (low + high) / 2 (mention); off-by-one in loop bounds.
التقييم
5 exercises including tracing a sort by hand.
الصلة بالمسار الوظيفي
Formalized in BEG-039; interview staple at Junior level.