Articles

Co to jest sortowanie?


Najlepsza odpowiedź

W informatyce algorytm sortowania to algorytm, który umieszcza elementy listy w określonej kolejności. Najczęściej używanymi porządkami są porządek numeryczny i porządek leksykograficzny. Wydajne sortowanie jest ważne dla optymalizacji wydajności innych algorytmów (takich jak algorytmy wyszukiwania i łączenia), które wymagają, aby dane wejściowe znajdowały się na posortowanych listach. Sortowanie jest również często przydatne do kanonizacji danych i tworzenia danych w postaci czytelnej dla człowieka. Bardziej formalnie, dane wyjściowe dowolnego algorytmu sortowania muszą spełniać dwa warunki:

  • Dane wyjściowe są w porządku niezmniejszającym się (każdy element nie jest mniejszy niż poprzedni element zgodnie z żądaną całkowitą kolejnością);
  • Dane wyjściowe to permutacja (zmiana kolejności, ale zachowanie wszystkich oryginalnych elementów) danych wejściowych.

Ponadto dane wejściowe są często przechowywane w tablicy, która umożliwia dostęp losowy, a nie listę, która umożliwia tylko dostęp sekwencyjny; chociaż wiele algorytmów można zastosować do obu typów danych po odpowiedniej modyfikacji.

Algorytmy sortowania są często określane jako słowo, po którym następuje słowo „sort”, i gramatycznie są używane w języku angielskim jako wyrażenia rzeczownikowe, na przykład w zdaniu „nie jest efektywne używanie sortowania przez wstawianie na dużych listach”, sortowanie przez wstawianie fraz odnosi się do algorytmu sortowania przez wstawianie.

Odpowiedź

Sortowanie miliarda obiektów jest na pewno w zasięgu, jeśli możesz zachować je w pamięci. Potrzebujesz porównania O (n log n), prawda? Jeśli nie możesz, możesz posortować to, co mieści się w pamięci twojego komputera (lub komputerów, jeśli masz system rozproszony), i połączyć wyniki. W pewnym momencie w latach 90. zmodyfikowane sortowanie scalające miało światowy rekord szybkości i super liniowe przyspieszenie na procesor.

Inną rzeczą, którą robisz, jest to, że gdy N staje się duże (lub właściwie zawsze, gdy cokolwiek zwalnia przy rozsądnych wejściach), przyjrzyj się bliżej temu, czego naprawdę potrzebujesz.

Dlaczego musisz sortować obiekty? Jeśli szukasz tylko duplikatów, istnieją znacznie szybsze sposoby! Jeśli chcesz przetworzyć dolne (lub górne) 5\%, istnieje O (n) algorytmów, które mogą partycjonować na podstawie postów Sortuj pozycję!

Kiedy sprawy stają się wolne, patrzysz na to, co się dzieje, i zanim zorientujesz się, czy to jest najszybszy algorytm, zrób cokolwiek to jest, dowiesz się, czy tak jest właściwie w ogóle! (Wyjątek: jeśli szybsze „cokolwiek” jest już zdebugowanym cienkim, możesz po prostu uderzyć, to może być lepiej zrobić to… na przykład jeśli okaże się, że e testowanie, czy tablica zawiera jakiś element wiele razy, prostsze może być zastąpienie tablicy zestawem i sprawdzenie, czy jest teraz na tyle szybki, że nie obchodzi Cię, że gdybyś zrobił kolejne sześć godzin badań, mógłbyś wyeliminować połowę czeki czy cokolwiek innego).

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *