sortowanie

sortowanie,

inform. zadanie polegające na uporządkowaniu elementów pewnego ciągu (np. zapisanych w tablicy) wg wartości klucza (np. s. liczb w porządku rosnącym albo s. rekordów opisujących osoby w kolejności ich nazwisk lub dat urodzenia).

Rekordy w pliku sortuje się wg relacji między ich kluczami (identyfikator umieszczony w ustalonym polu rekordu); sortowania w komputerze dzielą się na wewn. — wykonywane w pamięci operacyjnej, i zewn. — wykonywane w pamięci pomocniczej, np. na dysku; najlepsze sekwencyjne algorytmy sortowania wewn. osiągają średnią (oczekiwaną) czasową złożoność obliczeniową rzędu n logn, tzn. dolną granicę złożoności problemu sortowania (n jest liczbą sortowanych elementów, za miarę złożoności zaś przyjmuje się liczbę porównań elementów); sortowanie jest bardzo częstą operacją w przetwarzaniu danych — m.in. od jego sprawności zależy jakość systemów przetwarzania.