فرز بايثون: طرق الفرز والخوارزميات في بايثون

تعرف على كيفية استخدام وظيفة Python Sort لفرز القوائم والمصفوفات والقواميس وما إلى ذلك باستخدام طرق وخوارزميات الفرز المختلفة في Python: البيانات بترتيب تسلسلي إما بترتيب تصاعدي أو تنازلي.

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

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

في هذا البرنامج التعليمي ، سوف نفهم كيفية عمل الفرز في بايثون باستخدام خوارزميات مختلفة.

تصنيف Python

بناء جملة تصنيف Python

لإجراء الفرز ، توفر Python الوظيفة المضمنة مثل وظيفة "sort ()". يتم استخدامه لفرز عناصر البيانات لقائمة بترتيب تصاعدي أو تنازلي.

دعونا نفهم هذا المفهوم بمثال.

مثال 1:

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort() print( “ List in ascending order: ”, a ) ``` 

الإخراج:

في هذا المثال ، يتم فرز القائمة غير المرتبة المحددة بترتيب تصاعدي باستخدام وظيفة "Sort ()" .

المثال 2:

``` a = [ 3, 5, 2, 6, 7, 9, 8, 1, 4 ] a.sort( reverse = True ) print( “ List in descending order: ”, a ) ``` 

الإخراج

في المثال أعلاه ، يتم فرز القائمة غير المرتبة المحددة بترتيب عكسي باستخدام الوظيفة "فرز (عكسي = صحيح)".

الوقتضع فرز الفقاعة O (n) O (n2) O (n2) O (1) نعم نعم فرز الإدراج O (n) O (n2) O (n2) O (1) نعم نعم فرز سريع O (n log (n)) O (n log (n)) O (n2) O (N) لا نعم دمج فرز O (n log (n)) O (n log (n)) O (n log (n)) O (N) نعم لا فرز الكومة O (n log (n)) O (n log (n)) O (n log (n)) O (1) No نعم

في جدول المقارنة أعلاه "O" هو تدوين Big Oh الموضح أعلاه بينما تعني "n" و "N" حجم الإدخال .

الأسئلة المتداولة

Q # 1) ما هو الفرز () في بايثون؟

الإجابة: في بايثون Sort () هي وظيفة تُستخدم لفرز القوائم أو المصفوفات بترتيب معين. تسهل هذه الوظيفة عملية الفرز أثناء العمل في المشاريع الكبيرة. إنه مفيد جدًا للمطورين.

س # 2) كيف تفرز في بايثون؟

الإجابة: توفر Python تقنيات فرز متنوعة تُستخدم لفرز العنصر. على سبيل المثال ، الفرز السريع ، ودمج الفرز ، وفرز الفقاعة ، وفرز الإدراج ، وما إلى ذلك. جميع تقنيات الفرز فعالة وسهلة الفهم.

Q # 3) كيف تعمل بايثون نوع () العمل؟

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

الخاتمة

في البرنامج التعليمي أعلاه ، ناقشنا تقنية الفرز في Python مع تقنيات الفرز العامة.

  • فرز الفقاعات
  • فرز الإدراج
  • فرز سريع

لقد تعلمنا عن تعقيدات الوقت والمزايا وأمبير ؛ سلبيات. قمنا أيضًا بمقارنة جميع التقنيات المذكورة أعلاه.

تعقيد خوارزميات الفرز

تعقيد الوقت هو مقدار الوقت الذي يستغرقه الكمبيوتر لتشغيل خوارزمية معينة. يحتوي على ثلاثة أنواع من حالات تعقيد الوقت.

  • أسوأ حالة: أقصى وقت يستغرقه الكمبيوتر لتشغيل البرنامج.
  • متوسط ​​الحالة: الوقت الذي يستغرقه الكمبيوتر بين الحد الأدنى والحد الأقصى لتشغيل البرنامج.
  • أفضل حالة: الحد الأدنى للوقت الذي يستغرقه الكمبيوتر لتشغيل البرنامج. إنها أفضل حالة لتعقيد الوقت.

تدوين التعقيد

تدوين Big Oh ، O: تدوين Big oh هو الطريقة الرسمية لنقل الحد الأعلى من وقت تشغيل الخوارزميات. يتم استخدامه لقياس تعقيد الوقت في أسوأ الحالات أو نقول أكبر قدر من الوقت الذي تستغرقه الخوارزمية لإكماله. الطريقة الرسمية لنقل الحد الأدنى من وقت تشغيل الخوارزميات. يتم استخدامه لقياس تعقيد الوقت في أفضل حالة أو نقول مقدار الوقت الممتاز الذي تستغرقه الخوارزمية.

تدوين ثيتا ، : تدوين ثيتا هو الطريقة الرسمية للتعبير كلا الحدين ، أي الحد الأدنى والأعلى للوقت الذي تستغرقه الخوارزمية لإكمالها.

طرق الفرز في بايثون

فرز الفقاعات

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

دعونا نأخذ مثالاً لفهم هذه التقنية:

  • يتم تزويدنا بمصفوفة تحتوي على العناصر " 10 ، 40 ، 7 ، 3 ، 15 ". الآن ، نحتاج إلى ترتيب هذه المصفوفة بترتيب تصاعدي باستخدام تقنية الفرز الفقاعي في بايثون.
    • الخطوة الأولى هي ترتيب المصفوفة بالترتيب المحدد.
    • في "التكرار 1" ، نقارن العنصر الأول من المصفوفة مع العناصر الأخرى واحدًا تلو الآخر.
    • تصف الأسهم الحمراء مقارنة العناصر الأولى مع العناصر الأخرى في المصفوفة.
    • إذا لاحظت أن الرقم "10" أصغر من "40" ، فإنه يظل كما هو مكان ولكن العنصر التالي "7" أصغر من "10". ومن ثم يتم استبداله ويأتي في المقام الأول.
    • سيتم تنفيذ العملية المذكورة أعلاه مرارًا وتكرارًا لفرز العناصر.

    • في "التكرار 2" تتم مقارنة العنصر الثاني مع العناصر الأخرى في المصفوفة.
    • إذا كان العنصر المقارن صغيرًا ، فسيتم يتم استبدالها ، وإلا فإنها ستبقى في نفس المكان.

    • في "التكرار 3" تتم مقارنة العنصر الثالث مع العناصر الأخرى في المصفوفة.

    • في الماضي "التكرار 4" يتم مقارنة العنصر الأخير الثاني مع العناصر الأخرى في المصفوفة.
    • فيهذه الخطوة يتم فرز المصفوفة بترتيب تصاعدي.

برنامج لفرز الفقاعات

``` def Bubble_Sort(unsorted_list): for i in range(0,len(unsorted_list)-1): for j in range(len(unsorted_list)-1): if(unsorted_list[j]>unsorted_list[j+1]): temp_storage = unsorted_list[j] unsorted_list[j] = unsorted_list[j+1] unsorted_list[j+1] = temp_storage return unsorted_list unsorted_list = [5, 3, 8, 6, 7, 2] print("Unsorted List: ", unsorted_list) print("Sorted List using Bubble Sort Technique: ", Bubble_Sort(unsorted_list)) ``` 
0> الإخراج

التعقيد الزمني لفرز الفقاعة

  • أسوأ حالة: أسوأ تعقيد زمني لفرز الفقاعة هو O ( n 2).
  • متوسط ​​الحالة: متوسط ​​التعقيد الزمني لفرز الفقاعة هو O ( n 2).
  • أفضل حالة: أفضل تعقيد زمني لفرز الفقاعة هو O (n).

المزايا

  • يستخدم في الغالب ويسهل تنفيذه.
  • يمكننا تبديل عناصر البيانات دون استهلاك مساحة تخزين قصيرة المدى.
  • يتطلب أقل space.

العيوب

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

الإدراج فرز

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

لنأخذ مثالاً

  • مصفوفة تحتوي على العناصر "100 ، 50 ، 30 ، 40 ، 10".
  • أولاً ، نرتب المصفوفة ونبدأ في المقارنة
  • في الخطوة الأولى ، تتم مقارنة "100" بالعنصر الثاني "50". يتم تبديل "50" بـ "100" لأنه أكبر.
  • في الخطوة الثانية ، مرة أخرى ، تتم مقارنة العنصر الثاني "100" بالعنصر الثالث "30" ويتم تبديله.
  • الآن ، إذا لاحظت أن "30" تأتي في المقام الأول لأنها مرة أخرى أصغر من "50".
  • ستحدث المقارنة حتى آخر عنصر من المصفوفة وفي النهاية ، سنحصل على فرز البيانات.

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

``` def InsertionSort(array): for i in range(1, len(array)): key_value = array[i] j = i-1 while j >= 0 and key_value  array[j] : array[j + 1] = array[j] j -= 1 array[j + 1] = key_value array = [11, 10, 12, 4, 5] print("The unsorted array: ", array) InsertionSort(array) print ("The sorted array using the Insertion Sort: ") for i in range(len(array)): print (array[i]) ``` 

الإخراج

تعقيد الوقت لفرز الإدراج

  • أسوأ حالة: أسوأ تعقيد زمني لفرز الإدراج هو O ( n 2).
  • متوسط ​​الحالة: متوسط ​​التعقيد الزمني لفرز الإدراج هو O ( n 2).
  • أفضل حالة: أفضل تعقيد زمني لفرز الإدراج هو O (n).

المزايا

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

العيوب

  • ليس من المفيد فرز عدد كبير من عناصر البيانات.
  • عند مقارنتها بتقنيات الفرز الأخرى ، فإنها لا تعمل بشكل جيد.

دمج الفرز

تستخدم طريقة الفرز هذه طريقة divide and conquer لفرز العناصر بترتيب معين. أثناء الفرز بمساعدة دمج الفرز ، فإن ملفيتم تقسيم العناصر إلى نصفين ثم يتم فرزها. بعد فرز جميع الأنصاف ، يتم ضم العناصر مرة أخرى لتشكيل ترتيب مثالي.

لنأخذ مثالاً لفهم هذه التقنية

  • مصفوفة "7 ، 3 ، 40 ، 10 ، 20 ، 15 ، 6 ، 5". تحتوي المصفوفة على 7 عناصر. إذا قسمناها إلى نصفين (0 + 7/2 = 3)
  • في الخطوة الثانية ، سترى أن العناصر مقسمة إلى جزأين. كل عنصر فيه 4 عناصر. الرجوع إلى الخطوة لا. 4 في الصورة.
  • الآن ، سنقوم بفرز العناصر والبدء في ضمها كما كنا مقسمين.
  • في الخطوة رقم. 5 إذا لاحظت أن 7 أكبر من 3 ، فسنقوم بتبادلها وضمها في الخطوة التالية والعكس صحيح.
  • في النهاية ، ستلاحظ أن المصفوفة الخاصة بنا يتم فرزها بترتيب تصاعدي.

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

``` def MergeSort(arr): if len(arr) > 1: middle = len(arr)//2 L = arr[:middle] R = arr[middle:] MergeSort(L) MergeSort(R) i = j = k = 0 while i  len(L) and j  len(R): if L[i]  R[j]: arr[k] = L[i] i += 1 else: arr[k] = R[j] j += 1 k += 1 while i  len(L): arr[k] = L[i] i += 1 k += 1 while j  len(R): arr[k] = R[j] j += 1 k += 1 def PrintSortedList(arr): for i in range(len(arr)): print(arr[i],) print() arr = [12, 11, 13, 5, 6, 7] print("Given array is", end="\n") PrintSortedList(arr) MergeSort(arr) print("Sorted array is: ", end="\n") PrintSortedList(arr) ``` 

الإخراج

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

  • أسوأ حالة: أسوأ تعقيد زمني لفرز الدمج هو O ( n log ( n )).
  • متوسط ​​الحالة: متوسط ​​تعقيد الوقت لفرز الدمج هو O ( n log ( n )).
  • أفضل حالة: أفضل تعقيد زمني لفرز الدمج هو O ( n log ( n )).

المزايا

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

الفرز السريع

يستخدم الفرز السريع مرة أخرى طريقة التقسيم والقهر لفرز عناصر القائمة أو مجموعة. يستهدف العناصر المحورية ويصنف العناصر وفقًا للعنصر المحوري المحدد.

على سبيل المثال

  • يتم تزويدنا بمصفوفة تحتوي على العناصر "1 ، 8،3،9،4،5،7 ".
  • لنفترض أن" 7 "عنصر تجريبي.
  • الآن سنقسم المصفوفة بطريقة تجعل يحتوي الجانب الأيسر على العناصر الأصغر من العنصر المحوري "7" والجانب الأيمن يحتوي على العناصر الأكبر من العنصر المحوري "7".
  • لدينا الآن صفيفتان "1،3،4،5" "و" 8 ، 9 ".
  • مرة أخرى ، علينا تقسيم كلتا المصفوفتين تمامًا كما فعلنا أعلاه. الاختلاف الوحيد هو أن العناصر المحورية تتغير.
  • نحتاج إلى تقسيم المصفوفات حتى نحصل على العنصر الفردي في المصفوفة.
  • في النهاية ، اجمع كل العناصر المحورية في a تسلسل من اليسار إلى اليمين وسوف تحصل على الترتيبمجموعة.

برنامج للفرز السريع

``` def Array_Partition( arr, lowest, highest ): i = ( lowest-1 ) pivot_element = arr[ highest ] for j in range( lowest, highest ): if arr[ j ] = pivot_element: i = i+1 arr[ i ], arr[ j ] = arr[ j ], arr[ i ] arr[ i+1 ], arr[ highest ] = arr[ highest ], arr[ i+1 ] return ( i+1 ) def QuickSort( arr, lowest, highest ): if len( arr ) == 1: return arr if lowest  highest: pi = Array_Partition( arr, lowest, highest ) QuickSort( arr, lowest, pi-1 ) QuickSort( arr, pi+1, highest ) arr = [ 9, 6, 7, 8, 0, 4 ] n = len( arr ) print( " Unsorted array: ", arr ) QuickSort( arr, 0, n-1 ) print( " Sorted array using Quick Sort: " ) for i in range( n ): print( " %d " % arr[ i ] ) ``` 

الإخراج

تعقيد الوقت للفرز السريع

  • أسوأ حالة: أسوأ تعقيد زمني للفرز السريع هو O ( n 2).
  • متوسط ​​الحالة: متوسط ​​التعقيد الزمني للفرز السريع هو O ( n log ( n ) ).
  • أفضل حالة: أفضل تعقيد زمني للفرز السريع هو O ( n log ( n )).

المزايا

  • تُعرف بأنها أفضل خوارزمية فرز في بايثون.
  • وهي مفيدة أثناء التعامل مع كمية كبيرة من البيانات.
  • لا يتطلب مساحة إضافية.

العيوب

  • يشبه تعقيد الحالة الأسوأ تعقيدات فرز الفقاعات و نوع الإدراج.
  • طريقة الفرز هذه ليست مفيدة عندما يكون لدينا بالفعل قائمة مرتبة.

فرز الكومة

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

على سبيل المثال:

  • يتم تزويدنا بمصفوفة تحتوي على العناصر "40 ، 100 ، 30 ، 50 ، 10".
  • في "الخطوة 1" صنعنا شجرة وفقًا لـ وجود العناصر في المصفوفة.

  • في " الخطوة 2" نقوم بعمل كومة قصوى أي لترتيب العناصر بترتيب تنازلي. سوف أعظم عنصرفي الجزء العلوي (الجذر) ويوجد أصغر عنصر في الجزء السفلي (العقد الطرفية). تصبح المصفوفة المحددة "100 ، 50 ، 30 ، 40 ، 10".

  • في "الخطوة 3" ، نحن نقوم بعمل الحد الأدنى من الكومة حتى نتمكن من إيجاد الحد الأدنى من عناصر المصفوفة. من خلال القيام بذلك ، نحصل على الحد الأقصى والحد الأدنى من العناصر.

  • في "الخطوة 4" بتنفيذ نفس الخطوات نحصل على المصفوفة المرتبة.

برنامج لفرز الكومة

``` def HeapSortify( arr, n, i ): larger_element = i left = 2 * i + 1 right = 2 * i + 2 if left  n and arr[ larger_element ]  arr[ left ]: larger_element = left if right  n and arr[ larger_element ]  arr[ right ]: larger_element = right if larger_element != i: arr[ i ], arr[ larger_element ] = arr[ larger_element ], arr[ i ] HeapSortify( arr, n, larger_element ) def HeapSort( arr ): n = len( arr ) for i in range( n//2 - 1, -1, -1 ): HeapSortify( arr, n, i ) for i in range( n-1, 0, -1 ): arr[ i ], arr[ 0 ] = arr[ 0 ], arr[ i ] HeapSortify( arr, i, 0 ) arr = [ 11, 10, 12, 4, 5, 6 ] print( " The unsorted array is: ", arr ) HeapSort( arr ) n = len( arr ) print( " The sorted array sorted by the Heap Sort: " ) for i in range( n ): print( arr[ i ] ) ``` 

الإخراج

تعقيد الوقت لفرز الكومة

  • أسوأ حالة: أسوأ تعقيد زمني لفرز الكومة هو O ( n log ( n )).
  • متوسط ​​الحالة: متوسط ​​التعقيد الزمني لفرز الكومة هو O ( n log ( n )).
  • أفضل حالة: أفضل تعقيد زمني لفرز الكومة هو O ( n log ( n )).

المزايا

  • يستخدم في الغالب بسبب إنتاجيته.
  • يمكنه يتم تنفيذها كخوارزمية موضعية.
  • لا تتطلب مساحة تخزين كبيرة.

العيوب

  • يلزم مساحة لـ فرز العناصر.
  • يجعل الشجرة لفرز العناصر.

مقارنة بين تقنيات الفرز

طريقة الفرز أفضل تعقيد لوقت الحالة متوسط ​​تعقيد وقت الحالة تعقيد وقت الحالة الأسوأ تعقيد المسافة الاستقرار في -
التمرير إلى الأعلى