logo

TechCodeview

Algoritmi de sortare

A Algoritm de sortare este folosit pentru a rearanja o anumită matrice sau o listă de elemente în funcție de un operator de comparare a elementelor. Operatorul de comparație este utilizat pentru a decide noua ordine a elementelor din structura de date respectivă.

De exemplu: Lista de caractere de mai jos este sortată în ordine crescătoare a valorilor lor ASCII. Adică, caracterul cu o valoare ASCII mai mică va fi plasat primul decât caracterul cu o valoare ASCII mai mare.



Cuprins

cele mai bune mașini din lume

Ce este Sortarea?

Triere se referă la rearanjarea unei matrice date sau a unei liste de elemente în funcție de un operator de comparare a elementelor. Operatorul de comparație este utilizat pentru a decide noua ordine a elementelor din structura de date respectivă. Sortarea înseamnă reordonarea tuturor elementelor fie în ordine crescătoare, fie în ordine descrescătoare.



Terminologie de sortare:

  • Sortare pe loc: Utilizează un algoritm de sortare in loc spațiu constant pentru producerea rezultatului (modifică numai matricea dată). Sortează lista doar prin modificarea ordinii elementelor din listă. Exemple: Sortare selecție, Sortare cu bule, Sortare prin inserție și Sortare grămadă.
  • Sortare internă: Sortarea internă este atunci când toate datele sunt plasate în memoria principala sau memorie interna . În sortarea internă, problema nu poate prelua intrarea peste dimensiunea sa. Exemplu: sortare heap, sortare cu bule, sortare prin selecție, sortare rapidă, sortare shell, sortare prin inserție.
  • Sortare externă: Sortarea externă este atunci când toate datele care trebuie sortate nu pot fi plasate în memorie la un moment dat, sortarea se numește sortare externă. Sortarea externă este utilizată pentru cantitatea masivă de date. Exemple: sortare îmbinare, sortare etichetă, sortare polifazată, sortare cu patru benzi, sortare radix externă etc.
  • Sortare stabilă: Când două aceleași date apar în la fel Ordin în datele sortate fără modificarea poziţiei lor se numeşte sortare stabilă. Exemple: Sortare prin îmbinare, Sortare prin inserare, Sortare cu bule.
  • Sortare instabilă: Când două aceleași date apar în diferit Ordin în datele sortate se numește sortare instabilă. Exemple: Sortare rapidă, Sortare heap, Sortare Shell .

Caracteristicile algoritmilor de sortare:

  • Complexitatea timpului: Complexitatea timpului, o măsură a cât timp durează rularea unui algoritm, este utilizată pentru a clasifica algoritmii de sortare. Performanța în cel mai rău caz, mediu și cel mai bun caz a unui algoritm de sortare poate fi utilizată pentru a cuantifica complexitatea în timp a procesului.
  • Complexitatea spațiului: Algoritmii de sortare au, de asemenea, complexitate spațială, care este cantitatea de memorie necesară pentru a executa algoritmul.
  • Stabilitate: Se spune că un algoritm de sortare este stabil dacă ordinea relativă a elementelor egale este păstrată după sortare. Acest lucru este important în anumite aplicații în care trebuie menținută ordinea inițială a elementelor egale.
  • Sortare in loc: Un algoritm de sortare in loc este unul care nu necesită memorie suplimentară pentru sortarea datelor. Acest lucru este important atunci când memoria disponibilă este limitată sau când datele nu pot fi mutate.
  • Adaptivitate: Un algoritm de sortare adaptiv este unul care profită de ordinea preexistentă a datelor pentru a îmbunătăți performanța.

Aplicații ale algoritmilor de sortare:

  • Algoritmi de căutare: Sortarea este adesea un pas crucial în algoritmii de căutare, cum ar fi căutarea binară, Căutarea ternară, unde datele trebuie sortate înainte de a căuta un anumit element.
  • Management de date: Sortarea datelor facilitează căutarea, preluarea și analiza.
  • Optimizarea bazei de date: Sortarea datelor în bazele de date îmbunătățește performanța interogărilor.
  • Învățare automată: Sortarea este utilizată pentru a pregăti datele pentru antrenarea modelelor de învățare automată.
  • Analiza datelor: Sortarea ajută la identificarea modelelor, a tendințelor și a valorii aberante în seturile de date. Joacă un rol vital în analiza statistică, modelarea financiară și alte domenii bazate pe date.
  • Sisteme de operare: Algoritmii de sortare sunt utilizați în sistemele de operare pentru sarcini precum programarea sarcinilor, gestionarea memoriei și organizarea sistemului de fișiere.

Elementele de bază ale algoritmilor de sortare:

  • Introducere în tehnicile de sortare – Structura datelor și tutoriale de algoritm
  • Aplicații, avantaje și dezavantaje ale algoritmului de sortare
  • Care este un exemplu real de sortare?
  • Ce este Sortarea în DSA | Sortarea sensului

Algoritmi de sortare:

Implementări biblioteci:

Probleme ușoare la sortare:

  • Sortați elementele după frecvență
  • Sortați o matrice de 0, 1 și 2
  • Sortați numerele stocate pe diferite mașini
  • Sortați o matrice în formă de undă
  • Verificați dacă oricare două intervale se suprapun într-un anumit set de intervale
  • Cum se sortează o serie de date în C/C++?
  • Sortarea șirurilor folosind Bubble Sort
  • Găsiți elementele lipsă dintr-un interval
  • Sortați o matrice în funcție de numărul de biți setați
  • Sortați elementele par plasate în ordine crescătoare și impare în ordine descrescătoare
  • Sortați o matrice când sunt sortate două jumătăți
  • Sortarea numerelor întregi mari
  • Sortați o listă legată de 0, 1 și 2

Probleme medii la sortare:

  • Număr de inversiuni în Array folosind Merge Sort
  • Găsiți Lungimea minimă Unsorted Subbarray, sortare care face ca matricea completă să fie sortată
  • Sortați o matrice aproape sortată (sau sortată K).
  • Sortați n numere în intervalul de la 0 la n^2 – 1 în timp liniar
  • Sortați o matrice în conformitate cu ordinea definită de o altă matrice
  • Găsiți punctul în care intervalele maxime se suprapun
  • Găsiți o permutare care cauzează cel mai rău caz de sortare fuzionare
  • Sortați vectorul perechilor în ordine crescătoare în C++
  • Schimbări minime pentru a face două matrice identice
  • Problema distribuirii ciocolatei
  • Permutați două tablouri astfel încât suma fiecărei perechi să fie mai mare sau egală cu K
  • Bucket Sort Pentru a sorta o matrice cu numere negative
  • Sortați o matrice în ordine crescătoare
  • Convertiți o matrice în formă redusă folosind Vector de perechi
  • Cea mai mică diferență triplet de la trei matrice
  • Verificați dacă este posibil să sortați o matrice cu schimbarea condiționată a adiacentelor permise

Probleme grele la sortare:

  • Găsiți Surpasser Count al fiecărui element din matrice
  • Numărați aparițiile distincte ca o consecință
  • Numărați numărul minim de subseturi (sau subsecvențe) cu numere consecutive
  • Alegeți k elemente de matrice astfel încât diferența de maxim și minim să fie minimizată
  • Schimb minim necesar pentru a converti arborele binar în arborele de căutare binar
  • K-lea cel mai mic element după eliminarea unor numere întregi din numerele naturale
  • Diferența maximă între frecvența a două elemente, astfel încât elementul care are o frecvență mai mare este, de asemenea, mai mare
  • Schimbări minime pentru a ajunge la matricea permutată cu cel mult 2 poziții permise
  • Aflați dacă este posibil să faceți aceleași elemente de matrice folosind un număr extern
  • Sortați o matrice după aplicarea ecuației date
  • Imprimați o matrice de șiruri în ordine sortată fără a copia un șir în altul

Link-uri rapide:

  • „Probleme de practică” la sortare
  • „Chestionare” despre sortare

Recomandat:

  • Aflați structura datelor și algoritmi | Tutorial DSA