Сортирање мехуром

Sortiranje mehurom
	Vizuelna predstava bablsort algoritma;
Klasa	Algoritam sortiranja
Struktura podataka	Niz
Najgora performanca
Najbolja performanca
Prosečna performanca
Najgora prostorna kompleksnost

Sortiranje mehurom ili Bablsort (engl. Bubble sort), понекад погрешно названо потапајуће сортирање, алгоритам је који се користи за сортирање низова. Алгоритам ради тако што упоређује свака два суседна члана низа и замењује им места, ако су чланови низа у погрешном редоследу. Пролази се кроз низ елемената све док се не изврши ниједна замена тј. елементи су сортирани у одговарајућем поретку (растућем или опадајућем). Назив води порекло од чињенице да се после прве итерације кроз низ највећи елемент налази на највећој позицији у низу, тј. на десној страни низа. Алгоритам је веома лак за имплементацију у свим програмским језицима, али је веома непрактичан и спор чак и када се упореди са алгоритмом као што је сортирање уметањем.^[1] Алгоритам ради добро на низовима који има мали број елемената, или који су полусортирани, тј. само одређени број елемената је на неправилним позицијама.

Анализа

Пример буббле сорта. Полази се од почетка низа, упроредјује сваки суседни пар и мења њихов положај, ако нису у правом редоследу (следећи је мањи од претходног). После сваке итерације, упоређује се један елемент мање, све док више не постоје елементи које треба упоређивати.

Перформансе

Баблсорт има најгору сложеност О(n²), где је n број елемената који се сортирају. Постоји много алгоритама за сортирање који имају знатно бољу сложеност O(n log n). Чак и други алгоритими сложености О(n²), као што је сортирање уметањем, имају тенденцију да имају боље перформансе од баблсорта. Дакле, сортирање мехуром није практичан алгоритам за сортирање када је n велико.

Једина значајна предност баблсорта за разлику од других имплементација, чак и квиксорта, али не сортирања уметањем, је способност да открије да је сортиран низ ефикасно уграђен у алгоритам. Сложеност баблсорта над већ сортираним низовима (у најбољем случају) је O(n). Насупрот томе, већина других алгоритама, чак и они са бољом просечном сложеношћу, обављају цео процес сортирања на сету и на тај начин су сложенији. Међутим, не само да инсертион сорт има овај механизам, већ и боље ради на низу који је знатно сортиран (мали број инверзија)

Зечеви и корњаче

Позиције елемената у баблсорту играју велику улогу у одређивању сложености. Велики елементи на почетку низа не представљају проблем јер се брзо замене. Мали елементи при крају низа се крећу на почетак веома споро. Због тога се ове врсте елемената респективно називају зечеви и корњаче.

Учињени су разни напори да се елиминишу корњаче како би се побољшала брзина баблсорта. Коктелсорт је двосмерни баблсорт који иде од почетка до краја, а онда се поништава и иде од краја до почетка. Он може да се помера корњаче прилично добро, али задржава сложеност O(n²). Комбсорт пореди елементе раздвојене великим празнинама, а може да помера корњаче изузетно брзо пре него што пређе на мање празнине. Његова просечна брзина се може упоредити са брзим алгоритмима као што је квиксорт.

Корак по корак пример

Низ бројева "5 1 4 2 8" потребно је сортирати од најмањег до највећег броја (у растућем поретку) помоћу баблсорта. У сваком кораку болдирани елементи се упоређују. Биће потребна три проласка кроз низ:

Први пролазак:

(5 1 4 2 8 ) $\to$ (1 5 4 2 8 ), Алгоритам упоређује прва два елемента и замењује 1 и 5 , 5 > 1.

(1 5 4 2 8 ) $\to$ (1 4 5 2 8 ), замена пошто је 5 > 4

(1 4 5 2 8 ) $\to$ (1 4 2 5 8 ), замена пошто је 5 > 2

(1 4 2 5 8 ) $\to$ (1 4 2 5 8 ), Сада, пошто су ови елементи већ сортирани (8 > 5), алгоритам их неће заменити.

Други пролазак:

(1 4 2 5 8 ) $\to$ (1 4 2 5 8 )

(1 4 2 5 8 ) $\to$ (1 2 4 5 8 ), замена пошто је 4 > 2

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

Сада, низ је већ сортиран, али наш алгоритам још увек не зна да је сортирање завршено. Алгоритам је завршен тек када продје кроз цео низ без и једне замене.

Трећи пролазак:

(1 2 4 5 8 ) $\to$ (1 2 4 5 8 )

Имплементација

Псеудокод имплементација

Алгоритам се може изразити као (0- базни низ):

procedure bubbleSort(A : list of sortable items )
   repeat     
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap(A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Да подсетимо, постоје бољи алгоритми за сортирање као што је квиксорт који се обично користе, а већина програмских језика има уграђену функцију у стандардној библиотеци која се може користити уместо да се имплементира сопствени алгоритам за сортирање.

Оптимизација буббле сорта

Баблсорт алгоритам се може лако опимизовати посматрањем, ако се уочи да n-ти пролаз проналази n-ти највећи елемент и ставља га на његово место. Дакле, унутрашња петља може да се избегне гледајући последњих n-1 елемената када ради за n-ти пут:

procedure bubbleSort(A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

Уопштено, може се десити да се више од једног елемента налази у завршној позицији у једном пролазу. Конкретно, после сваког пролаза, сви елементи до последње замене су сортирани и не треба их поново проверавати. То нам омогућава да се пресочи много елемената, што доводи до у најгорем случају 50% побољшања и додаје мало сложености, јер нови код подводи „заменљива” променљива:

Да би се ово постигло у псеудокоду пишемо следеће:

procedure bubbleSort(A : list of sortable items )
    n = length(A)
    repeat
       newn = 0
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             newn = i
          end if
       end for
       n = newn
    until n = 0
end procedure

Алтернативне модификације, као што је коктел сортирање метода покушаји су да се побољша буббле сорт задржавајући исту идеју (више пута се преде елементи и замена суседних елемената)

У пракси

Баблсорт, алгоритам за сортирање који стално пролази кроз низ, замењује места елементима док се не појаве у исправном редоследу. Треба запазити да се прво сортирају највећи елементи, а затим мањи.

Иако је баблсорт један од најједноставнијих алгоритама за сортирање потребно је разумети и његову примену. Његова сложеност O(n²) значи да се његова ефикасност смањује драматично на низовима који имају већи број елемената. Чак и међу једноставним O(n²) алгоритмима, алгоритми попут сортирања уметањем су знатно ефикаснији.

Због своје једноставности, баблсорт се често користи да се уведе концепт алгоритама или алгоритам за сортирање на уводним предавањима студентима информатика. Међутим, неки истраживачи као што је Овен Астрачан су отишли предалеко омаловажавајући баблсорт и његову популарност у образовању информатичара препоручујући да се више и не учи.^[2]

Тхе Јаргон филе, чији је познати назив глупи сорт "the archetypical [sic] perversely awful algorithm", такође назива баблсорт генерички лош алгоритам.^[3] Доналд Кнут у својој чувеној књизи Уметност рачунарског програмирања закључио је да се Баблсорт нема по чему препоручити осим по привлачном имену и чињеници да не испољава неке од занимљивих теоријских проблема о којим је он тада говорио.^[1]

Баблсорт је асимптотски еквивалентан сортирању уметањем по времену извршавања у најгорем случају, али ова два алгоритма се веома разликују по броју потребних замена (свапова). Експериментални резултати као што су они од Астрачана су такође показали да сортирање уметањем ради знатно боље чак и на случајним листама. Из тих разлога многи модерни уџбеници избегавају коришћење алгоритма баблсорта у корист сортирања уметањем.

Баблсорт такође слабо комуницира са модерним ЦПУ хардвером. То захтева најмање дупло више писања него код инсертион сорта, дупло висе кеша, више филијала. Експерименти за Астрачан сортирање стрингова у Јави показује да алгоритам мехура може да буде око 5 пута спорији од алгоритма са уметањем и 40% спорији од селекционог сортирања.^[2]

У компјутерској графици је популаран због његове способности да открије веома малу грешку (као замену само два елемента) у скоросортираним низовима и поправити је са линеарном сложеношћу (2n).

Варијације

Сортирање "пар-непар" је паралелна верзија баблсорта, за системе размене порука.
Коктел сортирање је паралелна верзија баблсорта.
У неким случајевима, сортирање се врши са десна на лево (у супротном смеру) који је погоднији за делимично сортиране низове, односно низове са несортираним елементима на крају.

Погрешан назив

Баблсорт се погрешно назива потапајуће сортирање. Потапајуће сортирање је исправан псеудоним за сортирање са уметањем. Ова грешка је углавном настала кад је Национоални институт за стандарде и технологију навео тај псеудоним за баблсорт. У књизи Доналда Кнута „Уметност компјутерског програмирања“, том 3: сортирања и претраге, он наводи у одељку 5.2.1 „сортирање методом уметања решава проблем на свом правом нивоу“.

Референце

^ ^а ^б Кнутх, Доналд (1998). Тхе Арт оф Цомпутер Программинг, сецтион 5.2.2: Сортинг бy Еxцхангинг. 3: Сортинг анд Сеарцхинг (Сецонд изд.). Аддисон-Wеслеy. стр. 106—110. ISBN 0-201-89685-0. „"[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!" (Quote from the first edition, 1973.)”
^ ^а ^б Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . (pdf)
^ jargon, node: bogo-sort

Literatura

Knuth, Donald (1997). The Art of Computer Programming. Volume 3: Sorting and Searching, Third Edition. Addison-Wesley. стр. 106-110. ISBN 978-0-201-89685-5. of section 5.2.2: Sorting by Exchanging.
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms. Second Edition. MIT Press and McGraw-Hill. ISBN 978-0-262-03293-3. Problem 2-2, pp. 38.
Sorting in the Presence of Branch Prediction and Caches
Horowitz, Ellis; Sahni, Sartaj; Susan Anderson-Freed (2008). Fundamentals of Data Structures. ISBN 978-81-7371-605-8.
Алгоритми и структуре података - Мило Томашевић
Увод у програмирање - Милан Шкарић

Spoljašnje veze

„Bubble Sort - Engleska Wikipedija”.
„Bubble Sort implemented in 34 languages”. Архивирано из оригинала 22. 05. 2013. г. Приступљено 30. 05. 2013.
Toptal. „Animated Sorting Algorithms: Bubble Sort”. – graphical demonstration and discussion of bubble sort
„Лафоре'с Буббле Сорт”. Архивирано из оригинала 19. 01. 2008. г. Приступљено 30. 05. 2013. (Јава апплет аниматион)

[Knuth-1] а ^б Кнутх, Доналд (1998). Тхе Арт оф Цомпутер Программинг, сецтион 5.2.2: Сортинг бy Еxцхангинг. 3: Сортинг анд Сеарцхинг (Сецонд изд.). Аддисон-Wеслеy. стр. 106—110. ISBN 0-201-89685-0. „"[A]lthough the techniques used in the calculations [to analyze the bubble sort] are instructive, the results are disappointing since they tell us that the bubble sort isn't really very good at all. Compared to straight insertion […], bubble sorting requires a more complicated program and takes about twice as long!" (Quote from the first edition, 1973.)”

[Astrachan2003-2] а ^б Owen Astrachan. Bubble Sort: An Archaeological Algorithmic Analysis. SIGCSE 2003 Hannan Akhtar . (pdf)

[3] rgon, node: bogo-sort

[1]

[2]

[3]