Sortare prin interclasare

Structuri de date și algoritmi în Python

Miriam Antona

Software engineer

Sortare prin interclasare

  • Urmează strategia divide și cucerește
    • Divide
      • împarte problema în subprobleme mai mici
    • Cucerește
      • subproblemele sunt rezolvate recursiv
    • Combină
      • soluțiile subproblemelor sunt combinate pentru a obține soluția finală
Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Lista a fost împărțită în două părți.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Lista a fost împărțită în două părți. Există două liste noi: prima conține jumătatea stângă a listei originale, iar a doua conține jumătatea dreaptă.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Listele noi au fost împărțite în două părți.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Există liste noi cu diviziunile ultimelor liste divizate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Listele noi au fost împărțite în două părți.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Există liste noi cu diviziunile ultimelor liste divizate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Listele noi au fost împărțite în două părți.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Listele noi au fost împărțite în două părți.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Elementele din ultimele liste divizate au fost sortate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Elementele din ultimele liste divizate au fost interclasate și ordonate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Elementele din ultimele liste divizate au fost interclasate și ordonate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - în acțiune

Reprezentare schematică a unei liste cu numere neordonate. Elementele din ultimele liste divizate au fost interclasate și ordonate. Toate elementele sunt sortate.

Structuri de date și algoritmi în Python

Sortare prin interclasare - implementare

def merge_sort(my_list):
  if len(my_list) > 1:

    mid = len(my_list)//2
    left_half = my_list[:mid]
    right_half = my_list[mid:]

    merge_sort(left_half)
    merge_sort(right_half)


    i = j = k = 0

    while i < len(left_half) and j < len(right_half):

      if left_half[i] < right_half[j]:

        my_list[k] = left_half[i]

        i += 1

      else:

        my_list[k] = right_half[j]

        j += 1

      k += 1

    while i < len(left_half):

      my_list[k] = left_half[i]
      i += 1
      k += 1


    while j < len(right_half):
      my_list[k] = right_half[j]
      j += 1
      k += 1

my_list = [35,22,90,4,50,20,30,40,1]
merge_sort(my_list)
print(my_list)

[1, 4, 20, 22, 30, 35, 40, 50, 90]
Structuri de date și algoritmi în Python

Sortare prin interclasare - complexitate

  • Cazul cel mai defavorabil: $O(n\log{}n)$
    • îmbunătățire semnificativă față de sortarea prin bule, prin selecție și prin inserție
    • potrivit pentru sortarea listelor mari
  • Cazul mediu: $\Theta(n\log{}n)$
  • Cazul cel mai favorabil: $\Omega(n\log{}n)$
    • alți algoritmi (ex. sortare prin bule, prin inserție) au complexitate mai bună în cazul favorabil
  • Complexitate spațială: $O(n)$
    • complexitate spațială mai mare față de alți algoritmi cu $O(1)$
  • Alte variante reduc această complexitate spațială
Structuri de date și algoritmi în Python

Să exersăm!

Structuri de date și algoritmi în Python

Preparing Video For Download...