Anglická verze
logolink

< Zpмt na seznam lekcн

Bubblesort - tшнdнcн algoritmus

AlgortimyObsah lekce:

  • Princip algoritmu
  • Bubblesort
  • Optimalizace algoritmu Bubblesort

Princip algoritmu

Tшнdicн algoritmus zvanэ bubble sort, jak nбzev napovнdб, funguje na principu bublinek, kterй vynбљн vмtљн инsla „nahoru“.

Pшнklad

Uspoшбdejte инsla 4, 8, 1, 4, 5, 2, 3 postupnэmi vэmмnami.

bubble sort

Znaиka oddмluje neuspoшбdanэ ъsek (vlevo) od uspoшбdanйho ъseku pole. Na zaибtku tшнdмnн je tedy u poslednнho prvku pole. Prochбzнme celй pole prvek po prvku od zaибtku do konce a je-li pшedchбzejнcн prvek vмtљн neћ nбsledujнcн, vymмnнme je. Tнm se po prvnнm prщchodu polem dostane (probublб) nejvмtљн prvek na konec a je poslednнm prvkem uspoшбdanйho ъseku. Znaиku posuneme o jedno mнsto dopшedu (doleva) a prochбzнme podruhй neuspoшбdanэ ъsek pole (od prvnнho prvku do znaиky) a je-li pшedchбzejнcн prvek vмtљн neћ nбsledujнcн, vymмnнme je. Tнm se uspoшбdanэ ъsek zvмtљн o druhэ prvek (druhэ nejvмtљн). Takto pokraиujeme dбle. Naposled tento postup opakujeme, je-li znaиka u druhйho prvku. Porovnбme prvnн dva prvky a je-li tшeba, vymмnнme. Tнm bude celй pole seшazenй.

Myљlenka (hrubэ algoritmus)

Pro znaиku od poslednнho zpмt do druhйho prvku pole opakujeme tuto иinnost:

  • projнt zkoumanэ ъsek od poибtku aћ do znaиky (oznaиena promмnou k) a zamмnit ty sousednн prvky, kterй nejsou podle velikosti

Tedy:

Bubblesort
for (i = 0; i < n-1; i++)
{projdi neusp. ъsek, je-li tшeba vymмт}

Prochбzenн s eventuбlnн vэmмnou lze upшesnit takto:

Bubblesort
for (k=0; k< n-i; k++)
if (cisla[k]>cisla[k+1])
{
<vymмт prvky>
}

Bubblesort - nejpomalejљн varianta

Tato prvnн varianta algoritmu slouћн pouze k tomu, abychom ukбzali, jak se dб pouze velmi malou zmмnou jedinйho znaku v programu, program velmi zefektivnit.

Bubblesort - zбkladnн nejpomalejљн varianta
for (k = 0; k < n-1; k++)
{
 for (i = 0; i < n-1; i++)
 {
  if (p[i]>p[i+1])
  {
    pom=p[i];
    p[i]=p[i+1];
    p[i+1]=pom;
  }
 }
}

Pшedpoklбdejme, ћe mбme definovanй pole p o n prvcнch, kterй naplnнme nбhodnэmi инsly a chceme je setшнdit podle velikosti.

Pшi prvnнm prщchodu cyklu FOR mб promмnnб k i i hodnotu 0 a porovnбvбme, zda je prvnн prvek p[i] vмtљн, neћ prvek nбsledujнcн, tedy p[i+1]. Pokud je podmнnka splnмna, jsou hodnoty tмchto promмnnэch prohozeny. K tomu slouћн tyto tшi шбdky:

  • pom=p[i]; -> Do pomocnй promмnnй pom si uloћнme hodnotu jednoho prvku.
  • p[i]=p[i+1]; -> Do prvku pole, jehoћ hodnotu mбme uloћenou z pшedchozнho kroku, dosadнme hodnotu druhйho prvku pole.
  • p[i+1]=pom; -> Na zбvмr umнstнme hodnotu z pomocnй promмnnй do druhйho prvku pole.

Takћe teп se nбm ukonиila podmнnka IF a program se vracн zpмt k druhйmu cyklu FOR, kde i uћ nabylo hodnoty 1. Nynн tedy porovnбvбme druhэ a tшetн prvek stejnэm zpщsobem jako pшedtнm.

Aћ vzroste инtaи i na hodnotu, kterб se rovnб hodnotм promмnnй n-1, pak uћ cyklus neprobмhne a program se vrбtн zpмt k prvnнmu cyklu FOR. Zde se инtaи k zvedne na hodnotu 1 a opмt probнhб pшehazovбnн dvojic инsel, opмt od prvnнho k poslednнmu.

Tahle varianta tшнdмnн je ze vљech tшн uvбdмnэch nejhorљн. Program ovмшuje seшazenн инsel pokaћdй od prvnнho инsla aћ po poslednн a to dokud cyklus FOR s k=0 aћ k < (n-1) nenabude svй maximбlnн hodnoty, tedy (n-2). Pшedpoklбdejme, ћe v poli mбme 10 000 инsel a ve stejnэ okamћik si 100 uћivatelщ zadб pшнkaz seшazenн. Uћ v tomto okamћiku by operace trvala zbyteиnм dlouho. Je to zbyteиnй mrhбnн иasem procesoru.

Bubblesort - varianta 2 aneb zбmмnou jednoho znaku k 50% nбrщstu vэkonu

Nynн celэ algoritmus zefektivnнme tнm, ћe ve druhйm cyklu ponechбme cyklus bмћet do n-k namнsto n-1.

Bubblesort - varianta 2
for (k = 0; k < n-1; k++)
{
 for (i = 0; i < n-k; i++)
 {
  if (p[i]>p[i+1])
  {
    pom=p[i];
    p[i]=p[i+1];
    p[i+1]=pom;
  }
 }
}

Aћ vzroste инtaи i na hodnotu, kterб se rovnб hodnotм promмnnй n, pak uћ cyklus neprobмhne a program se vrбtн zpмt k prvnнmu cyklu FOR. Zde se инtaи k zvedne na hodnotu 2 a opмt probнhб pшehazovбnн dvojic инsel, ale nikoliv k poslednнmu, pouze do n-k, protoћe ta nejvyљљн hodnota v poli je vћdy na poslednнm mнstм uћ po prvnнm prщchodu prvnнho cyklu FOR (probublala na poslednн mнsto v poli). Takћe jiћ nenн nutnй ji porovnбvat, neboќ mбme jistotu, ћe jiћ na sprбvnйm mнstм.

Jedinб vмc, kterб zbэvб vysvмtlit je, proи prvnн cyklus FOR mб probнhat pouze n-1. To proto, protoћe staин jednotlivэch porovnбnн provйst o jedno mйnм, neћ mб pole prvkщ. Pokud si sepнљete иtyшi nejvyљљн hodnoty pмti-prvkovйho pole, pak je jasnй, ћe ta pбtб hodnota nemщћe bэt vyљљн neћ ony иtyшi.

Dнky zmмnм z n-1 na n-k uћ program neovмшuje vљechna инsla, ale v kaћdйm dalљнm kroku uћ kontroluje o jedno инslo mйnм neћ v kroku pшedchozнm, neboќ s kaћdэm dalљнm krokem se hodnota k zvмtљuje a tнm ubэvб инsel, kterб nejsou jeљtм seшazena (seшazenб инsla pшibэvajн od nejvмtљнho po nejmenљн na pravйm konci pole).

Pшнklad.: Mбme pole o 5 инslech

bubblesort

*tento krok vщbec neprobнhб, do tabulky byl uveden jen ilustraиnм pro ъplnost "schodщ".

Domбcн ъkol

Naleznмte na Internetu alespoт dva dalљн algoritmy na tшнdмnн инsel a jeden realizujte v jazyce C.

Otбzky

  1. Popiљte princip algoritmu Bubblesort.
  2. Jakй optimalizace lze v algoritmu Bubblesort realizovat?
  3. Uveпte alespoт dva dalљн pшнklady tшнdнcнch algoritmщ.
webdesign, xhtml, css, php - Mgr. Michal Mikláš