Ordonarea unei colecții
Sortarea înseamnă a pune elementele unei colecții într-o anumită ordine.
Unele tipuri au o ordine naturală. Numerele sunt ordonate după valoare: 1 vine înaintea lui 2. Șirurile de caractere sunt ordonate alfabetic: "four" vine înaintea lui "one". Pentru orice altceva, sau când vrei o altă ordine, dai o ordine personalizată: o funcție de comparare care se uită la două elemente și spune care vine primul.
Tablourile au o singură metodă de sortare, sort(), iar două lucruri legate de ea se pot trece ușor cu vederea:
sort()schimbă tabloul pe loc și returnează același tablou, deci ordinea originală se pierde. Ca să o păstrezi, sortează o copie:[...words].sort().- Fără funcție de comparare,
sort()compară forma text a valorilor. Asta este în regulă pentru cuvinte, dar[10, 9, 2]iese ca[ 10, 2, 9 ], pentru că textul"10"vine înaintea textului"2". Pentru numere, transmite întotdeauna o funcție de comparare.
O funcție de comparare primește două elemente, a și b, și returnează un număr: negativ când a vine primul, pozitiv când b vine primul și 0 când sunt egale. a - b face asta pentru numere, iar a.localeCompare(b) o face pentru șiruri de caractere.
sort() este stabilă: elementele pe care funcția de comparare le consideră egale își păstrează ordinea originală.
Versiunile mai noi de Node.js au și toSorted() și toReversed(), care returnează un tablou nou și lasă originalul neatins. Exemplele de mai jos copiază tabloul manual cu [...words], ceea ce funcționează peste tot.
Exemplele de mai jos folosesc cuvintele one, two, three, four.
Ordinea naturală
Ordinea naturală este ordinea pe care un tip o are de la sine: numerele după valoare, șirurile de caractere literă cu literă.
[...words].sort() dă un tablou nou, în ordine alfabetică. Pentru ordinea descrescătoare nu există o metodă separată: sortează întâi, apoi întoarce tabloul cu reverse(). Pentru numere, funcția de comparare (a, b) => b - a face asta dintr-un singur pas.
Propriile tale tipuri de obiecte nu au o ordine naturală. Le dai una scriind o funcție de comparare care returnează un număr negativ, zero sau un număr pozitiv, aceeași regulă ca la orice altă funcție de comparare. Apoi o poți transmite lui sort() sau o poți folosi direct ca să compari două valori.
Copie sortată
[...words].sort() sortează o copie, deci words este afișat neschimbat după aceea. Ultimele două linii arată de ce numerele au nevoie de o funcție de comparare: fără una, [10, 9, 2] devine [ 10, 2, 9 ]; cu (a, b) => a - b devine [ 2, 9, 10 ].
Ieșire: program TypeScript și rezultatul capturat
const words = ['one', 'two', 'three', 'four']
// sort() schimbă tabloul pe care este apelată, deci sortează o copie a lui
const sorted = [...words].sort()
console.log(sorted)
console.log(words)
// fără funcție de comparare, sort() compară forma text a fiecărei valori
const numbers = [10, 9, 2]
console.log([...numbers].sort())
console.log([...numbers].sort((a, b) => a - b))
Sortare descrescătoare
Copia este sortată, apoi reverse() o întoarce, așa că cuvintele merg de la "two" în jos până la "four". Numerele arată calea mai scurtă pentru valori pe care le poți scădea: (a, b) => b - a sortează [10, 9, 2] direct în [ 10, 9, 2 ].
Ieșire: program TypeScript și rezultatul capturat
const words = ['one', 'two', 'three', 'four']
// sortează copia în ordine crescătoare, apoi întoarce-o
const desc = [...words].sort().reverse()
console.log(desc)
// pentru numere, o singură funcție de comparare face aceeași treabă dintr-un pas
const numbers = [10, 9, 2]
console.log([...numbers].sort((a, b) => b - a))
Un tip cu ordinea lui proprie
Version are un număr major și un număr minor. compareVersion() compară întâi major; doar când acel rezultat este 0 decide minor, pentru că || ia primul rezultat care nu este 0. Verificarea compareVersion(...) > 0 răspunde la întrebarea „este prima versiune mai mare?”.
Ieșire: program TypeScript și rezultatul capturat
type Version = {
major: number
minor: number
}
// compareVersion returnează un număr negativ, zero sau un număr pozitiv,
// exact ca funcțiile de comparare pe care le primește sort().
function compareVersion(a: Version, b: Version): number {
// || folosește primul rezultat care nu este 0: întâi major, apoi minor
return a.major - b.major || a.minor - b.minor
}
const v12: Version = { major: 1, minor: 2 }
const v13: Version = { major: 1, minor: 3 }
const v20: Version = { major: 2, minor: 0 }
const v15: Version = { major: 1, minor: 5 }
// Este 1.2 mai mare decât 1.3?
console.log(compareVersion(v12, v13) > 0)
// Este 2.0 mai mare decât 1.5?
console.log(compareVersion(v20, v15) > 0)
Ordini personalizate
O ordine personalizată este orice ordine pe care o descrii cu o funcție de comparare.
sort() primește acea funcție ca singurul ei argument. Pentru că sort() este stabilă, elementele pe care funcția le consideră egale rămân în ordinea lor originală, ceea ce este exact ce vrei când sortezi cuvintele după lungime.
O dorință des întâlnită este să sortezi după o proprietate a fiecărui element. Nu există o metodă specială pentru asta: scrie o funcție de comparare care compară acea proprietate, cu - pentru numere sau cu localeCompare() pentru șiruri de caractere.
Pentru ordinea descrescătoare, inversează a și b în comparație.
Ca să sortezi după un lucru și apoi după altul, unește două comparații cu ||. Acesta ia primul rezultat care nu este 0, deci atunci când prima comparație consideră elementele egale, a doua decide.
Sortare cu o funcție de comparare
Funcția de comparare returnează a.length - b.length. Un rezultat negativ înseamnă că a este mai scurt și vine primul, deci cuvintele ajung de la cel mai scurt la cel mai lung: [ 'c', 'bb', 'aaa' ].
Ieșire: program TypeScript și rezultatul capturat
const words = ['aaa', 'bb', 'c']
// funcția de comparare returnează a.length - b.length, deci cuvintele mai scurte vin primele
const sorted = [...words].sort((a, b) => a.length - b.length)
console.log(sorted)
Sortare după lungime
Cuvintele sunt comparate cu a.length - b.length. "one" și "two" au amândouă 3 litere; pentru că sort() este stabilă, "one" rămâne înaintea lui "two".
Ieșire: program TypeScript și rezultatul capturat
const words = ['one', 'two', 'three', 'four']
// sort() este stabilă: cuvintele de aceeași lungime își păstrează ordinea originală
const byLength = [...words].sort((a, b) => a.length - b.length)
console.log(byLength)
Sortare după ultima literă, descrescător
a[a.length - 1] este ultima literă a unui cuvânt. Literele lui b și a sunt comparate în ordine inversată, deci cuvântul cu cea mai mare ultimă literă vine primul: "four" (r), apoi "two" (o), apoi cele două cuvinte care se termină în „e”, în ordinea lor originală.
Ieșire: program TypeScript și rezultatul capturat
const words = ['one', 'two', 'three', 'four']
// compară ultimele litere, cu b înaintea lui a pentru ordine descrescătoare
const byLastLetter = [...words].sort((a, b) =>
b[b.length - 1].localeCompare(a[a.length - 1]))
console.log(byLastLetter)
Sortare după lungime, apoi alfabetic
|| compară întâi lungimile. Când două cuvinte sunt la fel de lungi, se trece la localeCompare(), care le ordonează alfabetic. Rezultatul este afișat cu join(' '), pe o singură linie: a b c aa bb aaa ccc.
Ieșire: program TypeScript și rezultatul capturat
const words = ['aaa', 'bb', 'c', 'b', 'a', 'aa', 'ccc']
// || folosește prima comparație care nu este 0: întâi lungimea, apoi alfabetul
const sorted = [...words].sort((a, b) => a.length - b.length || a.localeCompare(b))
console.log(sorted.join(' '))
Verificarea ordinii de sortare
Uneori vrei doar să știi dacă un tablou este deja sortat, fără să îl sortezi.
Nu există o verificare încorporată, dar every() scrie una într-o singură linie: fiecare element trebuie să vină după elementul dinaintea lui. Micul ajutor isSorted() de mai jos primește o funcție de comparare, așa că același ajutor poate verifica ordinea crescătoare, ordinea descrescătoare sau ordinea unei proprietăți. Pentru ordinea descrescătoare transmiți o funcție de comparare cu a și b inversate.
Verificare crescătoare și descrescătoare
isSorted() confirmă că 1, 2, 3, 4 sunt în ordine crescătoare. Același ajutor cu (a, b) => b - a confirmă că 4, 3, 2, 1 sunt în ordine descrescătoare. Elementul de la indexul 0 este întotdeauna acceptat, pentru că nu are niciun element înaintea lui.
Ieșire: program TypeScript și rezultatul capturat
// isSorted verifică fiecare pereche de vecini cu o funcție de comparare.
function isSorted<T>(items: T[], compare: (a: T, b: T) => number): boolean {
return items.every((value, i) => i === 0 || compare(items[i - 1], value) <= 0)
}
const ascending = [1, 2, 3, 4]
const descending = [4, 3, 2, 1]
console.log(isSorted(ascending, (a, b) => a - b))
// argumentele inversate verifică ordinea descrescătoare
console.log(isSorted(descending, (a, b) => b - a))
Verificarea ordinii după un câmp
Utilizatorii sunt Alice (24), Bob (31) și Charlie (29). Funcția de comparare se uită doar la age. Bob este mai în vârstă decât Charlie, deci tabloul nu este sortat după vârstă, iar răspunsul este false.
Ieșire: program TypeScript și rezultatul capturat
type User = {
name: string
age: number
}
function isSorted<T>(items: T[], compare: (a: T, b: T) => number): boolean {
return items.every((value, i) => i === 0 || compare(items[i - 1], value) <= 0)
}
const users: User[] = [
{ name: 'Alice', age: 24 },
{ name: 'Bob', age: 31 },
{ name: 'Charlie', age: 29 },
]
// sunt utilizatorii în ordinea vârstei?
console.log(isSorted(users, (a, b) => a.age - b.age))
Ordinea inversă
Inversarea pune ultimul element primul și primul element ultimul.
reverse() inversează un tablou pe loc, exact ca sort(). Ca să obții în schimb o copie inversată, inversează o copie: [...words].reverse(). Originalul își păstrează ordinea.
Copie inversată
Copia este inversată și afișată, apoi este afișat originalul, ca să se vadă că este neschimbat.
Ieșire: program TypeScript și rezultatul capturat
const words = ['one', 'two', 'three', 'four']
// reverse() lucrează tot pe loc, deci inversează o copie
const reversed = [...words].reverse()
console.log(reversed)
console.log(words)
Ordine aleatoare
Amestecarea pune elementele într-o ordine aleatoare.
Nu există o metodă de amestecare. Modul obișnuit este o buclă mică ce parcurge tabloul de la ultima poziție în jos și schimbă fiecare element cu un element de pe o poziție anterioară. Bucla schimbă tabloul pe care îl primește, deci amestecă o copie atunci când mai ai nevoie de original.
Math.random() ar da o altă ordine la fiecare rulare. De aceea, acest exemplu își pornește propriul generator cu o sămânță: două linii de aritmetică ce transformă o sămânță într-un șir de numere de la 0 până la 1. Aceeași sămânță dă întotdeauna aceeași ordine, ceea ce este util pentru teste și pentru exemple ca acesta.
Copie amestecată
Un generator cu sămânța 9 amestecă o copie a cuvintelor și afișează [ 'two', 'four', 'three', 'one' ]. Rulând programul din nou se afișează aceeași ordine, pentru că generatorul pornește de la aceeași sămânță.
Ieșire: program TypeScript și rezultatul capturat
// randomGenerator returnează o funcție care dă numere de la 0 până la 1.
// Aceeași sămânță dă mereu aceleași numere, deci rezultatul nu se schimbă.
function randomGenerator(seed: number): () => number {
let state = seed
return () => {
state = (state * 48271) % 2147483647
return state / 2147483647
}
}
const words = ['one', 'two', 'three', 'four']
const random = randomGenerator(9)
// Parcurge copia de la ultima poziție în jos și schimbă cu una anterioară.
const shuffled = [...words]
for (let i = shuffled.length - 1; i > 0; i--) {
const j = Math.floor(random() * (i + 1))
const kept = shuffled[i]
shuffled[i] = shuffled[j]
shuffled[j] = kept
}
console.log(shuffled)