Podczas omawiania funkcji sortowania dostępnych w poszczególnych językach programowania skupimy się na dostępnych w nich klasach i funkcjach wbudowanychfunkcja wbudowanafunkcjach wbudowanych, związanych z algorytmami sortowania.

Biblioteka standardowa C++

using namespace std;

qsort(), cstdlib

Pierwszą funkcją, którą się zajmiemy, będzie funkcja qsort() zawarta w pliku nagłówkowym <cstdlib>. Wspomniany nagłówek można rozwinąć do C Standard Library, co oznacza, że jest to funkcja odziedziczona jeszcze z języka C. Funkcja implementuje algorytm sortowania szybkiego korzystający z metody „dziel i zwyciężaj”. Jest to algorytm niestabilnystabilny algorytm sortowanianiestabilny, czyli nie gwarantuje zachowania początkowej kolejności elementów równych, a więc dla argumentów równych ich porządek jest niezdefiniowany. Służy do porządkowania tablic lub innych kontenerów danychkontener danychkontenerów danych.

Więcej naa temat tego algorytmu znajdziesz w e‑materiale Sortowanie szybkiePpzx1YyemSortowanie szybkie.

#include <iostream>
#include <cstdlib>

using namespace std;

int porownaj(const void* a, const void* b) {
    int arg1 = *((const int*)a);
    int arg2 = *((const int*)b);

    if (arg1 < arg2) return -1; // jeśli a < b
    if (arg1 > arg2) return 1;  // jeśli a > b
    return 0;                   // jeśli równe
}

int main() {
    const int rozmiar = 6;
    int tablica[rozmiar] = {500, 400, 425, -500, 0, 5};

    qsort(tablica, rozmiar, sizeof *tablica, porownaj);
    for (int i = 0; i < rozmiar; i++) {
        cout << tablica[i] << endl;
    }
}

-500
0
5
400
425
500

Wywołanie omawianej funkcji w zaprezentowanym programie ma postać qsort(tablica, rozmiar, sizeof tablica, porownaj);.

Kolejne argumenty to:

• tablica – wskaźnik do pierwszego elementu sortowanej tablicy, czyli nazwa tablicy, która w języku C++ jest takim wskaźnikiem,

• rozmiar – liczba elementów tablicy,

• sizeof *tablica – rozmiar w bajtach pojedynczego elementu tablicy zwracany przez operator sizeof,

• porownaj – funkcja używana do porównywania elementów tablicy.

Funkcja qsort() nie zwraca żadnej wartości i działa bezpośrednio na podanej tablicy, tzn. zmienia kolejność zapisanych w niej elementów. O sposobie sortowania decyduje funkcja porównująca podawana jako czwarty argument( zwana komparatoremkomparatorkomparatorem). Przeanalizujmy jej działanie.

Z jej deklaracji (int porownaj(const void* a, const void* b)) wynika, że przyjmuje ona dwa wskaźniki na wartości nieokreślonego typu. Dlatego pierwszą czynnością wewnątrz funkcji jest ustalenie typu porównywanych wartości. Przykładowa instrukcja *((const int*)a); konwertuje wskaźnik a do niemodyfikowalnego typu całkowitego za pomocą rzutowaniarzutowanie, konwersja typurzutowania. Gdybyśmy porównywali liczby zmiennoprzecinkowe, do rzutowania użylibyśmy instrukcji *((const float*)a);.

Omawiana funkcja zwraca wartość całkowitą oznaczającą wynik porównania, przy czym:

• jeżeli a < b, należy zwrócić wartość mniejszą od 0, np. -1,

• jeżeli a > b, należy zwrócić wartość większą od 0, np. 1,

• jeżeli a == b, należy zwrócić wartość 0.

#include <iostream>
#include <cstdlib>

using namespace std;

int porownaj(const void* a, const void* b) {
    int arg1 = *((const float*)a);
    int arg2 = *((const float*)b);

    if (arg1 < arg2) return 1;
    if (arg1 > arg2) return -1;
    return 0;
}

int main() {
    const int rozmiar = 6;
    float tablica[rozmiar] = { -9.23, 2.67, 0, 3.14, -23.56, 1.3 };

    qsort(tablica, rozmiar, sizeof *tablica, porownaj);
    for (int i = 0; i < rozmiar; i++) {
        cout << tablica[i] << endl;
    }
}

3.14
2.67
1.3
0
-9.23
-23.56

sort(), algorithm

Kolejna wbudowana funkcja sortująca to sort(). Jej deklaracja znajduje się w nagłówku <algorithm>. Funkcja ta wykorzystuje hybrydowy niestabilny algorytm sortowania o nazwie IntrosortintrosortIntrosort Porządek równych elementów jest nieokreślony.

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

int main() {
  const int rozmiar = 6;
  int tablica[rozmiar] = { 500, 400, 425, -500, 0, 5 };

  sort(tablica, tablica + rozmiar);
  for (int i = 0; i < rozmiar; i++) {
    cout << tablica[i] << endl;
  }
}

-500
0
5
400
425
500

Funkcja sort() w podstawowym wywołaniu porządkuje elementy klasy array lub vector niemalejąco w zakresie wyznaczanym przez pierwszy i drugi argument. Do porównywania elementów domyślnie używany jest operator <. W przypadku porządkowania tablic początek i koniec sortowanego zakresu możemy podać w różny sposób, np.:

• sort(tablica, tablica + rozmiar) – pierwszy argument jest wskaźnikiem wyznaczającym początek sortowanego zakresu, drugi argument to długość sortowanego zakresu, którą można też rozumieć jako liczbę elementów do posortowania;

• sort(&tablica[0], &tablica[rozmiar]) – obydwa argumenty są referencjami pierwszego i ostatniego sortowanego elementu podawanymi za pomocą operatora &, przy czym element wskazywany przez koniec zakresu nie jest porządkowany.

Z tego wynika, że gdybyśmy chcieli porządkować tablicę np. bez pierwszego i ostatniego elementu, możemy użyć wywołań: sort(tablica + 1, tablica + rozmiar) lub sort(&tablica[1], &tablica[rozmiar‑1]).

Jeżeli chcemy używać innego sposobu porządkowania niż domyślny lub chcemy porządkować złożone struktury lub obiekty (instancje klas użytkownika), możemy użyć własnej funkcji porównującej podawanej jako trzeci argument. Funkcja przyjmuje dwa argumenty i zwraca wartość typu bool:

• true (prawda) – jeżeli pierwszy element jest mniejszy od drugiego,

• false (fałsz) – jeżeli pierwszy element jest większy od drugiego.

#include <iostream>
#include <cstdlib>

using namespace std;

int porownaj(const void* a, const void* b) {
    int arg1 = *((const int*)a);
    int arg2 = *((const int*)b);
    
    if (arg1 < arg2) return -1;
    if (arg1 > arg2) return 1;
    
    return 0;
    }

    int main() {
    const int rozmiar = 6;
    int tablica[rozmiar] = { 500, 400, 425, -500, 0, 5 };
    
    
    int tab_parzyste[rozmiar];
    int tab_nieparzyste[rozmiar];
    
    int l = 0, k = 0;
    
    for (int i = 0; i < rozmiar; i++) {
        if (tablica[i] % 2 == 0) {
            tab_parzyste[l] = tablica[i];
            l++;
        }
        else {
            tab_nieparzyste[k] = tablica[i];
            k++;
        }
    }
    
    qsort(tab_parzyste, l, sizeof * tab_parzyste,porownaj);
    
    qsort(tab_nieparzyste, k, sizeof * tab_nieparzyste, porownaj);
    
    for (int i = 0; i < k; i++) {
        cout << tab_nieparzyste[i] << " ";
    }
    for (int i = 0; i < l; i++) {
        cout << tab_parzyste[i] << " ";
    }
    
    cout << endl;
    
}

5 425 -500 0 400 500

#include <iostream>
#include <algorithm>
#include <climits>

using namespace std;

bool porownaj(int a, int b) {
    if ((a % 2 == 0) & (b % 2 == 1)) {
        return true;
    }
    return false;
}

int main() {
    const int rozmiar = 6;
    int tablica[rozmiar] = { 1, 2, 3, 4, 5, 6};

    sort(tablica, &tablica[rozmiar], porownaj);
    for (int i = 0; i < rozmiar; i++) {
        cout << tablica[i] << " ";
    }
    cout << endl;
}

2 4 6 1 3 5

stable_sort(), algorithm

Jeżeli zależy nam na sortowaniu stabilnymstabilny algorytm sortowaniastabilnym, np. kiedy porządkujemy złożone struktury lub obiekty, powinniśmy używać funkcji stable_sort(), która do porządkowania wykorzystuje algorytm sortowania przez scalanie.

Więcej na temat tego algorytmu znajdziesz w e‑materiale Sortowanie przez scalaniePNHdnGJ4ISortowanie przez scalanie.

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct uczen {
    string imie;
    int ocena;
};

bool porownaj(uczen u1, uczen u2) {
    return u1.ocena > u2.ocena;
}

int main() {
    const int rozmiar = 5;
    uczen tablica[rozmiar] = { {"Adam", 3}, {"Ewa", 5}, {"Anna", 3}, {"Olga", 5}, {"Jacek", 3} };

    stable_sort(tablica, &tablica[rozmiar], porownaj);
    for (int i = 0; i < rozmiar; i++) {
        cout << tablica[i].imie << " " << tablica[i].ocena << endl;
    }
}

Funkcja porównująca porownaj() jako argumenty otrzymuje dwie struktury zawierające imię i ocenę ucznia. Funkcja zwraca wartość true, jeżeli ocena pierwszego ucznia jest większa od oceny drugiego. W ten sposób otrzymamy uporządkowanie nierosnące według ocen. Funkcja stable_sort() gwarantuje zachowanie stabilności tego sortowania.

Wynik działania programu:

Ewa 5
Olga 5
Adam 3
Anna 3
Jacek 3

Warto zwrócić uwagę, że porządek wejściowy uczniów o takich samych ocenach został zachowany.

Klasy i metody w języku Java

Arrays.sort()

W przypadku języka Java wbudowane metody sortujące znajdziemy w klasie Arrays z pakietu pakietu java.util.Arrays. Jedną z nich jest metoda sort().

import java.util.Arrays;

public class Przyklad1 {

    public static void main(String[] args) {
        int [] tablica1 = {500, 400, 425, -500, 0, 5};
        Arrays.sort(tablica1);

        int [] tablica2 = {500, 400, 425, -500, 0, 5};
        Arrays.sort(tablica2, 1, 5);

        System.out.println(Arrays.toString(tablica1));
        System.out.println(Arrays.toString(tablica2));
    }
}

Wynik działania programu:

[-500, 0, 5, 400, 425, 500]
[500, -500, 0, 400, 425, 5]

Wyjaśnijmy działanie zaprezentowanego programu. Język Java dopuszcza przeciążanie metodprzeciążanie metodprzeciążanie metod, dlatego możemy używać dwóch wywołań metody sortującej:

1. Arrays.sort(tablica1) – pozwala porządkować wszystkie elementy podanej jako argument tablicy niemalejąco,

2. Arrays.sort(tablica2, 1, 5) – umożliwia porządkowanie niemalejące zakresu elementów wyznaczonych przez podane indeksy, przy czym element wskazywany przez indeks końcowy nie jest brany pod uwagę.

Omawiana funkcja sort() domyślnie porządkuje podane elementy niemalejąco. Gdy chcemy zmienić porządek sortowania, musimy podać jeszcze jeden argument, czyli komparator odpowiedzialny za porównywanie poszczególnych wartości w sortowanej tablicy.

import java.util.Arrays;
import java.util.Collections;
import java.lang.Integer;

public class Przyklad2 {
    public static void main(String[] args) {
        Integer [] tablica1 = {5, 0, 500, 400, -500, 425};
        Integer [] tablica2 = {5, 0, 500, 400, -500, 425};
        
        Arrays.sort(tablica1, Collections.reverseOrder());
        Arrays.sort(tablica2, 1, 5, Collections.reverseOrder());

        System.out.println(Arrays.toString(tablica1));
        System.out.println(Arrays.toString(tablica2));
    }
}

[500, 425, 400, 5, 0, -500]
[5, 500, 400, 0, -500, 425]

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

class Uczen {
    String imie;
    int wiek;
    public Uczen(String imie, int wiek) {
        this.imie = imie;
        this.wiek = wiek;
    }
    public String toString() {
        return this.imie + " " + this.wiek;
    }
}

class Porownaj implements Comparator<Uczen> {
    public int compare(Uczen u1, Uczen u2) {
        return u1.wiek - u2.wiek;
    }
}

public class Przyklad3 {
    public static void main(String[] args) {
        Uczen [] tablica = {
            new Uczen("Adam", 16),
            new Uczen("Ewa", 18),
            new Uczen("Anna", 19),
            new Uczen("Anna", 17),
            new Uczen("Piotr", 16)
        };

        Arrays.sort(tablica, new Porownaj());

        for (int i = 0; i < tablica.length; i++ )
            System.out.println(tablica[i]);

    }
}

Adam 16
Piotr 16
Anna 17
Ewa 18
Anna 19

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;

class Uczen {
    String imie;
    int wiek;
    public Uczen(String imie, int wiek) {
        this.imie = imie;
        this.wiek = wiek;
    }
    public String toString() {
        return this.imie + " " + this.wiek;
    }
}

class Porownaj implements Comparator<Uczen> {
    public int compare(Uczen u1, Uczen u2) {
        return u2.wiek - u1.wiek;
    }
}

public class Przyklad3 {
    public static void main(String[] args) {
        Uczen [] tablica = {
            new Uczen("Adam", 16),
            new Uczen("Ewa", 18),
            new Uczen("Anna", 19),
            new Uczen("Anna", 17),
            new Uczen("Piotr", 16)
        };
        
        Arrays.sort(tablica, new Porownaj());

        for (int i = 0; i < tablica.length; i++ )
            System.out.println(tablica[i]);

    }
}

parallelSort()

W klasie Arrays zaimplementowana jest również metoda o nazwie parallelSort(), która wykorzystuje algorytm sortowania przez scalanie. Metoda ta może korzystać z wielu wątków jednocześnie, więc dla większych zbiorów danych jest zauważalnie szybsza. Przyjmuje ona identyczne argumenty jak funkcja sort(), w tej samej kolejności.

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.lang.Integer;

public class Przyklad4 {
    public static void main(String[] args) {
        int [] tablica1 = {400, -65, 23, 0, -234, 112, 345};
        Integer [] tablica2 = {400, -65, 23, 0, -234, 112, 345};

        Arrays.parallelSort(tablica1);
        Arrays.parallelSort(tablica2, 1, 6, Collections.reverseOrder());

        System.out.println(Arrays.toString(tablica1));
        System.out.println(Arrays.toString(tablica2));
    }
}

[-234, -65, 0, 23, 112, 345, 400]
[400, 112, 23, 0, -65, -234, 345]

Funkcje w języku Python

sorted()

Funkcja sorted() jest częścią biblioteki standardowej języka Python i wykorzystywana jest do porządkowania danych różnych typu. Mogą to być np. listy, krotki, ciągi znaków, słowniki czy zbiory.

Podczas sortowania funkcja korzysta z algorytmu timsorttimsorttimsort, nie modyfikuje sortowanych obiektów, ale zwraca nową posortowaną listę. Zastosowany algorytm gwarantuje stabilność sortowania.

lista = [ 3.14, -59, 32, 0, -500, 400, 1]

print(sorted(lista))
print(sorted(lista, reverse=True))

[-500, -59, 0, 1, 3.14, 32, 400]
[400, 32, 3.14, 1, 0, -59, -500]

[-3, 1, 3.14, 5, 8, 10, 18]
[18, 10, 8, 5, 3.14, 1, -3]
[-3, 1, 3.14, 5, 8, 10, 18]

lista = [5, 8, -3, 1, 10, 3.14, 18]
l2 = sorted(lista)
print(l2)
l3 = sorted(l2, reverse=True)
print(l3)
print(sorted(l3))

Funkcja sorted() umożliwia określanie własnych kryteriów sortowania za pomocą opcjonalnego argumentu key. Zapoznajmy się z przykładami.

print(sorted("Przykładowy tekst który chcemy uporządkować".split(), key=None))
print(sorted("Przykładowy tekst który chcemy uporządkować".split()))

['Przykładowy', 'chcemy', 'który', 'tekst', 'uporządkować']
['Przykładowy', 'chcemy', 'który', 'tekst', 'uporządkować']

lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

print(sorted(lista, key=lambda element: element % 2 == 0))

[1,3,5,7,9,2,4,6,8,10]

print(sorted("Przykładowy tekst który chcemy uporządkować".split(), key=len))

['tekst', 'który', 'chcemy', 'Przykładowy', 'uporządkować']

Metoda split() dzieli ciąg znaków na podciągi, wykorzystując znaki białe (spacje, tabulatory) i zwraca ich listę. Listę sortujemy, wskazując w argumencie key jako kryterium funkcję len(), która zwraca ich długość.

[1, 3, 5, 7, 9, 2, 4, 6, 8, 10]
['tekst', 'który', 'chcemy', 'Przykładowy', 'uporządkować']

lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(sorted(lista, key=lambda element: element % 2 == 0, reverse=True))

lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(sorted(lista, key=lambda element: element % 2))

print(sorted("Przykładowy tekst który chcemy uporządkować".split(), key=len, reverse=True))

Argumentu key często używa się do porządkowania danych składających się z wielu wartości. Jedna z wartości wybrana zostaje jako klucz sortowania. Takie dane zapisane mogą być w różnych strukturach, np. w krotkach lub słownikach, mogą również być atrybutami obiektów będących instancjami klas użytkownika.

Poniżej pokażemy przykłady sortowania danych uczniów składających się z imion i wieku niemalejąco według wieku ucznia.

krotki = [
    ('Adam', 16),
    ('Ewa', 18),
    ('Anna', 19),
    ('Anna', 17),
    ('Piotr', 16)
]

print(sorted(krotki, key=lambda uczen: uczen[1]))

[('Adam', 16), ('Piotr', 16), ('Anna', 17), ('Ewa', 18), ('Anna', 19)]

slowniki = [
    {'imie': 'Adam', 'wiek': 16},
    {'imie': 'Ewa', 'wiek': 18},
    {'imie': 'Anna', 'wiek': 19},
    {'imie': 'Anna', 'wiek': 17},
    {'imie': 'Piotr', 'wiek': 16}
]

print(sorted(slowniki, key=lambda uczen: uczen['wiek']))

[{'imie': 'Adam', 'wiek': 16}, {'imie': 'Piotr', 'wiek': 16}, {'imie': 'Anna', 'wiek': 17}, {'imie': 'Ewa', 'wiek': 18}, {'imie': 'Anna', 'wiek': 19}]

class Uczen:
    def __init__(self, imie, wiek):
        self.imie = imie
        self.wiek = wiek

    def __repr__(self):
        return self.imie + ' ' + str(self.wiek)

obiekty = [
    Uczen('Adam', 16),
    Uczen('Ewa', 18),
    Uczen('Anna', 19),
    Uczen('Anna', 17),
    Uczen('Piotr', 16)
]

print(sorted(obiekty, key=lambda uczen: uczen.wiek))

[Adam 16, Piotr 16, Anna 17, Ewa 18, Anna 19]

Podczas sortowania możemy również używać funkcji porównującej (komparatora), która powinna zwracać wartość mniejszą od 0, jeżeli pierwszy element jest mniejszy od drugiego; wartość większą od 0, w przeciwnym przypadku lub wartość 0, kiedy elementy są równe. Użycie funkcji porównującej daje nam możliwość określania własnych reguł, które decydują, który z dwóch elementów uznajemy za większy.

Do wskazania funkcji porównującej w argumencie key wykorzystujemy funkcję cmp_to_key() z modułu functools. Jej argumentem jest nazwa funkcji porównującej.

from functools import cmp_to_key

def porownaj(a, b):
    print("Porównuję:", a, "i", b, end="")
    if a % 2 == 1 and b % 2 == 0:
        print(" Zwracam -1")
        return -1
    print(" Zwracam 1")
    return 1

lista = [1, 2, 3, 4, 5, 6]
print(sorted(lista, key=cmp_to_key(porownaj)))

Porównuję: 2 i 1 Zwracam 1
Porównuję: 3 i 2 Zwracam -1
Porównuję: 3 i 2 Zwracam -1
Porównuję: 3 i 1 Zwracam 1
Porównuję: 4 i 3 Zwracam 1
Porównuję: 4 i 2 Zwracam 1
Porównuję: 5 i 2 Zwracam -1
Porównuję: 5 i 3 Zwracam 1
Porównuję: 6 i 5 Zwracam 1
Porównuję: 6 i 4 Zwracam 1
[1, 3, 5, 2, 4, 6]

list.sort()

Biblioteka standardowa zawiera również definicję funkcji sort() dostępnej jako metoda każdej listy. Metoda ta nie zawraca nowej listy, natomiast modyfikuje kolejność elementów listy, na rzecz której jest wywoływana. Wykorzystuje wspominany już algorytm stabilnego sortowania hybrydowego TimsorttimsortTimsort.

W metodzie sort() możemy korzystać z dwóch opcjonalnych nazwanych argumentów, tj. reverse oraz key. Ich działanie jest takie samo jak w przypadku funkcji sorted(). Poniżej zamieszczamy kilka przykładów.

lista = [5, 8, -3, 1, 10, 3.14, 18]
lista.sort()
print(lista)

[-3,1,3.14,5,8,10,18]

lista = [5, 8, -3, 1, 10, 3.14, 18]
lista.sort(reverse=True)
print(lista)

[18,10,8,5,3.14,1,-3]

lista = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
lista.sort(key=lambda x: x % 2 == 0)
print(lista)

[1,3,5,7,9,2,4,6,8,10]

Słownik