Tídní bublin



Internet je nevyčerpatelným zdrojem znalostí, i pokud jde o Tídní bublin. Do sítě byla a stále jsou vkládána staletí a staletí lidského poznání o Tídní bublin, a právě proto je tak obtížné se k ní dostat, protože můžeme najít místa, kde může být navigace obtížná nebo dokonce nepraktická. Naším návrhem je, abyste neztroskotali v moři dat týkajících se Tídní bublin a abyste se rychle a efektivně dostali do všech přístavů moudrosti.

S tímto cílem jsme udělali něco, co jde nad rámec samozřejmostí, a shromáždili jsme nejaktuálnější a nejlépe vysvětlené informace o Tídní bublin. Uspořádali jsme ji také tak, aby byla snadno čitelná, s minimalistickým a příjemným designem, který zajišťuje nejlepší uživatelský zážitek a nejkratší dobu načítání. Usnadňujeme vám to, abyste se museli starat jen o to, abyste se dozvěděli vše o Tídní bublin! Pokud si tedy myslíte, že jsme dosáhli svého cíle a že už víte, co jste chtěli vědět o Tídní bublin, budeme rádi, když se vrátíte do těchto klidných moří sapientiacs.com, kdykoli se ve vás znovu probudí hlad po vědění.

Tídní podle bublin (také azení podle vzestupného nebo výmnného azení ) je algoritmus, který tídí seznam prvk na základ srovnání . Tento procesu tídní pracuje na míst , druhy ve stabilním zpsobem a má runtime o v nejhorím pípad ( nejhorí pípad ), jako i v prmrné pouzdro (prmrný pípad). Doba bhu proto není asymptoticky optimální . V praxi se azení bublin pouívá jen zídka, protoe jiné metody mají lepí bhové chování. Algoritmus vak hraje roli ve výuce, protoe je snadné jej vysvtlit a demonstrovat. Algoritmus je vhodný také pro zavedení technik, jako je krok za krokem optimalizace, runtime nebo analýza sloitosti a správnosti .

zásada

Ve fázi bubliny je vstupní seznam veden zleva doprava. V kadém kroku je aktuální prvek porovnán se správným sousedem. Pokud tyto dva prvky poruují kritérium azení, jsou vymnny. Na konci fáze je ve vzestupném nebo sestupném poadí nejvtí nebo nejmení prvek záznamu na konci seznamu.

Fáze bubliny se opakuje, dokud není seznam vstup zcela tídn. Poslední prvek pedchozího bhu ji není teba brát v úvahu, protoe zbývající vstup, který se má tídit, ji neobsahuje ádné vtí ani mení prvky.

V závislosti na tom, zda je azen vzestupn nebo sestupn, se vtí nebo mení prvky, jako jsou bubliny ve vod (odtud název), zvedají vý a vý, tj. Na konec seznamu. Dv ísla jsou vdy vzájemn zamována v bublinách.

algoritmus

Z dvodu zjednoduení reprezentace algoritmu se níe pouívá (vtí ne) jako srovnávací vztah . Stejn jako u jakékoli metody azení zaloené na srovnání lze i toto nahradit jinou relací, která definuje celkovou objednávku .

Algoritmus ve své nejjednoduí form jako pseudokód :

bubbleSort(Array A)
  for (n=A.size; n>1; --n){
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
      } // Ende if
    } // Ende innere for-Schleife
  } // Ende äußere for-Schleife

Vstup je uloen v poli . Vnjí smyka postupn sniuje pravý limit pro fázi bubliny, protoe po kadé bublin je nejvtí prvek vstupu netídného zbytku v poloze zcela vpravo. Ve vnitní smyce probhne dosud nevytídná ást pole. Dv sousední data jsou zamnna, pokud jsou ve patném poadí (tj. Poruují kritérium tídní).

Tato nejjednoduí varianta vak nevyuívá výhody vlastnosti, e po iteraci, ve které nedolo k ádné výmn, nedojde ani ve zbývajících iteracích k ádné výmn. Následující pseudokód to bere v úvahu:

bubbleSort2(Array A)
  n = A.size
  do{
    swapped = false
    for (i=0; i<n-1; ++i){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
        swapped = true
      } // Ende if
    } // Ende for
    n = n-1
  } while (swapped)

Vnjí smyka prochází daty, která mají být tídna, dokud nejsou nutné dalí swapy.

píklad

Série pti ísel by mla být seazena vzestupn.

ísla uvedená tun jsou porovnána. Pokud je levice vtí ne pravá, dojde k výmn obou; dvojice ísel je poté oznaena mode. Pi prvním prchodu se nejvtí íslo posune úpln doprava. Druhý prchod proto ji nemusí porovnávat poslední a pedposlední pozici. Tetí bh: ádné srovnání poslední / pedposlední / pedposlední ...

55 07 78 12 42   1. Durchlauf
07 55 78 12 42
07 55 78 12 42
07 55 12 78 42   Letzter Vergleich
07 55 12 42 78   2. Durchlauf
07 55 12 42 78
07 12 55 42 78   Letzter Vergleich
07 12 42 55 78   3. Durchlauf
07 12 42 55 78   Letzter Vergleich
07 12 42 55 78   4. Durchlauf + Letzter Vergleich
07 12 42 55 78   Fertig sortiert.

sloitost

Nejhorí pípad

Bubblesort má bh pro seznamy délky . V pípad obrácen seazeného seznamu se provádí maximální poet zámn: za úelem posunutí prvního (a nejvtího) prvku zcela vpravo se provedou zámny. Obecn: Pohyb -tého prvku na místo se provádí výmnami. Sítání vech vede k výmnám jako celku . Protoe jsou vymovány pouze páry, které byly také pedem porovnány, algoritmus také potebuje alespo tolik srovnání. Pokud se podíváte na pseudokód algoritmu, mete snadno zjistit, e ádný z pokyn nelze provést vícekrát, take je to také nejlepí moná dolní mez.

Nejlepí pípad

Pokud je seznam ji seazen, Bubblesort projde seznam pouze jednou, aby zjistil, e seznam ji byl seazen, protoe nebylo nutné zamnit ádné sousední prvky. Proto Bubblesort potebuje kroky ke zpracování ji seazeného seznamu.

Pokud jsou prvky seznamu ji blízké pozicím, které by po tídní mly mít, je bhová doba podstatn lepí ne .

Prmrný pípad

Oekávaný poet srovnání pro náhodn zvolenou permutaci seznamu je

,

kde znamená na Eulerova konstanta ; oekávaný poet swap je .

Vymezení

I kdy tídní bublin není asymptoticky optimální, lze jej pouít pro malé vstupy, protoe u malých, které jsou pro tídní bublin malé, pevládají faktory stálého bhu tídicího algoritmu. Jedním pípadem pouití by bylo pouití bublinového tídní v rámci rekurzivního procesu tídní, aby se sníil poet rekurzí.

Pokud jsou prvky pole nebo seznamu (a do uritého potu) ji tídny s vysokou pravdpodobností, je vhodné tídní bublin, protoe to je nejlepí pípad, kdy má algoritmus lineární bh. Naproti tomu jiné úinné zpsoby tídní, jako nap. B. Quicksort nebo asymptoticky optimální metody, jako je Mergesort , nejlepí pípad .

Z tohoto pohledu konkuruje tídní bublin tídní s vloením , jeho nejlepím pípadem je ji seazená sekvence a která má stejnou sloitost jako tídní bublin (jako v prmrném a nejhorím pípad). Pro ob metody azení platí následující: Jsou stabilní a fungují na míst. V závislosti na implementaci má vak tídní vloení nií konstantní bhové faktory ne tídní bublin.

Zajíci a elvy

Pro tídicí úsilí Bubblesortu je rozhodující poloha prvk ped tídním. Velké prvky na zaátku nemají negativní úinek, protoe jsou rychle zamnny dozadu; malé prvky na konci se vak pomalu posouvají vped. Proto se prvky, které se rychle vymují, nazývají králíci a pomalé se nazývají elvy .

Combsort (také nazývaný Gapsort) je nejrychlejí algoritmus zaloený na bubbleortu. Na rozdíl od Bubblesortu jsou prvky, které jsou od sebe daleko, porovnávány a vymovány, aby se pedelo dilematu pomalu se pohybujících prvk. Jeho trvání je v nejhorím pípad také u a v nejlepím pípad u (Bubblesort :) . Combsort tak v nejhorích a nejlepích pípadech dosahuje stejné úrovn sloitosti jako Quicksort .

Koktejlové tídní (také nazývané Shakersort) je alternativní algoritmus tídní, který umouje pohybovat se prvky zleva doprava a zprava doleva. To také psobí proti problému pomalého pohybu prvk vped. Kvli alternaci se tento algoritmus nazývá také obousmrné tídní bublin. V nejhorím pípad je jeho runtime, podobn jako u Bubblesortu .

V roce 2009 spolenost Oyelami OM zveejnila optimalizovanou verzi Bubblesort, která se vyhne nejhorímu pípadu u polí / seznam seazených v opaném poadí. Vzhledem k pidruenému tídní na dálku ji není algoritmus, který pouívá, stabilní. Na základ výe uvedeného bubbleSort3 je níe znázornno optimalizované obousmrné tídní bublin pomocí funkce skriptu papyrusu. Float [] a je píklad ukazatele na pole s ísly s plovoucí desetinnou árkou. Dva celoíselné parametry pedstavují flexibilní oblast tídní pro pole (poátení hodnota L, koncová hodnota R). Za pedpokladu, e pole má 99 prvk a zaíná na 0, musí být nastaveny L = 0 a R = 99, aby bylo moné je kompletn seadit.

 '''FUNCTION''' SortByBubble3(Float[] a, Int L, Int R)
 1
 2  float X  ; pivot element
 3  float f  ; temp element for swap
 4  int m  ; last swap position
 5  int i  ; counter
 6; ------------------------ round1: suggested by Oyelami
 7  i = L
 8  m = R
 9 '''WHILE''' (i < m) ; to avoid worst-case by using an array sorted in reverse order
 10  X = a[i]
 11  f = a[m]
 12  '''IF''' (X > f)
 13   a[m] = X
 14   a[i] = f
 15  '''ENDIF'''
 16  i = i + 1
 17  m = m - 1
 18 '''ENDWHILE'''
 19; ----------------------- round2: optimized bi-directional BubbleSort
 20 '''WHILE''' (L < R)
 21  X = a[L]
 22  m = L - 1    ; init "m" out of sorting range related to Left bound
 23  i = L + 1
 24  '''WHILE''' (i <= R) ; -- BottomUp loop -- sorts to maximum at the end
 25   f = a[i]
 26   '''IF''' (X <= f)
 27    X = f   ; no exchange: set "pivot" to follower element
 28   '''ELSE'''
 29    a[i] = X  ; \ swap two elements
 30    m = i - 1  ; - update "last swap" position
 31    a[m] = f  ; / and keep current "pivot" for next comparison
 32   '''ENDIF'''
 33   i = i + 1  ; i++
 34  '''ENDWHILE'''
 35;         -------------
 36  R = R - 1   ; R--
 37  '''IF''' (R > m)
 38   '''IF''' (L < m)
 39    R = m   ; shrink the Right bound as much as possible
 40   '''ELSE'''
 41    R = L ; no swap last time, break the loop!
 42   '''ENDIF'''
 43  '''ENDIF'''
 44;          ==============
 45  X = a[R]
 46  m = R + 1    ; init "m" out of sorting range related to Right bound
 47  i = R - 1
 48  '''WHILE''' (i >= L) ; -- TopDown loop -- sorts to minimum on start
 49   f = a[i]
 50   '''IF''' (X >= f)
 51    X = f   ; no exchange: set "pivot" to follower element
 52   '''ELSE'''
 53    a[i] = X  ; \ swap two elements
 54    m = i + 1  ; - update "last swap" position
 55    a[m] = f  ; / and keep current "pivot" for next comparison
 56   '''ENDIF'''
 57   i = i - 1  ; i--
 58  '''ENDWHILE'''
 59  L = L + 1   ; L++
 60  '''IF''' (L < m)
 61   '''IF''' (R > m)
 62    L = m
 63   '''ELSE'''
 64    L = R ; no swap last time, break the loop!
 65   '''ENDIF'''
 66  '''ENDIF'''
 67 '''ENDWHILE'''
 68 '''ENDFUNCTION'''

literatura

webové odkazy

Commons : Bubblesort  - sbírka obrázk, videí a zvukových soubor

Individuální dkazy

  1. ^ Donald E. Knuth : The Art of Computer Programming : Volume 3 Sorting and Searching . 2. vydání. Addison-Wesley, Reading MA 1997, ISBN 0-201-89685-0 , str. 108-109 .

Opiniones de nuestros usuarios

Ivan Kočí

Toto je dobrý článek o Tídní bublin. Poskytuje potřebné informace bez excesů.

Nicolas Volf

Tento záznam o Tídní bublin bylo přesně to, co jsem chtěl najít.