\nFirst Pass:<\/b>
\n( 5<\/b> 1<\/b> 4 2 8 ) \u2013> ( 1<\/b> 5<\/b> 4 2 8 ), Here, algorithm compares the first two elements, and swaps since 5 > 1.
\n( 1 5<\/b> 4<\/b> 2 8 ) \u2013>\u00a0 ( 1 4<\/b> 5<\/b> 2 8 ), Swap since 5 > 4
\n( 1 4 5<\/b> 2<\/b> 8 ) \u2013>\u00a0 ( 1 4 2<\/b> 5<\/b> 8 ), Swap since 5 > 2
\n( 1 4 2 5<\/b> 8<\/b> ) \u2013> ( 1 4 2 5<\/b> 8<\/b> ), Now, since these elements are already in order (8 > 5), algorithm does not swap them.<\/p>\n[ad type=\u201dbanner\u201d]\n
Second Pass:<\/b>
\n( 1<\/b> 4<\/b> 2 5 8 ) \u2013> ( 1<\/b> 4<\/b> 2 5 8 )
\n( 1 4<\/b> 2<\/b> 5 8 ) \u2013> ( 1 2<\/b> 4<\/b> 5 8 ), Swap since 4 > 2
\n( 1 2 4<\/b> 5<\/b> 8 ) \u2013> ( 1 2 4<\/b> 5<\/b> 8 )
\n( 1 2 4 5<\/b> 8<\/b> ) \u2013>\u00a0 ( 1 2 4 5<\/b> 8<\/b> )
\nNow, the array is already sorted, but our algorithm does not know if it is completed. The algorithm needs one whole<\/b> pass without any<\/b> swap to know it is sorted.<\/p>\n
Third Pass:<\/b>
\n( 1<\/b> 2<\/b> 4 5 8 ) \u2013> ( 1<\/b> 2<\/b> 4 5 8 )
\n( 1 2<\/b> 4<\/b> 5 8 ) \u2013> ( 1 2<\/b> 4<\/b> 5 8 )
\n( 1 2 4<\/b> 5<\/b> 8 ) \u2013> ( 1 2 4<\/b> 5<\/b> 8 )
\n( 1 2 4 5<\/b> 8<\/b> ) \u2013> ( 1 2 4 5<\/b> 8<\/b> )<\/p>\n
Following are C\/C++, Python and Java implementations of Bubble Sort.<\/p>\n
C and C++<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20C%20program%20for%20implementation%20of%20Bubble%20sort%0A%23include%20%3Cstdio.h%3E%0A%20%0Avoid%20swap(int%20*xp%2C%20int%20*yp)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*xp%3B%0A%20%20%20%20*xp%20%3D%20*yp%3B%0A%20%20%20%20*yp%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20A%20function%20to%20implement%20bubble%20sort%0Avoid%20bubbleSort(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20int%20i%2C%20j%3B%0A%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n-1%3B%20i%2B%2B)%20%20%20%20%20%20%0A%20%0A%20%20%20%20%20%20%20%2F%2F%20Last%20i%20elements%20are%20already%20in%20place%20%20%20%0A%20%20%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%20n-i-1%3B%20j%2B%2B)%20%0A%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3E%20arr%5Bj%2B1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20swap(%26arr%5Bj%5D%2C%20%26arr%5Bj%2B1%5D)%3B%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20an%20array%20*%2F%0Avoid%20printArray(int%20arr%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20%20for%20(int%20i%3D0%3B%20i%20%3C%20size%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Bi%5D)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B64%2C%2034%2C%2025%2C%2012%2C%2022%2C%2011%2C%2090%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20bubbleSort(arr%2C%20n)%3B%0A%20%20%20%20printf(%22Sorted%20array%3A%20%5Cn%22)%3B%0A%20%20%20%20printArray(arr%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc and c++\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n[ad type=\u201dbanner\u201d]\n
Java<\/p>\n[pastacode lang=\u201djava\u201d manual=\u201d%2F%2F%20Java%20program%20for%20implementation%20of%20Bubble%20Sort%0Aclass%20BubbleSort%0A%7B%0A%20%20%20%20void%20bubbleSort(int%20arr%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20n-1%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20for%20(int%20j%20%3D%200%3B%20j%20%3C%20n-i-1%3B%20j%2B%2B)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3E%20arr%5Bj%2B1%5D)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%2F%2F%20swap%20temp%20and%20arr%5Bi%5D%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20int%20temp%20%3D%20arr%5Bj%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%20%3D%20arr%5Bj%2B1%5D%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%2B1%5D%20%3D%20temp%3B%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F*%20Prints%20the%20array%20*%2F%0A%20%20%20%20void%20printArray(int%20arr%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20int%20n%20%3D%20arr.length%3B%0A%20%20%20%20%20%20%20%20for%20(int%20i%3D0%3B%20i%3Cn%3B%20%2B%2Bi)%0A%20%20%20%20%20%20%20%20%20%20%20%20System.out.print(arr%5Bi%5D%20%2B%20%22%20%22)%3B%0A%20%20%20%20%20%20%20%20System.out.println()%3B%0A%20%20%20%20%7D%0A%20%0A%20%20%20%20%2F%2F%20Driver%20method%20to%20test%20above%0A%20%20%20%20public%20static%20void%20main(String%20args%5B%5D)%0A%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20BubbleSort%20ob%20%3D%20new%20BubbleSort()%3B%0A%20%20%20%20%20%20%20%20int%20arr%5B%5D%20%3D%20%7B64%2C%2034%2C%2025%2C%2012%2C%2022%2C%2011%2C%2090%7D%3B%0A%20%20%20%20%20%20%20%20ob.bubbleSort(arr)%3B%0A%20%20%20%20%20%20%20%20System.out.println(%22Sorted%20array%22)%3B%0A%20%20%20%20%20%20%20%20ob.printArray(arr)%3B%0A%20%20%20%20%7D%0A%7D\u201d message=\u201djava\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
Python<\/p>\n[pastacode lang=\u201dpython\u201d manual=\u201d%23%20Python%20program%20for%20implementation%20of%20Bubble%20Sort%0A%20%0Adef%20bubbleSort(arr)%3A%0A%20%20%20%20n%20%3D%20len(arr)%0A%20%0A%20%20%20%20%23%20Traverse%20through%20all%20array%20elements%0A%20%20%20%20for%20i%20in%20range(n)%3A%0A%20%0A%20%20%20%20%20%20%20%20%23%20Last%20i%20elements%20are%20already%20in%20place%0A%20%20%20%20%20%20%20%20for%20j%20in%20range(0%2C%20n-i-1)%3A%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20traverse%20the%20array%20from%200%20to%20n-i-1%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20Swap%20if%20the%20element%20found%20is%20greater%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%20than%20the%20next%20element%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20arr%5Bj%5D%20%3E%20arr%5Bj%2B1%5D%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20arr%5Bj%5D%2C%20arr%5Bj%2B1%5D%20%3D%20arr%5Bj%2B1%5D%2C%20arr%5Bj%5D%0A%20%0A%23%20Driver%20code%20to%20test%20above%0Aarr%20%3D%20%5B64%2C%2034%2C%2025%2C%2012%2C%2022%2C%2011%2C%2090%5D%0A%20%0AbubbleSort(arr)%0A%20%0Aprint%20(%22Sorted%20array%20is%3A%22)%0Afor%20i%20in%20range(len(arr))%3A%0A%20%20%20%20print%20(%22%25d%22%20%25arr%5Bi%5D)%2C%20\u2033 message=\u201dpython\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
\u00a0<\/p>\n
Output<\/p>\n
Sorted array: 11 12 22 25 34 64 90<\/p>\n
Illustration :<\/strong><\/p>\n Optimized Implementation:<\/strong> Output:<\/p>\n Sorted array: 11 12 22 25 34 64 90<\/p>\n Worst and Average Case Time Complexity: <\/strong>O(n*n). Worst case occurs when array is reverse sorted.<\/p>\n Best Case Time Complexity:<\/strong> O(n). Best case occurs when array is already sorted.<\/p>\n Auxiliary Space:<\/strong> O(1)<\/p>\n Boundary Cases:<\/strong> Bubble sort takes minimum time (Order of n) when elements are already sorted.<\/p>\n Sorting In Place: <\/strong>Yes<\/p>\n Stable:<\/strong> Yes<\/p>\n Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm. Bubble Sort – searching and sorting algorithm – Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping the adjacent elements .<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[83475,1,71670],"tags":[71128,71185,71133,70030,70892,71190,70273,71127,70461,71121,71150,71135,71179,71134,71141,70978,71157,71131,71155,70531,71177,70975,71137,71143,71166,71123,71140,71183,71182,71130,71126,71189,71169,71122,71171,71148,71129,71124,71173,71139,71132,70538,70780,71151,70833,71163,71152,71146,70533,71186,71181,71144,70895,71138,70271,70928,70017,71164,71160,71147,71158,70969,71176,71165,71168,71136,71170,71153,71172,70046,71145,71120,70016,70960,71154,71187,71125,71175,71162,70020,71161,70534,70652,71149,70967,71156,71142,71159,71191,71178,71188,70535,71180,71167,71184,71174],"class_list":["post-25061","post","type-post","status-publish","format-standard","hentry","category-bubble-sort","category-coding","category-searching-and-sorting","tag-algorithm-for-bubble-sort","tag-algorithm-for-bubble-sort-in-c","tag-algorithm-of-bubble-sort","tag-all-sorting-algorithms","tag-best-sorting-algorithm","tag-bible-search","tag-binary-sort","tag-bubble-short","tag-bubble-sort","tag-bubble-sort-algorithm","tag-bubble-sort-algorithm-in-c","tag-bubble-sort-algorithm-in-data-structure","tag-bubble-sort-algorithm-in-java","tag-bubble-sort-algorithm-with-example","tag-bubble-sort-animation","tag-bubble-sort-c","tag-bubble-sort-c-program","tag-bubble-sort-code","tag-bubble-sort-code-in-c","tag-bubble-sort-complexity","tag-bubble-sort-definition","tag-bubble-sort-example","tag-bubble-sort-example-step-by-step","tag-bubble-sort-explanation","tag-bubble-sort-game","tag-bubble-sort-in-c","tag-bubble-sort-in-c-program","tag-bubble-sort-in-c-with-explanation","tag-bubble-sort-in-cpp","tag-bubble-sort-in-data-structure","tag-bubble-sort-in-java","tag-bubble-sort-in-java-program","tag-bubble-sort-in-python","tag-bubble-sort-java","tag-bubble-sort-java-code","tag-bubble-sort-logic","tag-bubble-sort-program","tag-bubble-sort-program-in-c","tag-bubble-sort-program-in-java","tag-bubble-sort-pseudocode","tag-bubble-sort-python","tag-bubble-sort-time-complexity","tag-bubblesort","tag-bucket-sort-algorithm","tag-c-array","tag-c-code-for-bubble-sort","tag-c-program-for-bubble-sort","tag-comparison-of-sorting-algorithms","tag-complexity-of-bubble-sort","tag-difference-between-bubble-sort-and-insertion-sort","tag-difference-between-bubble-sort-and-selection-sort","tag-different-sorting-algorithms","tag-fastest-sorting-algorithm","tag-flowchart-for-bubble-sort","tag-heap-sort","tag-heap-sort-algorithm","tag-insertion-sort-algorithm","tag-insertion-sort-algorithm-in-data-structure","tag-insertion-sort-in-data-structure","tag-java-program-for-bubble-sort","tag-java-sort","tag-java-sorting-algorithms","tag-java-sorting-program","tag-merge-sort-c","tag-pointer-array","tag-program-for-bubble-sort","tag-program-for-bubble-sort-in-c","tag-program-of-bubble-sort","tag-quick-sort-program","tag-quicksort","tag-quicksort-c","tag-selection-sort","tag-selection-sort-algorithm","tag-selection-sort-java","tag-short-bubble","tag-short-in-c","tag-sort-code","tag-sort-example","tag-sort-java","tag-sorting-algorithms","tag-sorting-algorithms-comparison","tag-sorting-algorithms-complexity","tag-sorting-algorithms-in-c","tag-sorting-algorithms-in-data-structures","tag-sorting-algorithms-java","tag-sorting-algorithms-with-examples","tag-sorting-in-data-structure","tag-sorting-program","tag-sorting-techniques-in-c","tag-sorting-techniques-in-data-structure","tag-the-complexity-of-bubble-sort-algorithm-is","tag-time-complexity-of-bubble-sort","tag-types-of-sorting-in-data-structure-with-examples","tag-what-is-bubble-sort","tag-what-is-bubble-sort-in-c","tag-what-is-sorting-in-data-structure"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25061","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=25061"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/25061\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=25061"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=25061"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=25061"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}![\"bubble](\"https:\/\/www.wikitechy.com\/technology\/wp-content\/uploads\/2017\/05\/bubble-sort1.png\")
<\/p>\n[ad type=\u201dbanner\u201d]\n
\nThe above function always runs O(n^2) time even if the array is sorted. It can be optimized by stopping the algorithm if inner loop didn\u2019t cause any swap.<\/p>\n[pastacode lang=\u201dc\u201d manual=\u201d%2F%2F%20Optimized%20implementation%20of%20Bubble%20sort%0A%23include%20%3Cstdio.h%3E%0A%20%0Avoid%20swap(int%20*xp%2C%20int%20*yp)%0A%7B%0A%20%20%20%20int%20temp%20%3D%20*xp%3B%0A%20%20%20%20*xp%20%3D%20*yp%3B%0A%20%20%20%20*yp%20%3D%20temp%3B%0A%7D%0A%20%0A%2F%2F%20An%20optimized%20version%20of%20Bubble%20Sort%0Avoid%20bubbleSort(int%20arr%5B%5D%2C%20int%20n)%0A%7B%0A%20%20%20int%20i%2C%20j%3B%0A%20%20%20bool%20swapped%3B%0A%20%20%20for%20(i%20%3D%200%3B%20i%20%3C%20n-1%3B%20i%2B%2B)%0A%20%20%20%7B%0A%20%20%20%20%20swapped%20%3D%20false%3B%0A%20%20%20%20%20for%20(j%20%3D%200%3B%20j%20%3C%20n-i-1%3B%20j%2B%2B)%0A%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20if%20(arr%5Bj%5D%20%3E%20arr%5Bj%2B1%5D)%0A%20%20%20%20%20%20%20%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20swap(%26arr%5Bj%5D%2C%20%26arr%5Bj%2B1%5D)%3B%0A%20%20%20%20%20%20%20%20%20%20%20swapped%20%3D%20true%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%7D%0A%20%0A%20%20%20%20%20%2F%2F%20IF%20no%20two%20elements%20were%20swapped%20by%20inner%20loop%2C%20then%20break%0A%20%20%20%20%20if%20(swapped%20%3D%3D%20false)%0A%20%20%20%20%20%20%20%20break%3B%0A%20%20%20%7D%0A%7D%0A%20%0A%2F*%20Function%20to%20print%20an%20array%20*%2F%0Avoid%20printArray(int%20arr%5B%5D%2C%20int%20size)%0A%7B%0A%20%20%20%20int%20i%3B%0A%20%20%20%20for%20(i%3D0%3B%20i%20%3C%20size%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20%20printf(%22%25d%20%22%2C%20arr%5Bi%5D)%3B%0A%20%20%20%20printf(%22%5Cn%22)%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20functions%0Aint%20main()%0A%7B%0A%20%20%20%20int%20arr%5B%5D%20%3D%20%7B64%2C%2034%2C%2025%2C%2012%2C%2022%2C%2011%2C%2090%7D%3B%0A%20%20%20%20int%20n%20%3D%20sizeof(arr)%2Fsizeof(arr%5B0%5D)%3B%0A%20%20%20%20bubbleSort(arr%2C%20n)%3B%0A%20%20%20%20printf(%22Sorted%20array%3A%20%5Cn%22)%3B%0A%20%20%20%20printArray(arr%2C%20n)%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dc\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n
\nIn computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"