Sortarea colecțiilor în Go

Ordonarea unei colecții

Sortarea înseamnă să pui elementele unei colecții într-o anumită ordine.

Unele tipuri au o ordine naturală. Numerele sunt ordonate după valoare: 1 vine înainte de 2. Șirurile de caractere sunt ordonate alfabetic: "four" vine înainte de "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 dintre ele vine primul.

Go sortează slice-uri cu pachetul slices:

slices.Sort() sortează un slice în ordine naturală. Îl modifică pe loc: ordinea originală se pierde.
slices.Sorted() (Go 1.23) întoarce un slice nou, sortat, și lasă originalul așa cum era. Îi dai slices.Values(s), care parcurge elementele lui s.
slices.SortFunc() sortează pe loc folosind propria ta funcție de comparare.

Mai vechea funcție sort.Slice() din pachetul sort face aceeași treabă cu o funcție „less” care întoarce true sau false. Codul nou folosește de obicei slices.

Exemplele de mai jos folosesc patru cuvinte scurte.

Sintaxa funcției de comparare pentru SortFunc

T reprezintă tipul elementelor. Funcția de comparare primește două elemente și întoarce un număr: negativ când a vine primul, pozitiv când b vine primul și 0 când sunt egale. cmp.Compare(a, b) din pachetul cmp dă exact un astfel de număr pentru numere și pentru șiruri de caractere.

slices.SortFunc(items, func(a, b T) int {
  // return a negative number if a comes first,
  // a positive number if b comes first, 0 if equal
})

Ordinea naturală

Ordinea naturală este ordinea pe care un tip o are de la sine: numerele după valoare, șirurile de caractere literă cu literă.

slices.Sorted(slices.Values(s)) dă un slice nou, în ordine naturală. Pentru ordinea descrescătoare nu există o funcție separată: sortezi mai întâi, apoi întorci slice-ul cu slices.Reverse().

Tipurile tale proprii nu au o ordine naturală. În Go îi adaugi una scriind pe struct o metodă Compare care întoarce un număr negativ, zero sau un număr pozitiv, după aceeași regulă ca o funcție de comparare. Apoi poți să dai metoda aceea lui slices.SortFunc() sau să o folosești direct ca să compari două valori.

Copie sortată

slices.Sorted() creează un slice nou, sortat alfabetic. Slice-ul original words este afișat după aceea, ca să se vadă că nu s-a schimbat.

Ia cuvintele one, two, three, four. Fă un slice nou sortat în ordine naturală (alfabetică) cu slices.Sorted, așa încât slice-ul original să nu fie schimbat. Afișează slice-ul sortat, apoi afișează slice-ul original.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele one, two, three, four. Fă un slice nou sortat în ordine naturală (alfabetică) cu slices.Sorted, așa încât slice-ul original să nu fie schimbat. Afișează slice-ul sortat, apoi afișează slice-ul original.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // slices.Sorted întoarce un slice nou, sortat; words rămâne așa cum era.
  sorted := slices.Sorted(slices.Values(words))

  fmt.Println(sorted)
  fmt.Println(words)
}

Sortare descrescătoare

Copia este sortată, apoi slices.Reverse() o întoarce, așa că vin cuvintele de la "two" în jos până la "four".

Ia cuvintele one, two, three, four. Fă o copie sortată cu slices.Sorted, apoi întoarce-o cu slices.Reverse, așa încât cuvintele să fie în ordine alfabetică descrescătoare. Afișează rezultatul.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele one, two, three, four. Fă o copie sortată cu slices.Sorted, apoi întoarce-o cu slices.Reverse, așa încât cuvintele să fie în ordine alfabetică descrescătoare. Afișează rezultatul.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Sortează o copie, apoi întoarce-o.
  desc := slices.Sorted(slices.Values(words))
  slices.Reverse(desc)

  fmt.Println(desc)
}

Un tip cu ordinea lui proprie

Version are un număr Major și un număr Minor. Metoda lui Compare compară întâi Major; doar când acestea sunt egale decide Minor. cmp.Or() alege primul rezultat care nu este 0. Verificarea Compare(...) > 0 răspunde la întrebarea „prima versiune este mai mare?”.

Definește un struct Version cu câmpurile Major și Minor și dă-i o metodă Compare care întoarce un număr negativ, zero sau un număr pozitiv, comparând întâi Major și apoi Minor. Afișează dacă versiunea 1.2 este mai mare decât 1.3, apoi dacă 2.0 este mai mare decât 1.5, folosind Compare(...) > 0.

> Ieșire: program Go și rezultatul capturat

Prompt

Definește un struct Version cu câmpurile Major și Minor și dă-i o metodă Compare care întoarce un număr negativ, zero sau un număr pozitiv, comparând întâi Major și apoi Minor. Afișează dacă versiunea 1.2 este mai mare decât 1.3, apoi dacă 2.0 este mai mare decât 1.5, folosind Compare(...) > 0.

package main

import (
  "cmp"
  "fmt"
)

type Version struct {
  Major int
  Minor int
}

// Compare întoarce un număr negativ, zero sau un număr pozitiv,
// la fel ca funcțiile de comparare folosite de slices.SortFunc.
func (v Version) Compare(other Version) int {
  return cmp.Or(
    cmp.Compare(v.Major, other.Major),
    cmp.Compare(v.Minor, other.Minor),
  )
}

func main() {
  // Este 1.2 mai mare decât 1.3?
  fmt.Println(Version{1, 2}.Compare(Version{1, 3}) > 0)

  // Este 2.0 mai mare decât 1.5?
  fmt.Println(Version{2, 0}.Compare(Version{1, 5}) > 0)
}

Ordini personalizate

O ordine personalizată este orice ordine pe care o descrii cu o funcție de comparare.

slices.SortFunc() sortează un slice pe loc cu funcția aceea. Dacă două elemente se compară ca fiind egale, ordinea lor nu este garantată. slices.SortStableFunc() păstrează elementele egale în ordinea lor originală. Folosește-o când acest lucru contează, de exemplu când sortezi cuvinte după lungime.

O dorință des întâlnită este să sortezi după o proprietate a fiecărui element. Go nu are o funcție specială pentru asta: scrii o funcție de comparare care compară acea proprietate, de obicei cu cmp.Compare().

Pentru ordinea descrescătoare, schimbă între ele a și b în comparație: cmp.Compare(b, a) în loc de cmp.Compare(a, b).

Ca să sortezi după un lucru și apoi după altul, combină două comparații cu cmp.Or(). Aceasta întoarce primul rezultat care nu este 0. Dacă prima comparație spune că elementele sunt egale, a doua decide.

Sortare cu o funcție de comparare

Funcția de comparare întoarce len(a) - len(b). Un rezultat negativ înseamnă că a este mai scurt și vine primul, așa că la final cuvintele sunt de la cel mai scurt la cel mai lung.

Ia cuvintele aaa, bb, c. Sortează-le cu slices.SortFunc folosind o funcție de comparare care întoarce len(a) - len(b), așa încât cuvintele mai scurte să vină primele. Afișează rezultatul.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele aaa, bb, c. Sortează-le cu slices.SortFunc folosind o funcție de comparare care întoarce len(a) - len(b), așa încât cuvintele mai scurte să vină primele. Afișează rezultatul.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"aaa", "bb", "c"}

  // Șirurile mai scurte vin primele.
  slices.SortFunc(words, func(a, b string) int {
    return len(a) - len(b)
  })

  fmt.Println(words)
}

Sortare după lungime

Cuvintele sunt comparate după lungime cu cmp.Compare(len(a), len(b)). "one" și "two" au amândouă 3 litere; sortarea stabilă păstrează "one" înaintea lui "two".

Ia cuvintele one, two, three, four. Sortează-le după lungime cu slices.SortStableFunc și cmp.Compare pe lungimi, așa încât cuvintele de aceeași lungime să își păstreze ordinea originală. Afișează rezultatul.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele one, two, three, four. Sortează-le după lungime cu slices.SortStableFunc și cmp.Compare pe lungimi, așa încât cuvintele de aceeași lungime să își păstreze ordinea originală. Afișează rezultatul.

package main

import (
  "cmp"
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Sortare stabilă: cuvintele de lungime egală își păstrează ordinea originală.
  slices.SortStableFunc(words, func(a, b string) int {
    return cmp.Compare(len(a), len(b))
  })

  fmt.Println(words)
}

Sortare după ultima literă, descrescător

a[len(a)-1] este ultima literă a unui cuvânt. Literele lui b și a sunt date lui cmp.Compare() în ordine schimbată, așa că vine primul cuvântul cu cea mai mare ultimă literă: "four" (r), apoi "two" (o), apoi cele două cuvinte care se termină în „e”, în ordinea lor originală.

Ia cuvintele one, two, three, four. Sortează-le după ultima literă în ordine descrescătoare: folosește slices.SortStableFunc cu cmp.Compare, dând ultima literă a lui b înaintea ultimei litere a lui a. Afișează rezultatul.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele one, two, three, four. Sortează-le după ultima literă în ordine descrescătoare: folosește slices.SortStableFunc cu cmp.Compare, dând ultima literă a lui b înaintea ultimei litere a lui a. Afișează rezultatul.

package main

import (
  "cmp"
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Compară ultimele litere, cu b și a schimbate între ele pentru ordine descrescătoare.
  slices.SortStableFunc(words, func(a, b string) int {
    return cmp.Compare(b[len(b)-1], a[len(a)-1])
  })

  fmt.Println(words)
}

Sortare după lungime, apoi alfabetic

cmp.Or() compară mai întâi lungimile. Când două cuvinte sunt la fel de lungi, se trece la strings.Compare(), care le ordonează alfabetic.

Ia cuvintele aaa, bb, c, b, a, aa, ccc. Sortează-le mai întâi după lungime și apoi alfabetic, folosind slices.SortFunc cu cmp.Or ca să combini cmp.Compare pe lungimi și strings.Compare pe cuvinte. Afișează rezultatul.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele aaa, bb, c, b, a, aa, ccc. Sortează-le mai întâi după lungime și apoi alfabetic, folosind slices.SortFunc cu cmp.Or ca să combini cmp.Compare pe lungimi și strings.Compare pe cuvinte. Afișează rezultatul.

package main

import (
  "cmp"
  "fmt"
  "slices"
  "strings"
)

func main() {
  words := []string{"aaa", "bb", "c", "b", "a", "aa", "ccc"}

  // cmp.Or folosește prima comparație care nu este 0: întâi lungimea, apoi alfabetul.
  slices.SortFunc(words, func(a, b string) int {
    return cmp.Or(
      cmp.Compare(len(a), len(b)),
      strings.Compare(a, b),
    )
  })

  fmt.Println(words)
}

Verificarea ordinii sortate

Uneori vrei doar să știi dacă un slice este deja sortat, fără să îl sortezi.

slices.IsSorted() întoarce true când slice-ul este în ordine naturală crescătoare. slices.IsSortedFunc() face același lucru cu propria ta funcție de comparare. Go nu are IsSortedDescending: dai o funcție de comparare cu a și b schimbate între ele.

Ca să verifici ordinea după o singură proprietate, cum ar fi vârsta unui utilizator, compară acea proprietate în interiorul funcției.

Verificare crescătoare și descrescătoare

slices.IsSorted() confirmă că 1, 2, 3, 4 sunt în ordine crescătoare. slices.IsSortedFunc() cu cmp.Compare(b, a) confirmă că 4, 3, 2, 1 sunt în ordine descrescătoare.

Verifică dacă numerele 1, 2, 3, 4 sunt în ordine crescătoare cu slices.IsSorted și afișează răspunsul. Apoi verifică dacă 4, 3, 2, 1 sunt în ordine descrescătoare cu slices.IsSortedFunc și o funcție de comparare care schimbă între ele a și b, și afișează acel răspuns.

> Ieșire: program Go și rezultatul capturat

Prompt

Verifică dacă numerele 1, 2, 3, 4 sunt în ordine crescătoare cu slices.IsSorted și afișează răspunsul. Apoi verifică dacă 4, 3, 2, 1 sunt în ordine descrescătoare cu slices.IsSortedFunc și o funcție de comparare care schimbă între ele a și b, și afișează acel răspuns.

package main

import (
  "cmp"
  "fmt"
  "slices"
)

func main() {
  ascending := []int{1, 2, 3, 4}
  descending := []int{4, 3, 2, 1}

  fmt.Println(slices.IsSorted(ascending))

  // Argumentele schimbate între ele verifică ordinea descrescătoare.
  fmt.Println(slices.IsSortedFunc(descending, func(a, b int) int {
    return cmp.Compare(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, așa că slice-ul nu este sortat după vârstă.

Definește un struct User cu Name și Age. Fă un slice cu Alice 24, Bob 31 și Charlie 29. Folosește slices.IsSortedFunc cu cmp.Compare pe vârste ca să verifici dacă utilizatorii sunt sortați după vârstă și afișează răspunsul.

> Ieșire: program Go și rezultatul capturat

Prompt

Definește un struct User cu Name și Age. Fă un slice cu Alice 24, Bob 31 și Charlie 29. Folosește slices.IsSortedFunc cu cmp.Compare pe vârste ca să verifici dacă utilizatorii sunt sortați după vârstă și afișează răspunsul.

package main

import (
  "cmp"
  "fmt"
  "slices"
)

type User struct {
  Name string
  Age  int
}

func main() {
  users := []User{{"Alice", 24}, {"Bob", 31}, {"Charlie", 29}}

  // Sunt utilizatorii în ordinea vârstei?
  fmt.Println(slices.IsSortedFunc(users, func(a, b User) int {
    return cmp.Compare(a.Age, b.Age)
  }))
}

Ordinea inversă

Inversarea pune ultimul element primul și primul element ultimul.

slices.Reverse() inversează un slice pe loc. Ca să obții în schimb o copie inversată, copiază mai întâi slice-ul cu slices.Clone() și inversează copia. Originalul își păstrează ordinea.

Copie inversată

Copia este inversată și afișată, apoi este afișat originalul, ca să se vadă că nu s-a schimbat.

Ia cuvintele one, two, three, four. Copiază slice-ul cu slices.Clone și inversează copia cu slices.Reverse, așa încât originalul să rămână la fel. Afișează copia inversată, apoi afișează originalul.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele one, two, three, four. Copiază slice-ul cu slices.Clone și inversează copia cu slices.Reverse, așa încât originalul să rămână la fel. Afișează copia inversată, apoi afișează originalul.

package main

import (
  "fmt"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Inversează o copie, ca originalul să își păstreze ordinea.
  reversed := slices.Clone(words)
  slices.Reverse(reversed)

  fmt.Println(reversed)
  fmt.Println(words)
}

Ordine aleatoare

Amestecarea pune elementele într-o ordine aleatoare.

Pachetul math/rand din Go are o funcție Shuffle(). Îi dai numărul de elemente și o funcție de interschimbare; ea apelează funcția de interschimbare pentru perechi aleatoare de poziții. La fel ca slices.Reverse(), lucrează pe loc, așa că amestecă o copie făcută cu slices.Clone() dacă mai ai nevoie de original.

O sursă aleatoare creată cu rand.New(rand.NewSource(seed)) dă aceeași ordine „aleatoare” de fiecare dată când programul rulează cu acel seed. Este util pentru teste și pentru exemple ca acesta. Fără un seed fix, ordinea se schimbă la fiecare rulare.

Copie amestecată

O sursă aleatoare cu seed-ul 7 amestecă o copie a cuvintelor. Funcția de interschimbare schimbă între ele elementele de pe pozițiile i și j.

Ia cuvintele one, two, three, four. Creează o sursă aleatoare cu seed-ul 7 folosind rand.New(rand.NewSource(7)). Amestecă o copie a slice-ului făcută cu slices.Clone, folosind metoda Shuffle cu o funcție de interschimbare. Afișează copia amestecată.

> Ieșire: program Go și rezultatul capturat

Prompt

Ia cuvintele one, two, three, four. Creează o sursă aleatoare cu seed-ul 7 folosind rand.New(rand.NewSource(7)). Amestecă o copie a slice-ului făcută cu slices.Clone, folosind metoda Shuffle cu o funcție de interschimbare. Afișează copia amestecată.

package main

import (
  "fmt"
  "math/rand"
  "slices"
)

func main() {
  words := []string{"one", "two", "three", "four"}

  // Un seed fix dă aceeași ordine „aleatoare” la fiecare rulare.
  r := rand.New(rand.NewSource(7))

  shuffled := slices.Clone(words)
  r.Shuffle(len(shuffled), func(i, j int) {
    shuffled[i], shuffled[j] = shuffled[j], shuffled[i]
  })

  fmt.Println(shuffled)
}