Comparații
Interschimbări
Trecere

  • În curs de inserare
  • Comparate
  • Interschimbate
  • Partea sortată

Mai multe despre sortarea prin inserție

Sortarea prin inserție

Sortarea prin inserție funcționează așa cum mulți oameni își aranjează cărțile de joc în mână. Păstrează o parte sortată la începutul listei, ia următoarea valoare și o împinge înapoi peste fiecare valoare mai mare, până își găsește locul. Redați sortarea la orice viteză sau parcurgeți-o câte o comparație și urmăriți contoarele de comparații, interschimbări și treceri. Apăsați Redare pentru a urmări sortarea sau Pas și Înapoi pentru a avansa câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde. Casetele numără comparațiile, interschimbările și trecerile. Alegeți câte bare sunt, cum încep sau introduceți propriile numere. Cu tabla selectată, săgețile avansează câte un pas, bara de spațiu pornește și pune pauză, iar Home și End sar la început și la sfârșit.

Cum funcționează

  1. Alegeți câte bare sunt și cum încep: aleatoriu, aproape sortate, inversate sau cu puține valori distincte. Sau introduceți propriile numere.
  2. Apăsați Redare sau folosiți Pas și Înapoi ca să avansați câte o comparație. Trageți glisorul pentru pași ca să săriți oriunde în sortare.
  3. Încercați o listă aproape sortată și una inversată și comparați câte comparații necesită fiecare.

Cum funcționează sortarea prin inserție

Prima valoare singură formează o parte sortată. Luați a doua valoare și comparați-o cu cea dinaintea ei; dacă aceea e mai mare, interschimbați-le și continuați să comparați și să interschimbați până când valoarea dinainte nu e mai mare sau valoarea ajunge la început. Acum primele două valori sunt în ordine. Faceți la fel cu a treia valoare, cu a patra și așa mai departe până la sfârșitul listei.

Rapidă pe liste aproape sortate

Fiecare trecere se oprește la prima valoare care nu e mai mare, așa că o valoare aflată deja aproape de locul ei costă doar una sau două comparații. O listă sortată necesită n − 1 comparații și nicio interschimbare; o listă inversată, cel mai rău caz, necesită n(n − 1)/2 din fiecare. Numărul de interschimbări este mereu egal cu numărul de inversiuni din lista inițială, adică perechile aflate în ordine greșită. De aceea sortarea prin inserție e folosită des pentru liste scurte sau aproape sortate și în interiorul unor sortări mai rapide, pentru a termina bucățile mici.

Întrebări frecvente

Cum funcționează sortarea prin inserție?

Construiește o parte sortată la începutul listei. Fiecare trecere ia următoarea valoare și o mută înapoi peste fiecare valoare mai mare dinaintea ei, până își găsește locul. După trecerea k, primele k + 1 valori sunt în ordine, deși o valoare ulterioară mai poate fi inserată între ele.

Câte comparații și interschimbări face sortarea prin inserție?

Numărul de interschimbări este mereu egal cu numărul de inversiuni din lista inițială: zero pentru o listă sortată, n(n − 1)/2 pentru una inversată. Comparațiile sunt interschimbările plus cel mult una pe trecere, deci între n − 1 și n(n − 1)/2.

De ce e rapidă sortarea prin inserție pe liste aproape sortate?

Pentru că o trecere se oprește imediat ce întâlnește o valoare care nu e mai mare. Când fiecare valoare e aproape de locul ei final, fiecare trecere e scurtă, iar întreaga sortare durează un timp apropiat de n.

Este sortarea prin inserție stabilă?

Da. O valoare trece doar peste valori strict mai mari, așa că valorile egale nu se depășesc niciodată și își păstrează ordinea inițială.

Numerele mele sunt trimise undeva?

Nu. Sortarea rulează în browserul dumneavoastră, iar ultimele setări rămân în stocarea locală a acestui browser.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Mergi la editor