बबल सॉर्ट

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

Sorting algorithms

{{1}} का गहराई से अध्ययन किया
Unsorted collection को ascending/descending क्रम में sort कैसे करें
समस्याओं की complexity घट सकती है
कुछ sorting algorithms:
- bubble sort
- selection sort
- insertion sort
- merge sort
- quicksort

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है.

पहला मान दूसरे मान से बड़ा

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. पहला और दूसरा तत्व अदला-बदली किए गए हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर दूसरे तत्व पर और दूसरा तीसरे तत्व पर है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर तीसरे तत्व पर और दूसरा चौथे तत्व पर है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर तीसरे तत्व पर और दूसरा चौथे तत्व पर है. तीसरा और चौथा तत्व अदला-बदली किए गए हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर चौथे तत्व पर और दूसरा पाँचवें तत्व पर है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर चौथे तत्व पर और दूसरा पाँचवें तत्व पर है. चौथा और पाँचवां तत्व अदला-बदली किए गए हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर चौथे तत्व पर और दूसरा पाँचवें तत्व पर है. पाँचवां तत्व नीला है क्योंकि वह क्रम में है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. अंतिम तत्व नीला है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर दूसरे तत्व पर और दूसरा तीसरे तत्व पर है. अंतिम तत्व नीला है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर दूसरे तत्व पर और दूसरा तीसरे तत्व पर है. दूसरा और तीसरा तत्व अदला-बदली किए गए हैं. अंतिम तत्व नीला है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर तीसरे तत्व पर और दूसरा चौथे तत्व पर है. अंतिम तत्व नीला है.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर तीसरे तत्व पर और दूसरा चौथे तत्व पर है. अंतिम दो तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. अंतिम दो तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. पहला और दूसरा तत्व अदला-बदली किए गए हैं. अंतिम दो तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर दूसरे तत्व पर और दूसरा तीसरे तत्व पर है. अंतिम दो तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर दूसरे तत्व पर और दूसरा तीसरे तत्व पर है. अंतिम तीन तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. अंतिम तीन तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. अंतिम चार तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट

अव्यवस्थित संख्याओं की सूची का आरेख. एक पॉइंटर पहले तत्व पर और दूसरा दूसरे तत्व पर है. सभी तत्व नीले हैं.

पहला मान दूसरे मान से बड़ा
- उन्हें swap करें
दूसरा मान पहले मान से बड़ा
- कुछ नहीं

बबल सॉर्ट - इम्प्लीमेंटेशन

def bubble_sort(my_list):
  list_length = len(my_list)
  for i in range(list_length-1):
    for j in range(list_length-1-i):

      if my_list[j] > my_list[j+1]:

        my_list[j] , my_list[j+1] = my_list[j+1] , my_list[j]

  return my_list

print(bubble_sort([4,3,7,1,5]))

[1, 3, 4, 5, 7]

बबल सॉर्ट - इम्प्लीमेंटेशन

def bubble_sort(my_list):
  list_length = len(my_list)
  is_sorted = False

  while not is_sorted:

    is_sorted = True

    for i in range(list_length-1):

      if my_list[i] > my_list[i+1]:

        my_list[i] , my_list[i+1] = my_list[i+1] , my_list[i]

        is_sorted = False

    list_length -= 1

  return my_list

बबल सॉर्ट - complexity

Worst case: $O(n^2)$
Best case - non-improved version: $\Omega(n^2)$
Best case - improved version: $\Omega(n)$
Average case: $\Theta(n^2)$
बहुत असorted बड़ी lists पर प्रदर्शन कमज़ोर
अच्छा प्रदर्शन:
- बड़ी sorted/लगभग sorted lists
- छोटी lists

अभ्यास करते हैं!

Python में Data Structures और Algorithms