{"id":247,"date":"2015-06-30T11:07:03","date_gmt":"2015-06-30T01:07:03","guid":{"rendered":"https:\/\/learn-java-by-example.com\/?p=247"},"modified":"2015-06-30T14:37:48","modified_gmt":"2015-06-30T04:37:48","slug":"bubble-sort","status":"publish","type":"post","link":"https:\/\/learn-java-by-example.com\/java\/bubble-sort\/","title":{"rendered":"Bubble Sort"},"content":{"rendered":"<p>The Bubble Sort algorithm gets it&#8217;s name from the fact that on each pass, one element of the array &#8216;bubbles&#8217; it&#8217;s way through to it&#8217;s correct (sorted) position in the array. Rather than me try and explain the details the following video gives a great visual demonstration of how the algorithm works. The source code is also heavily commented to explain how the bubble sort is implemented.<\/p>\n<p><span class=\"embed-youtube\" style=\"text-align:center; display: block;\"><iframe loading=\"lazy\" class=\"youtube-player\" width=\"640\" height=\"360\" src=\"https:\/\/www.youtube.com\/embed\/MtcrEhrt_K0?version=3&#038;rel=1&#038;showsearch=0&#038;showinfo=1&#038;iv_load_policy=1&#038;fs=1&#038;hl=en-US&#038;autohide=2&#038;wmode=transparent\" allowfullscreen=\"true\" style=\"border:0;\" sandbox=\"allow-scripts allow-same-origin allow-popups allow-presentation\"><\/iframe><\/span><\/p>\n<p>If you Google &#8220;Java Bubble Sort&#8221; you will be presented with a multitude of examples which use two loops to implement the bubble sort. Although these examples all correctly sort the array, the majority of them scan the entire array on each pass which is unnecessary. Remember that after each pass another element in the array is in the correct position, so each pass has less to check.<\/p>\n<p>Additionally if on any given pass we don&#8217;t swap any elements then we know that the array is correctly sorted and we <\/p>\n<pre class=\"brush: java; title: ; notranslate\" title=\"\">\r\npackage com.learnjava.math.sort;\r\n\r\nimport java.util.Random;\r\n\r\n\/**\r\n * Write a program to sort an array of numbers using a Bubble Sort\r\n *\r\n * @author https:\/\/learn-java-by-example.com\r\n *\r\n *\/\r\npublic class BubbleSort {\r\n\r\n\tpublic static void main(String[] args) {\r\n\r\n\t\t\/\/ Create an array of random numbers to sort\r\n\r\n\t\tint[] data = generateData();\r\n\r\n\t\t\/\/ Display the unsorted data\r\n\r\n\t\tSystem.out.println(&quot;Unsorted data:&quot;);\r\n\t\tprintArray(data);\r\n\r\n\t\t\/\/ Sort the array\r\n\r\n\t\tbubbleSort(data);\r\n\r\n\t\t\/\/ Display the sorted data\r\n\r\n\t\tSystem.out.println(&quot;Sorted data:&quot;);\r\n\t\tprintArray(data);\r\n\t}\r\n\r\n\tprivate static void bubbleSort(int[] data) {\r\n\r\n\t\tint n = data.length;\r\n\r\n\t\t\/\/ Assume the array initially unsorted\r\n\r\n\t\tboolean sorted = false;\r\n\r\n\t\t\/\/ Keep track of which pass we are on\r\n\t\t\/\/\r\n\t\t\/\/ A pass involves one trip through\r\n\t\t\/\/ the array comparing and swapping elements\r\n\t\t\/\/\r\n\t\t\/\/ After each pass (at least) one extra\r\n\t\t\/\/ element will be in the correct position\r\n\r\n\t\tint pass = 1;\r\n\r\n\t\t\/\/ We loop until the array is sorted\r\n\t\t\/\/ We know the array is sorted if we\r\n\t\t\/\/ do a complete pass without swapping any elements\r\n\r\n\t\twhile (!sorted) {\r\n\r\n\t\t\t\/\/ Initially assume it is sorted\r\n\t\t\t\/\/ We'll toggle this flag if a swap is needed\r\n\r\n\t\t\tsorted = true;\r\n\r\n\t\t\t\/\/ Perform a pass\r\n\t\t\t\/\/ After each pass we know another\r\n\t\t\t\/\/ element in the array is correctly sorted\r\n\t\t\t\/\/ So we don't need to loop through the entire array\r\n\r\n\t\t\tfor (int j=0; j&lt;n-pass; j++) {\r\n\r\n\t\t\t\t\/\/ Check if the value needs to be swapped or not\r\n\r\n\t\t\t\tif (data[j] &gt; data[j+1]) {\r\n\r\n\t\t\t\t\t\/\/ Swap values\r\n\r\n\t\t\t\t\tint temp = data[j];\r\n\t\t\t\t\tdata[j] = data[j+1];\r\n\t\t\t\t\tdata[j+1] = temp;\r\n\r\n\t\t\t\t\t\/\/ Array may not be sorted,\r\n\t\t\t\t\t\/\/ so need another pass\r\n\r\n\t\t\t\t\tsorted = false;\r\n\t\t\t\t}\r\n\t\t\t}\r\n\r\n\t\t\t\/\/ Print out the array after we have\r\n\t\t\t\/\/ finished each element to see the progress\r\n\r\n\t\t\tSystem.out.println(&quot;Pass &quot; + pass);\r\n\t\t\tprintArray(data);\r\n\r\n\t\t\tpass++;\r\n\t\t}\r\n\t}\r\n\r\n\tprivate static int[] generateData() {\r\n\t\tRandom random = new Random();\r\n\r\n\t\tint[] data = new int[10];\r\n\t\tfor (int i=0; i&lt;data.length; i++) {\r\n\t\t\tdata[i] = random.nextInt(100);\r\n\t\t}\r\n\t\treturn data;\r\n\t}\r\n\r\n\tprivate static void printArray(int[] data) {\r\n\t\tfor (int i=0; i&lt;data.length; i++) {\r\n\t\t\tSystem.out.print(data[i]);\r\n\t\t\tSystem.out.print(&quot;, &quot;);\r\n\t\t}\r\n\t\tSystem.out.println();\r\n\t}\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>The Bubble Sort algorithm gets it&#8217;s name from the fact that on each pass, one element of the array &#8216;bubbles&#8217; it&#8217;s way through to it&#8217;s correct (sorted) position in the array. Rather than me try and explain the details the following video gives a great visual demonstration of how the algorithm works. The source code&#8230;<\/p>\n","protected":false},"author":3,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"jetpack_publicize_message":"","jetpack_is_tweetstorm":false,"jetpack_publicize_feature_enabled":true,"jetpack_social_options":[]},"categories":[24,4],"tags":[69,43,6,33,66],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/p6Yyl2-3Z","jetpack-related-posts":[{"id":238,"url":"https:\/\/learn-java-by-example.com\/java\/selection-sort\/","url_meta":{"origin":247,"position":0},"title":"Selection Sort","date":"June 19, 2015","format":false,"excerpt":"When you are learning Java you are very likely going to be asked to write a program to sort values. We will start with one of the simpler sort algorithms, the Selection Sort (also known as an Exchange Sort). It's not a particularly efficient algorithm and really only suitable for\u2026","rel":"","context":"In &quot;Java&quot;","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":199,"url":"https:\/\/learn-java-by-example.com\/java\/pythagoras-theorem\/","url_meta":{"origin":247,"position":1},"title":"Pythagoras Theorem","date":"December 13, 2010","format":false,"excerpt":"One of our member students was asked to implement the Pythagoras Theorem using Java. This is a good opportunity to introduce the Math class which contains a collection of static methods for various mathematical functions. We need the square root method (sort) to calculate the hypotenuse, and can also use\u2026","rel":"","context":"In &quot;Java&quot;","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":182,"url":"https:\/\/learn-java-by-example.com\/java\/high-guessing-game\/","url_meta":{"origin":247,"position":2},"title":"High Low Guessing Game","date":"May 17, 2011","format":false,"excerpt":"The assignment here is to write a simple game where the user tries to guess a randomly selected number. After each guess the application tells the user if the guess is too high or too low. This is repeated until the user finally guesses the number. First thing we need\u2026","rel":"","context":"In &quot;Java&quot;","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":32,"url":"https:\/\/learn-java-by-example.com\/slider\/quality-java-code\/","url_meta":{"origin":247,"position":3},"title":"Quality Java Code","date":"June 1, 2011","format":false,"excerpt":"All our Java code is developed, tested and reviewed by developers with decades of Java experience. The code is also well commented allowing you to easily understand what is being done.","rel":"","context":"In &quot;Slider&quot;","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":25,"url":"https:\/\/learn-java-by-example.com\/slider\/learn-java-the-easy-way\/","url_meta":{"origin":247,"position":4},"title":"Learn Java the Easy Way","date":"January 1, 2011","format":false,"excerpt":"One of the easiest ways to learn Java programming is by studying examples of solutions to a variety of programming problems. \"Learn Java by Example\" is the perfect companion to anyone studying Java development, providing a wealth of example Java code to complement the coding skills being taught to you.","rel":"","context":"In &quot;Slider&quot;","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":37,"url":"https:\/\/learn-java-by-example.com\/slider\/great-support\/","url_meta":{"origin":247,"position":5},"title":"Great Support","date":"June 1, 2011","format":false,"excerpt":"All the Java code, examples and solutions are fully supported. We also make Java mentoring available to our members, the perfect companion as you are learning Java.","rel":"","context":"In &quot;Slider&quot;","img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/posts\/247"}],"collection":[{"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/users\/3"}],"replies":[{"embeddable":true,"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/comments?post=247"}],"version-history":[{"count":3,"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/posts\/247\/revisions"}],"predecessor-version":[{"id":250,"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/posts\/247\/revisions\/250"}],"wp:attachment":[{"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/media?parent=247"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/categories?post=247"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/learn-java-by-example.com\/wp-json\/wp\/v2\/tags?post=247"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}