Selection Sort और Insertion Sort

Python में Data Structures और Algorithms

Miriam Antona

Software engineer

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. एक पॉइंटर पहले तत्व की ओर इशारा करता है.

सबसे छोटा मान पहचानें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. एक पॉइंटर पहले तत्व की ओर इशारा करता है. पहला तत्व नारंगी है.

सबसे छोटा मान पहचानें

Selection sort

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

सबसे छोटा मान पहचानें

Selection sort

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

सबसे छोटा मान पहचानें

Selection sort

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

सबसे छोटा मान पहचानें

Selection sort

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

सबसे छोटा मान पहचानें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. एक पॉइंटर चौथे तत्व की ओर इशारा करता है. चौथा तत्व नारंगी है.

सबसे छोटा मान पहचानें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. एक पॉइंटर पाँचवें तत्व की ओर इशारा करता है. चौथा तत्व नारंगी है.

सबसे छोटा मान पहचानें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला तत्व नारंगी है. पहला और चौथा तत्व बदले जा चुके हैं.

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

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

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं, और पाँचवाँ नारंगी. दो तीर दिखाते हैं कि चौथा और पाँचवाँ तत्व बदले जाएँगे.

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं, और चौथा नारंगी. चौथा और पाँचवाँ तत्व बदले जा चुके हैं.

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा, तीसरा और चौथा तत्व नीले हैं.

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. सभी तत्व नीले हैं.

सबसे छोटा मान पहचानें
सबसे छोटे मान को पहले अन-सॉर्टेड तत्व से बदलें

Selection sort - implementation

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

    lowest = my_list[i]

    index = i

    for j in range(i + 1, list_length):

      if my_list[j] < lowest:

        index = j

        lowest = my_list[j]

    my_list[i] , my_list[index] = my_list[index] , my_list[i]

  return my_list

Selection sort - complexity

सबसे खराब स्थिति: $O(n^2)$
औसत स्थिति: $\Theta(n^2)$
सर्वोत्तम स्थिति: $\Omega(n^2)$

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला तत्व नीला है और दूसरा तत्व दूसरों से ऊपर उठा हुआ है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला तत्व नीला है और दूसरा तत्व ऊपर उठा हुआ है. पहला तत्व दाएँ शिफ्ट किया गया है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. दूसरा तत्व नीला है. ऊपर उठा हुआ तत्व अब पहली पोजीशन पर है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला और दूसरा तत्व नीले हैं.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला और दूसरा तत्व नीले हैं. तीसरा तत्व दूसरों से ऊपर उठा हुआ है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं. तीसरा तत्व दूसरों से ऊपर उठा हुआ है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं. तीसरा तत्व ऊपर उठा हुआ है. तीसरा तत्व दाएँ शिफ्ट किया गया है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं. तीसरा तत्व ऊपर उठा हुआ है. तीसरा और दूसरा तत्व दाएँ शिफ्ट किए गए हैं.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं. तीसरा तत्व ऊपर उठा हुआ है. तीसरा, दूसरा और तीसरा तत्व दाएँ शिफ्ट किए गए हैं.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा और तीसरा तत्व नीले हैं. तीसरा तत्व ऊपर उठा हुआ है. तीसरा, दूसरा और तीसरा तत्व दाएँ शिफ्ट किए गए हैं. ऊपर उठा हुआ तत्व अब पहली पोजीशन पर है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा, तीसरा और चौथा तत्व नीले हैं. पाँचवाँ तत्व दूसरों से ऊपर उठा हुआ है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा, तीसरा और चौथा तत्व नीले हैं. पाँचवाँ तत्व ऊपर उठा हुआ है. चौथा तत्व दाएँ शिफ्ट किया गया है.

Insertion sort

बिना क्रम के संख्याओं वाली सूची का योजनामूलक चित्र. पहला, दूसरा, तीसरा और चौथा तत्व नीले हैं. पाँचवाँ तत्व ऊपर उठा हुआ है. ऊपर उठा हुआ तत्व अब चौथी पोजीशन पर है.

Insertion sort - implementation

def insertion_sort(my_list):
  for i in range(1, len(my_list)):

      number_to_order = my_list[i]

      j = i - 1

      while j >= 0 and number_to_order < my_list[j]:

          my_list[j + 1] = my_list[j]

          j -= 1

      my_list[j + 1] = number_to_order

  return my_list

Insertion sort - complexity

सबसे खराब स्थिति: $O(n^2)$
औसत स्थिति: $\Theta(n^2)$
सर्वोत्तम स्थिति: $\Omega(n)$

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

Python में Data Structures और Algorithms