Sortarea este una dintre cele mai utilizate caracteristici în programare. Și va dura timp pentru a finaliza sortarea dacă nu am folosit algoritmul corect.
În acest articol, vom discuta despre diferiți algoritmi de sortare.
Vă vom ghida prin diferiții algoritmi de sortare cu fiecare pas care vine în implementare. Partea de implementare va fi în Python. Îl puteți converti cu ușurință în orice limbă odată ce obțineți algoritmul. Aceasta este problema sintaxei limbajului.
Vom vedea diferiți algoritmi de la cel mai rău la cel mai bun în acest tutorial. Deci, nu vă faceți griji. Urmăriți articolul și implementați-le.
Să ne aprofundăm în algoritmii de sortare.
Cuprins
Sortare prin inserare
Sortarea prin inserție este unul dintre algoritmii simpli de sortare. Este ușor de implementat. Și vă va costa mai mult timp să sortați o matrice. Nu va fi folosit în majoritatea cazurilor pentru sortarea pentru matrice mai mari.
Algoritmul de sortare prin inserare menține subpărți sortate și nesortate în tabloul dat.
Sub-partea sortată conține doar primul element la începutul procesului de sortare. Vom lua un element din matricea nesortată și le vom plasa în poziția corectă în submatricea sortată.
Să vedem ilustrațiile vizuale ale sortării inserției pas cu pas cu un exemplu.
Să vedem pașii pentru implementarea sortării prin inserare.
- Inițializați matricea cu date fictive (numere întregi).
- Iterați peste matricea dată de la al doilea element.
- Luați poziția curentă și elementul în două variabile.
- Scrieți o buclă care se repetă până când apare primul element al matricei sau elementul care este mai mic decât elementul curent.
- Actualizați elementul curent cu elementul anterior.
- Scăderea poziţiei curente.
- Aici, bucla trebuie să ajungă fie la începutul matricei, fie să găsească un element mai mic decât elementul curent. Înlocuiți elementul de poziție curentă cu elementul curent.
Complexitatea temporală a sortării de inserție este O(n^2), iar complexitatea spațiului dacă O(1).
Asta e; am sortat matricea dată. Să rulăm următorul cod. Sper că ați instalat Python, dacă nu, consultați ghidul de instalare. Alternativ, puteți utiliza un compilator Python online.
def insertion_sort(arr, n): for i in range(1, n): ## current position and element current_position = i current_element = arr[i] ## iteratin until ### it reaches the first element or ### the current element is smaller than the previous element while current_position > 0 and current_element < arr[current_position - 1]: ## updating the current element with previous element arr[current_position] = arr[current_position - 1] ## moving to the previous position current_position -= 1 ## updating the current position element arr[current_position] = current_element if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] insertion_sort(arr, 9) ## printing the array print(str(arr))
Sortare selecție
Sortarea prin selecție este similară cu sortarea prin inserție, cu o ușoară diferență. Acest algoritm împarte, de asemenea, matricea în subpărți sortate și nesortate. Și apoi, la fiecare iterație, vom lua elementul minim din sub-partea nesortată și îl vom plasa în ultima poziție a sub-partea sortată.
Să sortăm ilustrații de selecție pentru o mai bună înțelegere.
Să vedem pașii pentru a implementa sortarea selecției.
- Inițializați matricea cu date fictive (numere întregi).
- Iterați peste matricea dată.
- Mențineți indicele elementului minim.
- Scrieți o buclă care iterează de la elementul curent la ultimul element.
- Verificați dacă elementul curent este mai mic decât elementul minim sau nu.
- Dacă elementul curent este mai mic decât elementul minim, atunci înlocuiți indexul.
- Avem la noi indicele elementului minim. Schimbați elementul curent cu elementul minim folosind indecși.
Complexitatea temporală a sortării selecției este O(n^2), iar complexitatea spațiului dacă O(1).
Încercați să implementați algoritmul, deoarece este similar cu sortarea prin inserție. Puteți vedea codul mai jos.
def selection_sort(arr, n): for i in range(n): ## to store the index of the minimum element min_element_index = i for j in range(i + 1, n): ## checking and replacing the minimum element index if arr[j] < arr[min_element_index]: min_element_index = j ## swaping the current element with minimum element arr[i], arr[min_element_index] = arr[min_element_index], arr[i] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] selection_sort(arr, 9) ## printing the array print(str(arr))
Sortare cu bule
Sortarea cu bule este un algoritm simplu. Schimbă elementele adiacente la fiecare iterație în mod repetat până când matricea dată este sortată.
Iterează peste matrice și mută elementul curent în următoarea poziție până când este mai mic decât elementul următor.
Ilustrațiile ne ajută să înțelegem vizual sortarea cu bule. Să-i vedem.
Să vedem pașii pentru implementarea sortării cu bule.
Complexitatea temporală a sortării cu bule este O(n^2), iar complexitatea spațială dacă O(1).
Puteți implementa cu ușurință sortarea cu bule până acum. Să vedem codul.
def bubble_sort(arr, n): for i in range(n): ## iterating from 0 to n-i-1 as last i elements are already sorted for j in range(n - i - 1): ## checking the next element if arr[j] > arr[j + 1]: ## swapping the adjucent elements arr[j], arr[j + 1] = arr[j + 1], arr[j] if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] bubble_sort(arr, 9) ## printing the array print(str(arr))
Merge Sort
Merge sort este un algoritm recursiv pentru sortarea matricei date. Este mai eficient decât algoritmii discutați anterior în ceea ce privește complexitatea timpului. Urmează abordarea divide și învinge.
Algoritmul de sortare de îmbinare împarte matricea în două jumătăți și le sortează separat. După sortarea celor două jumătăți ale matricei, le îmbină într-o singură matrice sortată.
Deoarece este un algoritm recursiv, acesta împarte matricea până când matricea devine cea mai simplă (matrice cu un element) de sortat.
E timpul pentru ilustrare. Să vedem.
Să vedem pașii pentru a implementa sortarea de îmbinare.
- Inițializați matricea cu date fictive (numere întregi).
- Scrieți o funcție numită merge pentru a îmbina sub-matrice într-o singură matrice sortată. Acceptă matricea de argumente, indicii stânga, mijloc și dreapta.
- Obțineți lungimile lungimilor sub-matricelor din stânga și din dreapta folosind indecșii dați.
- Copiați elementele din matrice în matricele din stânga și din dreapta respective.
- Iterați peste cele două sub-matrice.
- Comparați cele două elemente de sub-matrice.
- Înlocuiți elementul de matrice cu elementul mai mic din cele două sub-matrice pentru sortare.
- Verificați dacă există elemente rămase în ambele sub-matrice.
- Adăugați-le în matrice.
- Scrieți o funcție numită merge_sort cu parametrii matrice, indecși stânga și dreapta.
- Dacă indexul din stânga este mai mare sau egal cu indicele din dreapta, atunci reveniți.
- Găsiți punctul de mijloc al matricei pentru a împărți matricea în două jumătăți.
- Apelați recursiv merge_sort folosind indecșii stânga, dreapta și mijloc.
- După apelurile recursive, îmbinați matricea cu funcția de îmbinare.
Complexitatea temporală a sortării de îmbinare este O(nlogn), iar complexitatea spațială dacă O(1).
Asta este pentru implementarea algoritmului de sortare de îmbinare. Verificați codul de mai jos.
def merge(arr, left_index, mid_index, right_index): ## left and right arrays left_array = arr[left_index:mid_index+1] right_array = arr[mid_index+1:right_index+1] ## getting the left and right array lengths left_array_length = mid_index - left_index + 1 right_array_length = right_index - mid_index ## indexes for merging two arrays i = j = 0 ## index for array elements replacement k = left_index ## iterating over the two sub-arrays while i < left_array_length and j < right_array_length: ## comapring the elements from left and right arrays if left_array[i] < right_array[j]: arr[k] = left_array[i] i += 1 else: arr[k] = right_array[j] j += 1 k += 1 ## adding remaining elements from the left and right arrays while i < left_array_length: arr[k] = left_array[i] i += 1 k += 1 while j < right_array_length: j += 1 k += 1 def merge_sort(arr, left_index, right_index): ## base case for recursive function if left_index >= right_index: return ## finding the middle index mid_index = (left_index + right_index) // 2 ## recursive calls merge_sort(arr, left_index, mid_index) merge_sort(arr, mid_index + 1, right_index) ## merging the two sub-arrays merge(arr, left_index, mid_index, right_index) if __name__ == '__main__': ## array initialization arr = [3, 4, 7, 8, 1, 9, 5, 2, 6] merge_sort(arr, 0, 8) ## printing the array print(str(arr))
Concluzie
Există mulți alți algoritmi de sortare, dar mai sus sunt câțiva dintre cei utilizați frecvent. Sper că ți-a plăcut să înveți sortarea.
Apoi, aflați despre algoritmii de căutare.
Codare fericită 🙂 👨💻