Algorithms بالعربي

Quicksort مقدمة اتعرضنا في الفصول اللي عدت لأكتر من algorithm بيحل مشكلة ال sorting , بداية من ال Insertion sort وال Merge sort في الفصل التاني , واخر حاجة في الفصل السادس اتعرضنا لل Heap sort , في الفصل ده بإذن الله هنتعرض لل Quicksort algorithm , وهنشوف إنه أفضل algorithm شفناة لغاية دلوقتي , أولا ال Quicksort فيه ميزة ال sort in place زي ال Heap sort وعكس ال Merge sort , واحنا عارفين إن sort in place معناها إنه بيرتب في نفس ال data structure اللي فيها مجموعة الأرقام , وبمعنى أكثر دقة ال algorithm بيكون sort in place لما بيكون بيحتاج عدد constant من أماكن تخزين إضافية , يعني لو فيه algorithm بيحتاج يحجز array من 10 أرقام بالتحديد ( عدد constant) كسعة تخزين إضافية أثناء تنفيذه فهو مازال sort in place , أما لو بيحتاج يحجز array من عدد n / 2 ( حيث إن n دخل ال algorithm) فهنا n / 2 مش constant وبالتالي ال algorithm مش sort in place. بالرغم من إن ال Quicksort ال worst-case running time بتاعه بيساوي Θ(n 2 ) وده asymptotically كبير جدا , وده لو فاكرين هو ال worst-case

Heapsort مقدمة اتعرضنا في الباب الأول لل insertion sort algorithm وقلنا ان أهم ميزة فيه هي الـ storage لانه sort in place يعني بيرتب في نفس الـ array مش بيحتاج يحجز memory زيادة ولكن مشكلته ان الـ running time بتاعه O(n 2 ) , واتعرضنا لل merge sort algorithm وقلنا ان أهم ميزة فيه هي الـ speed لان الـ running time بتاعه O(nlgn) ولكن مشكلته انه مش sort in place لانه بيحتاج يحجز memory زيادة عن الـ array اللي بيرتبها ( الـ algorithm بيكون sort in place لو بيحجز في الـ memory عدد أماكن زيادة عن الـ data structure بتاعته متزدش عن انها constant لكن لو بيحجز عدد متناسب مع الدخل يعني n أو n/2 أو lgn فده ميعتبرش sort in place) , في الفصل ده هنتعرض لل heapsort algorithm وده algorithm بيجمع الميزة اللي في الـ insertion sort بانه sort in place والميزة اللي في الـ merge sort بان الـ running time بتاعه O(nlgn) . الـ heapsort بيقدم design approach جديدة غير الـ incremental بتاعة الـ insertion sort وغير الـ divide-and-conquer بتاعة الـ merge sort , الـ design approach الجدي