Sortowanie (algorytmy)

2012-09-25 23:05

Rejestracja: 12 lat temu

Ostatnio: 2 lata temu

0

Tak sobie czytam o algorytmach i chciałbym zapytać jak to wygląda w praktyce.
Których prócz Quicksortu faktycznie się używa.
Patrząc na złożoność obliczeniową, to porównywalne, jak nie lepsze są:

  • przez scalanie
  • introspektywne
  • przez zliczanie
  • przez kopcowanie
  • kubełkowe

Których faktycznie się używa?

@ubuntuser zależy o jaką "praktykę" chodzi. W systemach bazodanowych na przykład zwykle używa się merge-sorta. - Shalom 2012-09-26 10:28

Pozostało 580 znaków

2012-09-25 23:31

Rejestracja: 15 lat temu

Ostatnio: 4 godziny temu

0

Zależy od zbioru, który chcesz posortować każde z nich ma swoją złożoność pesymistyczną i optymistyczną, oraz sposób "skakania" po pamięci, lub dodatkową pamięć, której nie zawsze można sobie zażyczyć w każdej ilości np. masz duży plik do posortowania, którego na raz nie można załadować do pamięci, lub posiadasz dane częściowo posortowane tylko trzeba je "dosortować"

Pozostało 580 znaków

2012-09-25 23:46

Rejestracja: 14 lat temu

Ostatnio: 1 godzina temu

3
  • przez scalanie
    Wymaga dodatkowej pamięci jeżeli sortujesz tablice. Jeżeli sortujesz listy, to nie wymaga dodatkowej pamięci, a ponadto zachowuje swoją złożoność, bo nie wymaga wydajnego dostępu do losowej pozycji elementu.

  • introspektywne
    To jest przecież quicksort z kontrolą głębokości stosu i fallbackiem do jakiegoś sortowania z gwarantowaną złożonością O(n lg n), czyli zwykle heapsort. Wydaje mi się, że dość często jest właśnie stosowany jako główny algorytm.

  • przez zliczanie
    Opłaca się tylko wtedy, kiedy rozmiar uniwersum kluczy jest porównywalny do rozmiaru danych.

  • przez kopcowanie
    Ogólnie jest wolniejsze od sortowania szybkiego czy sortowania przez scalanie, gdyż wykonuje wiele dostępów do losowych pozycji pamięci. Losowych oczywiście dla procesora, który nie radzi sobie z przewidywaniem adresów. W przypadku sortowania szybkiego, a dokładniej partycjonowania mamy skanowanie liniowe i z tym procesory sobie bardzo dobrze radzą.

  • kubełkowe
    Nie zawsze się opłaca. Jeśli mamy relatywnie mało elementów do porównania, ale każdy element jest bardzo długi i ponadto elementy mają długie wspólne prefiksy, to złożoność tego sortowania może stać się wysoka.


"Programs must be written for people to read, and only incidentally for machines to execute." - Abelson & Sussman, SICP, preface to the first edition
"Ci, co najbardziej pragną planować życie społeczne, gdyby im na to pozwolić, staliby się w najwyższym stopniu niebezpieczni i nietolerancyjni wobec planów życiowych innych ludzi. Często, tchnącego dobrocią i oddanego jakiejś sprawie idealistę, dzieli od fanatyka tylko mały krok."
Demokracja jest fajna, dopóki wygrywa twoja ulubiona partia.

Pozostało 580 znaków

2012-09-26 08:00

Rejestracja: 16 lat temu

Ostatnio: 25 minut temu

0

A co z sortowaniem przez wstawianie?

Pozostało 580 znaków

2012-09-26 09:37

Rejestracja: 16 lat temu

Ostatnio: 3 godziny temu

4

chciałbym zapytać jak to wygląda w praktyce.
W praktyce nie myśli się o algorytmach, tylko odpala jakąś gotową w bibliotece funkcję sort(), która jest zazwyczaj quicksortem, ewentualnie introsortem (czyli quicksort+heapsort).

W Javie jest to Dual-Pivot Quicksort. - bogdans 2012-09-26 10:02

Pozostało 580 znaków

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0