برنامج Python لدمج الفرز

باعتبارها لغة برمجة متعددة النماذج مع نهج تصميم منظم وموجه للكائنات ونحو وقواعد بسيطة وغير مرتبة ، تبرز Python بسرعة كلغة مفضلة للمبرمجين الذين يعملون في مشاريع متفاوتة التعقيد والحجم.

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

ما هو دمج الفرز؟

إنها تقنية فرز للأغراض العامة تمكن المستخدمين من أخذ مجموعة بيانات عشوائية من أي نوع ومن أي مصدر وتقسيمها إلى مراحل متكررة حتى يتم تقسيمها في النهاية إلى مكوناتها الفردية - وهي تقنية تكرارية ، يشار إليها عادةً باسم ' طريقة فرق تسد.

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

تحقق من دوراتنا الأخرى في علوم البيانات في upGrad.

تقنية فرق تسد

خذ ، على سبيل المثال ، مجموعة بيانات عشوائية من الحروف الأبجدية: N ، H ، V ، B ، Q ، D ، Z ، R.

الخطوة 1 : يتم تقسيم مجموعة البيانات الأصلية أولاً إلى مجموعتين على النحو التالي:

N ، H ، V ، B Q ، D ، Z ، R

الخطوة 2 : يتم تقسيم كل من المصفوفتين الناتج إلى مزيد من التقسيم الفرعي على النحو التالي:

N ، H V ، B Q ، D Z ، R

الخطوة 3 : أخيرًا ، يتم إجراء المزيد من المصفوفات الأربعة حتى يتم تقسيم سلسلة البيانات بالكامل إلى مكوناتها الفردية:

N H V B Q D Z R

ثم تنعكس العملية ، وتبدأ الآن نقاط البيانات الفردية في الاندماج بطريقة مرحلية. ولكن خلال عملية الدمج هذه ، يتم تقييم كل عنصر في كل مصفوفة فرعية ومبادلتها بحيث يتم ترتيبها في تسلسل منطقي (ترتيب أبجدي) ، على النحو التالي:

الخطوة 4 : تندمج العناصر الفردية في أزواج أثناء تبديل المراكز كما هو مطلوب لتشكيل التسلسل الصحيح:

H ، N B ، V D ، Q R ، Z

الخطوة 5 : تستمر العملية العودية للدمج والفرز في التكرار التالي:

B ، H ، N ، V D ، Q ، R ، Z

الخطوة 6 : يتم أخيرًا إعادة تكوين سلسلة البيانات بأكملها بترتيبها الأبجدي المنطقي:

B ، D ، H ، N ، Q ، R ، V ، Z

استكشف دوراتنا الشهيرة في علوم البيانات

دمج عمليات الفرز

هناك طريقتان لتطبيق Merge Sort في Python. النهج التنازلي والنهج التصاعدي.

نهج من أعلى إلى أسفل:

النهج الأكثر شيوعًا هو النهج الموصوف أعلاه. يستغرق وقتًا أطول ويستهلك قدرًا أكبر من الذاكرة ، وبالتالي فهو غير فعال عند العمل مع مجموعات بيانات أصغر. ومع ذلك ، فهي أكثر موثوقية ، لا سيما عند تطبيقها على مجموعات البيانات الكبيرة.

اقرأ مقالاتنا الشهيرة في علوم البيانات

إدخال رمز:

def merge_sort (inp_arr):

الحجم = len (inp_arr)

إذا كان الحجم> 1:

الوسط = الحجم // 2

left_arr = inp_arr (: وسط)

rIght_arr = inp_arr (وسط :)

merge_sort (left_arr)

دمج _sort (right_arr)

أنا = 0

ي = 0

ك = 0

(حيث i و j هما المكرران لاجتياز النصفين الأيمن والأيسر من سلسلة البيانات ، على التوالي ، و k هو مكرر سلسلة البيانات الإجمالية).

left_size = len (left_arr)

الحجم الصحيح = len (right_arr)

بينما أنا <left_size و j <الحق الحجم:

إذا left_arr (i) <right_arr (j):

inp_arr (k) - left_arr (i)

أنا> = 1

آخر:

inp_arr (k) = right_arr (j)

ي + = 1

ك + = 1

بينما أنا <left_size:

inp_arr (k) = left_arr (i)

أنا + = 1

ك + = 1

بينما j <right_size:

inp_arr (k) = right_arr (j)

ي + = 1

ك + = 1

inp_arr = (N ، H ، V ، B ، Q ، D ، Z ، R)

print (: Input Array: \ n ”)

طباعة (inp_arr)

merge_sort (inp_arr)

طباعة ("مصفوفة مرتبة: \ n")

طباعة (inp_arr)

انتاج:

صفيف الإدخال: N ، H ، V ، B ، Q ، D ، Z ، R

صفيف الإخراج: B ، D ، H ، N ، Q ، R ، V ، Z

النهج التصاعدي:

يعتبر النهج التصاعدي أسرع ، ويستهلك ذاكرة أقل ، ويعمل بكفاءة مع مجموعات بيانات أصغر ، ولكنه قد يواجه مشكلات عند العمل مع مجموعات البيانات الكبيرة. لذلك فهو أقل استخدامًا.

إدخال رمز:

دمج def (يسار ، يمين):

النتيجة = [] س ، ص = 0 ، 0

لـ k في النطاق (0 ، len (يسار) + len (يمين)):

إذا كان i == len (يسار): # إذا كان في نهاية الشوط الأول ،

result.append (يمين [j]) # أضف كل قيم النصف الثاني

ي + = 1

elif j == len (يمين): # إذا كان في نهاية الشوط الثاني ،

result.append (يسار [x]) # أضف كل قيم النصف الأول

أنا + = 1

elif right [j] <left [i]:

result.append (يمين [j])

ي + = 1

آخر:

result.append (يسار [i])

أنا + = 1

نتيجة العودة

def mergesort (ar_list):

الطول = لين (ar_list)

الحجم = 1

بينما الحجم <الطول:

size + = size # يتم التهيئة عند 2 كما هو موضح

لنقاط البيع في النطاق (0 ، الطول ، الحجم):

بدء = نقاط البيع

منتصف = نقاط البيع + int (الحجم / 2)

النهاية = نقاط البيع + الحجم

يسار = ar_list [start: mid] right = ar_list [mid: end]

ar_list [start: end] = دمج (يسار ، يمين)

العودة ar_list

ar_list = [N، H، V، B، Q، D، Z، R] طباعة (ترتيب دمج (قائمة ar))

انتاج:

صفيف الإدخال: N ، H ، V ، B ، Q ، D ، Z ، R

صفيف الإخراج: B ، D ، H ، N ، Q ، R ، V ، Z

تم تطبيق تطبيق Merge Sort على مجموعات البيانات الواقعية الأكثر تعقيدًا

دعنا نطبق النهج من أعلى إلى أسفل على أربع مركبات عشوائية للطرق الوعرة في الهند:

إدخال رمز:

فئة السيارة:

def __init __ (الذات ، العلامة التجارية ، الموديل ، السعر):

self.brand = العلامة التجارية

نموذج self.model = نموذج

self.price = السعر

def __str __ (ذاتي):

return str.format ("العلامة التجارية: {} ، الطراز: {} ، السعر: {}" ، self.brand ،

النموذج الذاتي ، السعر الذاتي)

دمج def (list1، i، j، k، comp_fun):

left_copy = list1 [i: k + 1]

r_sublist = list1 [k + 1: r + 1]

left_copy_index = 0

j_sublist_index = 0

Sorted_index = أنا

while left_copy_index <len (left_copy) وj_sublist_index <

لين (j_sublist):

if comp_fun (left_copy [left_copy_index] ، j_sublist [j_sublist_index]):

list1 [sorted_index] = left_copy [left_copy_index]

left_copy_index = left_copy_index + 1

آخر :

list1 [Sorted_index] = j_sublist [j_sublist_index]

j_sublist_index = j_sublist_index + 1

Sorted_index = Sorted_index + 1

بينما left_copy_index <len (left_copy):

list1 [sorted_index] = left_copy [left_copy_index]

left_copy_index = left_copy_index + 1

Sorted_index = Sorted_index + 1

بينما j_sublist_index <len (j_sublist):

list1 [Sorted_index] = j_sublist [j_sublist_index]

j_sublist_index = j_sublist_index + 1

Sorted_index = Sorted_index + 1

def merge_sort (list1، i، j، comp_fun):

إذا أنا> = ي:

إرجاع

ك = (أنا + ي) // 2

merge_sort (list1، i، k، comp_fun)

merge_sort (list1، k + 1، j، comp_fun)

دمج (list1، i، j، k، comp_fun)

car1 = سيارة ("جيب" ، "رانجلر" ، 0.58)

car2 = سيارة ("Ford"، "Endeavour"، 0.35)

car3 = Car ("Jaguar Land Rover"، "Range Rover Sport"، 1.76)

car4 = Car ("Mercedes Benz"، "G-class"، 2.42)

list1 = [سيارة 1 ، سيارة 2 ، سيارة 3 ، سيارة 4]

merge_sort (list1، 0، len (list1) -1، lambda carA، carB: carA.brand <carB.brand)

print ("السيارات مرتبة حسب العلامة التجارية:")

للسيارة فيالقائمة 1:

طباعة (سيارة)

طباعة ()

merge_sort (list1، 0، len (list1) -1، lambda carA، carB: carA.price <carB.price)

print ("السيارات مرتبة حسب السعر:")

للسيارة فيالقائمة 1:

طباعة (سيارة)

انتاج:

السيارات مرتبة حسب الماركة:

فورد انديفور

جاكوار لاند روفر رينج روفر سبورت

جيب رانجلر

مرسيدس بنز جي كلاس

السيارات مرتبة حسب السعر:

فورد انديفور

جيب رانجلر

جاكوار لاند روفر رينج روفر

مرسيدس بنز جي كلاس

يمكنك تعلم الجوانب النظرية والعملية لبايثون من خلال شهادة upGrad الاحترافية في علوم البيانات وتحليلات الأعمال من جامعة ميريلاند. تساعدك هذه الدورة على تعلم بايثون من البداية. حتى لو كنت جديدًا في البرمجة والترميز ، ستقدم لك upGrad دورة تحضيرية لمدة أسبوعين حتى تتمكن من التعرف على أساسيات البرمجة. ستتعرف على أدوات مختلفة مثل Python و SQL أثناء العمل في مشاريع صناعية متعددة.

خطط لوظيفتك في تطوير البرمجيات الآن!

تقدم بطلب للحصول على برنامج الشهادة المهنية في علوم البيانات وتحليلات الأعمال