Skip to content

Instantly share code, notes, and snippets.

@duangsuse

duangsuse/BubbleSorter.html

Created August 13, 2018 06:32
Show Gist options
  • Save duangsuse/b5d4a0c514db4301dcf5218c354db253 to your computer and use it in GitHub Desktop.
Save duangsuse/b5d4a0c514db4301dcf5218c354db253 to your computer and use it in GitHub Desktop.
Download ZIP
也不算是「quick」version，因为 wiki 上的那个版本也很快，对比一些国内的博客是少比较了n 次，但是，常量是不进大 O 表示法的
Raw
BubbleSorter.html
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<!-- NewPage -->
<html lang="en">
<head>
<meta charset="utf8">
<!-- Generated by javadoc (1.8.0_181) on Mon Aug 13 14:19:50 CST 2018 -->
<title>BubbleSorter</title>
<meta name="date" content="2018-08-13">
<style>
/* Javadoc style sheet */
/*
Overall document style
*/
@import url('resources/fonts/dejavu.css');
body {
background-color:#ffffff;
color:#353833;
font-family:'DejaVu Sans', Arial, Helvetica, sans-serif;
font-size:14px;
margin:0;
}
a:link, a:visited {
text-decoration:none;
color:#4A6782;
}
a:hover, a:focus {
text-decoration:none;
color:#bb7a2a;
}
a:active {
text-decoration:none;
color:#4A6782;
}
a[name] {
color:#353833;
}
a[name]:hover {
text-decoration:none;
color:#353833;
}
pre {
font-family:'DejaVu Sans Mono', monospace;
font-size:14px;
}
h1 {
font-size:20px;
}
h2 {
font-size:18px;
}
h3 {
font-size:16px;
font-style:italic;
}
h4 {
font-size:13px;
}
h5 {
font-size:12px;
}
h6 {
font-size:11px;
}
ul {
list-style-type:disc;
}
code, tt {
font-family:'DejaVu Sans Mono', monospace;
font-size:14px;
padding-top:4px;
margin-top:8px;
line-height:1.4em;
}
dt code {
font-family:'DejaVu Sans Mono', monospace;
font-size:14px;
padding-top:4px;
}
table tr td dt code {
font-family:'DejaVu Sans Mono', monospace;
font-size:14px;
vertical-align:top;
padding-top:4px;
}
sup {
font-size:8px;
}
/*
Document title and Copyright styles
*/
.clear {
clear:both;
height:0px;
overflow:hidden;
}
.aboutLanguage {
float:right;
padding:0px 21px;
font-size:11px;
z-index:200;
margin-top:-9px;
}
.legalCopy {
margin-left:.5em;
}
.bar a, .bar a:link, .bar a:visited, .bar a:active {
color:#FFFFFF;
text-decoration:none;
}
.bar a:hover, .bar a:focus {
color:#bb7a2a;
}
.tab {
background-color:#0066FF;
color:#ffffff;
padding:8px;
width:5em;
font-weight:bold;
}
/*
Navigation bar styles
*/
.bar {
background-color:#4D7A97;
color:#FFFFFF;
padding:.8em .5em .4em .8em;
height:auto;/*height:1.8em;*/
font-size:11px;
margin:0;
}
.topNav {
background-color:#4D7A97;
color:#FFFFFF;
float:left;
padding:0;
width:100%;
clear:right;
height:2.8em;
padding-top:10px;
overflow:hidden;
font-size:12px;
}
.bottomNav {
margin-top:10px;
background-color:#4D7A97;
color:#FFFFFF;
float:left;
padding:0;
width:100%;
clear:right;
height:2.8em;
padding-top:10px;
overflow:hidden;
font-size:12px;
}
.subNav {
background-color:#dee3e9;
float:left;
width:100%;
overflow:hidden;
font-size:12px;
}
.subNav div {
clear:left;
float:left;
padding:0 0 5px 6px;
text-transform:uppercase;
}
ul.navList, ul.subNavList {
float:left;
margin:0 25px 0 0;
padding:0;
}
ul.navList li{
list-style:none;
float:left;
padding: 5px 6px;
text-transform:uppercase;
}
ul.subNavList li{
list-style:none;
float:left;
}
.topNav a:link, .topNav a:active, .topNav a:visited, .bottomNav a:link, .bottomNav a:active, .bottomNav a:visited {
color:#FFFFFF;
text-decoration:none;
text-transform:uppercase;
}
.topNav a:hover, .bottomNav a:hover {
text-decoration:none;
color:#bb7a2a;
text-transform:uppercase;
}
.navBarCell1Rev {
background-color:#F8981D;
color:#253441;
margin: auto 5px;
}
.skipNav {
position:absolute;
top:auto;
left:-9999px;
overflow:hidden;
}
/*
Page header and footer styles
*/
.header, .footer {
clear:both;
margin:0 20px;
padding:5px 0 0 0;
}
.indexHeader {
margin:10px;
position:relative;
}
.indexHeader span{
margin-right:15px;
}
.indexHeader h1 {
font-size:13px;
}
.title {
color:#2c4557;
margin:10px 0;
}
.subTitle {
margin:5px 0 0 0;
}
.header ul {
margin:0 0 15px 0;
padding:0;
}
.footer ul {
margin:20px 0 5px 0;
}
.header ul li, .footer ul li {
list-style:none;
font-size:13px;
}
/*
Heading styles
*/
div.details ul.blockList ul.blockList ul.blockList li.blockList h4, div.details ul.blockList ul.blockList ul.blockListLast li.blockList h4 {
background-color:#dee3e9;
border:1px solid #d0d9e0;
margin:0 0 6px -8px;
padding:7px 5px;
}
ul.blockList ul.blockList ul.blockList li.blockList h3 {
background-color:#dee3e9;
border:1px solid #d0d9e0;
margin:0 0 6px -8px;
padding:7px 5px;
}
ul.blockList ul.blockList li.blockList h3 {
padding:0;
margin:15px 0;
}
ul.blockList li.blockList h2 {
padding:0px 0 20px 0;
}
/*
Page layout container styles
*/
.contentContainer, .sourceContainer, .classUseContainer, .serializedFormContainer, .constantValuesContainer {
clear:both;
padding:10px 20px;
position:relative;
}
.indexContainer {
margin:10px;
position:relative;
font-size:12px;
}
.indexContainer h2 {
font-size:13px;
padding:0 0 3px 0;
}
.indexContainer ul {
margin:0;
padding:0;
}
.indexContainer ul li {
list-style:none;
padding-top:2px;
}
.contentContainer .description dl dt, .contentContainer .details dl dt, .serializedFormContainer dl dt {
font-size:12px;
font-weight:bold;
margin:10px 0 0 0;
color:#4E4E4E;
}
.contentContainer .description dl dd, .contentContainer .details dl dd, .serializedFormContainer dl dd {
margin:5px 0 10px 0px;
font-size:14px;
font-family:'DejaVu Sans Mono',monospace;
}
.serializedFormContainer dl.nameValue dt {
margin-left:1px;
font-size:1.1em;
display:inline;
font-weight:bold;
}
.serializedFormContainer dl.nameValue dd {
margin:0 0 0 1px;
font-size:1.1em;
display:inline;
}
/*
List styles
*/
ul.horizontal li {
display:inline;
font-size:0.9em;
}
ul.inheritance {
margin:0;
padding:0;
}
ul.inheritance li {
display:inline;
list-style:none;
}
ul.inheritance li ul.inheritance {
margin-left:15px;
padding-left:15px;
padding-top:1px;
}
ul.blockList, ul.blockListLast {
margin:10px 0 10px 0;
padding:0;
}
ul.blockList li.blockList, ul.blockListLast li.blockList {
list-style:none;
margin-bottom:15px;
line-height:1.4;
}
ul.blockList ul.blockList li.blockList, ul.blockList ul.blockListLast li.blockList {
padding:0px 20px 5px 10px;
border:1px solid #ededed;
background-color:#f8f8f8;
}
ul.blockList ul.blockList ul.blockList li.blockList, ul.blockList ul.blockList ul.blockListLast li.blockList {
padding:0 0 5px 8px;
background-color:#ffffff;
border:none;
}
ul.blockList ul.blockList ul.blockList ul.blockList li.blockList {
margin-left:0;
padding-left:0;
padding-bottom:15px;
border:none;
}
ul.blockList ul.blockList ul.blockList ul.blockList li.blockListLast {
list-style:none;
border-bottom:none;
padding-bottom:0;
}
table tr td dl, table tr td dl dt, table tr td dl dd {
margin-top:0;
margin-bottom:1px;
}
/*
Table styles
*/
.overviewSummary, .memberSummary, .typeSummary, .useSummary, .constantsSummary, .deprecatedSummary {
width:100%;
border-left:1px solid #EEE;
border-right:1px solid #EEE;
border-bottom:1px solid #EEE;
}
.overviewSummary, .memberSummary {
padding:0px;
}
.overviewSummary caption, .memberSummary caption, .typeSummary caption,
.useSummary caption, .constantsSummary caption, .deprecatedSummary caption {
position:relative;
text-align:left;
background-repeat:no-repeat;
color:#253441;
font-weight:bold;
clear:none;
overflow:hidden;
padding:0px;
padding-top:10px;
padding-left:1px;
margin:0px;
white-space:pre;
}
.overviewSummary caption a:link, .memberSummary caption a:link, .typeSummary caption a:link,
.useSummary caption a:link, .constantsSummary caption a:link, .deprecatedSummary caption a:link,
.overviewSummary caption a:hover, .memberSummary caption a:hover, .typeSummary caption a:hover,
.useSummary caption a:hover, .constantsSummary caption a:hover, .deprecatedSummary caption a:hover,
.overviewSummary caption a:active, .memberSummary caption a:active, .typeSummary caption a:active,
.useSummary caption a:active, .constantsSummary caption a:active, .deprecatedSummary caption a:active,
.overviewSummary caption a:visited, .memberSummary caption a:visited, .typeSummary caption a:visited,
.useSummary caption a:visited, .constantsSummary caption a:visited, .deprecatedSummary caption a:visited {
color:#FFFFFF;
}
.overviewSummary caption span, .memberSummary caption span, .typeSummary caption span,
.useSummary caption span, .constantsSummary caption span, .deprecatedSummary caption span {
white-space:nowrap;
padding-top:5px;
padding-left:12px;
padding-right:12px;
padding-bottom:7px;
display:inline-block;
float:left;
background-color:#F8981D;
border: none;
height:16px;
}
.memberSummary caption span.activeTableTab span {
white-space:nowrap;
padding-top:5px;
padding-left:12px;
padding-right:12px;
margin-right:3px;
display:inline-block;
float:left;
background-color:#F8981D;
height:16px;
}
.memberSummary caption span.tableTab span {
white-space:nowrap;
padding-top:5px;
padding-left:12px;
padding-right:12px;
margin-right:3px;
display:inline-block;
float:left;
background-color:#4D7A97;
height:16px;
}
.memberSummary caption span.tableTab, .memberSummary caption span.activeTableTab {
padding-top:0px;
padding-left:0px;
padding-right:0px;
background-image:none;
float:none;
display:inline;
}
.overviewSummary .tabEnd, .memberSummary .tabEnd, .typeSummary .tabEnd,
.useSummary .tabEnd, .constantsSummary .tabEnd, .deprecatedSummary .tabEnd {
display:none;
width:5px;
position:relative;
float:left;
background-color:#F8981D;
}
.memberSummary .activeTableTab .tabEnd {
display:none;
width:5px;
margin-right:3px;
position:relative;
float:left;
background-color:#F8981D;
}
.memberSummary .tableTab .tabEnd {
display:none;
width:5px;
margin-right:3px;
position:relative;
background-color:#4D7A97;
float:left;
}
.overviewSummary td, .memberSummary td, .typeSummary td,
.useSummary td, .constantsSummary td, .deprecatedSummary td {
text-align:left;
padding:0px 0px 12px 10px;
}
th.colOne, th.colFirst, th.colLast, .useSummary th, .constantsSummary th,
td.colOne, td.colFirst, td.colLast, .useSummary td, .constantsSummary td{
vertical-align:top;
padding-right:0px;
padding-top:8px;
padding-bottom:3px;
}
th.colFirst, th.colLast, th.colOne, .constantsSummary th {
background:#dee3e9;
text-align:left;
padding:8px 3px 3px 7px;
}
td.colFirst, th.colFirst {
white-space:nowrap;
font-size:13px;
}
td.colLast, th.colLast {
font-size:13px;
}
td.colOne, th.colOne {
font-size:13px;
}
.overviewSummary td.colFirst, .overviewSummary th.colFirst,
.useSummary td.colFirst, .useSummary th.colFirst,
.overviewSummary td.colOne, .overviewSummary th.colOne,
.memberSummary td.colFirst, .memberSummary th.colFirst,
.memberSummary td.colOne, .memberSummary th.colOne,
.typeSummary td.colFirst{
width:25%;
vertical-align:top;
}
td.colOne a:link, td.colOne a:active, td.colOne a:visited, td.colOne a:hover, td.colFirst a:link, td.colFirst a:active, td.colFirst a:visited, td.colFirst a:hover, td.colLast a:link, td.colLast a:active, td.colLast a:visited, td.colLast a:hover, .constantValuesContainer td a:link, .constantValuesContainer td a:active, .constantValuesContainer td a:visited, .constantValuesContainer td a:hover {
font-weight:bold;
}
.tableSubHeadingColor {
background-color:#EEEEFF;
}
.altColor {
background-color:#FFFFFF;
}
.rowColor {
background-color:#EEEEEF;
}
/*
Content styles
*/
.description pre {
margin-top:0;
}
.deprecatedContent {
margin:0;
padding:10px 0;
}
.docSummary {
padding:0;
}
ul.blockList ul.blockList ul.blockList li.blockList h3 {
font-style:normal;
}
div.block {
font-size:14px;
font-family:'DejaVu Serif', Georgia, "Times New Roman", Times, serif;
}
td.colLast div {
padding-top:0px;
}
td.colLast a {
padding-bottom:3px;
}
/*
Formatting effect styles
*/
.sourceLineNo {
color:green;
padding:0 30px 0 0;
}
h1.hidden {
visibility:hidden;
overflow:hidden;
font-size:10px;
}
.block {
display:block;
margin:3px 10px 2px 0px;
color:#474747;
}
.deprecatedLabel, .descfrmTypeLabel, .memberNameLabel, .memberNameLink,
.overrideSpecifyLabel, .packageHierarchyLabel, .paramLabel, .returnLabel,
.seeLabel, .simpleTagLabel, .throwsLabel, .typeNameLabel, .typeNameLink {
font-weight:bold;
}
.deprecationComment, .emphasizedPhrase, .interfaceName {
font-style:italic;
}
div.block div.block span.deprecationComment, div.block div.block span.emphasizedPhrase,
div.block div.block span.interfaceName {
font-style:normal;
}
div.contentContainer ul.blockList li.blockList h2{
padding-bottom:0px;
}
</style>
<script type="text/javascript">
function show(type)
{
count = 0;
for (var key in methods) {
var row = document.getElementById(key);
if ((methods[key] & type) != 0) {
row.style.display = '';
row.className = (count++ % 2) ? rowColor : altColor;
}
else
row.style.display = 'none';
}
updateTabs(type);
}
function updateTabs(type)
{
for (var value in tabs) {
var sNode = document.getElementById(tabs[value][0]);
var spanNode = sNode.firstChild;
if (value == type) {
sNode.className = activeTableTab;
spanNode.innerHTML = tabs[value][1];
}
else {
sNode.className = tableTab;
spanNode.innerHTML = "<a href=\"javascript:show("+ value + ");\">" + tabs[value][1] + "</a>";
}
}
}
</script>
</head>
<body>
<script type="text/javascript"><!--
try {
if (location.href.indexOf('is-external=true') == -1) {
parent.document.title="BubbleSorter";
}
}
catch(err) {
}
//-->
var methods = {"i0":10,"i1":10};
var tabs = {65535:["t0","All Methods"],2:["t2","Instance Methods"],8:["t4","Concrete Methods"]};
var altColor = "altColor";
var rowColor = "rowColor";
var tableTab = "tableTab";
var activeTableTab = "activeTableTab";
</script>
<noscript>
<div>JavaScript is disabled on your browser.</div>
</noscript>
<!-- ========= START OF TOP NAVBAR ======= -->
<div class="topNav"><a name="navbar.top">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.top" title="Skip navigation links">Skip navigation links</a></div>
<a name="navbar.top.firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../org/duangsuse/package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li>Prev&nbsp;Class</li>
<li>Next&nbsp;Class</li>
</ul>
<ul class="navList">
<li><a href="../../index.html?org/duangsuse/BubbleSorter.html" target="_top">Frames</a></li>
<li><a href="BubbleSorter.html" target="_top">No&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_top">
<li><a href="../../allclasses-noframe.html">All&nbsp;Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_top");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li><a href="#field.summary">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li><a href="#field.detail">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.detail">Method</a></li>
</ul>
</div>
<a name="skip.navbar.top">
<!-- -->
</a></div>
<!-- ========= END OF TOP NAVBAR ========= -->
<!-- ======== START OF CLASS DATA ======== -->
<div class="header">
<div class="subTitle">org.duangsuse</div>
<h2 title="Class BubbleSorter" class="title">Class BubbleSorter&lt;T extends java.lang.Comparable&lt;? super T&gt;&gt;</h2>
</div>
<div class="contentContainer">
<ul class="inheritance">
<li>java.lang.Object</li>
<li>
<ul class="inheritance">
<li>org.duangsuse.BubbleSorter&lt;T&gt;</li>
</ul>
</li>
</ul>
<div class="description">
<ul class="blockList">
<li class="blockList">
<dl>
<dt><span class="paramLabel">Type Parameters:</span></dt>
<dd><code>T</code> - Item type of target array to sort</dd>
</dl>
<hr>
<br>
<pre>public class <span class="typeNameLabel">BubbleSorter&lt;T extends java.lang.Comparable&lt;? super T&gt;&gt;</span>
extends java.lang.Object</pre>
<div class="block">A simple packaged bubble sort algorithm
<br>
<h2>Algorithm</h2>
<br>
"Quick" version of <a href="https://en.wikipedia.org/wiki/Bubble_sort">Bubble sort</a>
<pre><code>
start = 0 end = 4
[100, 10, 12 , 43, 223] // i = 0 j = 0
[100, 10 &lt;-&gt; 12, 43, 223] // j = 1
[100, 12, 10 &lt;-&gt; 43] // j = 2
[100, 12, 43, 10 &lt;-&gt; 223] // j = 3
[100, 12, 43, 223, 10]
// Next iteration i = 1, end -= 1
[100, 12 &lt;-&gt; 43, 223], 10 // j = 1
[100, 43, 12 &lt;-&gt; 223], 10 // j = 2
[100, 43, 223, 12], 10 // j = 3
// Next iteration i = 2 end -= 2
[100, 43 &lt;-&gt; 223], 12, 10 // j = 1
[100, 223, 43], 12, 10 // j = 2
// Next iteration i = 3 end -= 3
[100 &lt;-&gt; 223], 43, 12, 10 // j = 0
[220, 100], 43, 12, 10 // j = 1
result: 200, 100, 43, 21, 10
...
</code></pre>
<h2>Implementation</h2>
<br>
<pre><code>
for (i = start; i &lt; end; i++) // For array size
for (j = start; j &lt; end - (i - start); j++) // Compare and swap
// Swap if list[j] less than list[j + 1]
</code></pre>
<br>
<h2>Performance</h2>
<br>
<strong>O(n ^ 2)</strong> for <strong>worst case</strong> and <strong>best case</strong></div>
</li>
</ul>
</div>
<div class="summary">
<ul class="blockList">
<li class="blockList">
<!-- =========== FIELD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="field.summary">
<!-- -->
</a>
<h3>Field Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Field Summary table, listing fields, and an explanation">
<caption><span>Fields</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Field and Description</th>
</tr>
<tr class="altColor">
<td class="colFirst"><code>boolean</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../org/duangsuse/BubbleSorter.html#DEBUG">DEBUG</a></span></code>
<div class="block">Should use debug println</div>
</td>
</tr>
</table>
</li>
</ul>
<!-- ======== CONSTRUCTOR SUMMARY ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor.summary">
<!-- -->
</a>
<h3>Constructor Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Constructor Summary table, listing constructors, and an explanation">
<caption><span>Constructors</span><span class="tabEnd">&nbsp;</span></caption>
<tr>
<th class="colOne" scope="col">Constructor and Description</th>
</tr>
<tr class="altColor">
<td class="colOne"><code><span class="memberNameLink"><a href="../../org/duangsuse/BubbleSorter.html#BubbleSorter--">BubbleSorter</a></span>()</code>&nbsp;</td>
</tr>
</table>
</li>
</ul>
<!-- ========== METHOD SUMMARY =========== -->
<ul class="blockList">
<li class="blockList"><a name="method.summary">
<!-- -->
</a>
<h3>Method Summary</h3>
<table class="memberSummary" border="0" cellpadding="3" cellspacing="0" summary="Method Summary table, listing methods, and an explanation">
<caption><span id="t0" class="activeTableTab"><span>All Methods</span><span class="tabEnd">&nbsp;</span></span><span id="t2" class="tableTab"><span><a href="javascript:show(2);">Instance Methods</a></span><span class="tabEnd">&nbsp;</span></span><span id="t4" class="tableTab"><span><a href="javascript:show(8);">Concrete Methods</a></span><span class="tabEnd">&nbsp;</span></span></caption>
<tr>
<th class="colFirst" scope="col">Modifier and Type</th>
<th class="colLast" scope="col">Method and Description</th>
</tr>
<tr id="i0" class="altColor">
<td class="colFirst"><code><a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../org/duangsuse/BubbleSorter.html#bubbleSort-T:A-">bubbleSort</a></span>(<a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]&nbsp;list)</code>
<div class="block">Sort a list, bigger item result in front
<a href="../../org/duangsuse/BubbleSorter.html#bubbleSort-T:A-int-int-"><code>bubbleSort(Comparable[], int, int)</code></a></div>
</td>
</tr>
<tr id="i1" class="rowColor">
<td class="colFirst"><code><a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]</code></td>
<td class="colLast"><code><span class="memberNameLink"><a href="../../org/duangsuse/BubbleSorter.html#bubbleSort-T:A-int-int-">bubbleSort</a></span>(<a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]&nbsp;list,
int&nbsp;start,
int&nbsp;end)</code>
<div class="block">Sort a part of comparable list, bigger item result in front</div>
</td>
</tr>
</table>
<ul class="blockList">
<li class="blockList"><a name="methods.inherited.from.class.java.lang.Object">
<!-- -->
</a>
<h3>Methods inherited from class&nbsp;java.lang.Object</h3>
<code>clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait</code></li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
<div class="details">
<ul class="blockList">
<li class="blockList">
<!-- ============ FIELD DETAIL =========== -->
<ul class="blockList">
<li class="blockList"><a name="field.detail">
<!-- -->
</a>
<h3>Field Detail</h3>
<a name="DEBUG">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>DEBUG</h4>
<pre>public&nbsp;boolean DEBUG</pre>
<div class="block">Should use debug println</div>
</li>
</ul>
</li>
</ul>
<!-- ========= CONSTRUCTOR DETAIL ======== -->
<ul class="blockList">
<li class="blockList"><a name="constructor.detail">
<!-- -->
</a>
<h3>Constructor Detail</h3>
<a name="BubbleSorter--">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>BubbleSorter</h4>
<pre>public&nbsp;BubbleSorter()</pre>
</li>
</ul>
</li>
</ul>
<!-- ============ METHOD DETAIL ========== -->
<ul class="blockList">
<li class="blockList"><a name="method.detail">
<!-- -->
</a>
<h3>Method Detail</h3>
<a name="bubbleSort-java.lang.Comparable:A-">
<!-- -->
</a><a name="bubbleSort-T:A-">
<!-- -->
</a>
<ul class="blockList">
<li class="blockList">
<h4>bubbleSort</h4>
<pre>public&nbsp;<a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]&nbsp;bubbleSort(<a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]&nbsp;list)</pre>
<div class="block">Sort a list, bigger item result in front
<a href="../../org/duangsuse/BubbleSorter.html#bubbleSort-T:A-int-int-"><code>bubbleSort(Comparable[], int, int)</code></a></div>
<dl>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>list</code> - list to sort</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>sorted list, or <code>null</code> if start or end index is illegal</dd>
</dl>
</li>
</ul>
<a name="bubbleSort-java.lang.Comparable:A-int-int-">
<!-- -->
</a><a name="bubbleSort-T:A-int-int-">
<!-- -->
</a>
<ul class="blockListLast">
<li class="blockList">
<h4>bubbleSort</h4>
<pre>public&nbsp;<a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]&nbsp;bubbleSort(<a href="../../org/duangsuse/BubbleSorter.html" title="type parameter in BubbleSorter">T</a>[]&nbsp;list,
int&nbsp;start,
int&nbsp;end)</pre>
<div class="block">Sort a part of comparable list, bigger item result in front</div>
<dl>
<dt><span class="paramLabel">Parameters:</span></dt>
<dd><code>list</code> - list to sort</dd>
<dd><code>start</code> - sort start position</dd>
<dd><code>end</code> - sort end position</dd>
<dt><span class="returnLabel">Returns:</span></dt>
<dd>sorted list, or <code>null</code> if start or end index is illegal</dd>
</dl>
</li>
</ul>
</li>
</ul>
</li>
</ul>
</div>
</div>
<!-- ========= END OF CLASS DATA ========= -->
<!-- ======= START OF BOTTOM NAVBAR ====== -->
<div class="bottomNav"><a name="navbar.bottom">
<!-- -->
</a>
<div class="skipNav"><a href="#skip.navbar.bottom" title="Skip navigation links">Skip navigation links</a></div>
<a name="navbar.bottom.firstrow">
<!-- -->
</a>
<ul class="navList" title="Navigation">
<li><a href="../../org/duangsuse/package-summary.html">Package</a></li>
<li class="navBarCell1Rev">Class</li>
<li><a href="../../deprecated-list.html">Deprecated</a></li>
<li><a href="../../help-doc.html">Help</a></li>
</ul>
</div>
<div class="subNav">
<ul class="navList">
<li>Prev&nbsp;Class</li>
<li>Next&nbsp;Class</li>
</ul>
<ul class="navList">
<li><a href="../../index.html?org/duangsuse/BubbleSorter.html" target="_top">Frames</a></li>
<li><a href="BubbleSorter.html" target="_top">No&nbsp;Frames</a></li>
</ul>
<ul class="navList" id="allclasses_navbar_bottom">
<li><a href="../../allclasses-noframe.html">All&nbsp;Classes</a></li>
</ul>
<div>
<script type="text/javascript"><!--
allClassesLink = document.getElementById("allclasses_navbar_bottom");
if(window==top) {
allClassesLink.style.display = "block";
}
else {
allClassesLink.style.display = "none";
}
//-->
</script>
</div>
<div>
<ul class="subNavList">
<li>Summary:&nbsp;</li>
<li>Nested&nbsp;|&nbsp;</li>
<li><a href="#field.summary">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.summary">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.summary">Method</a></li>
</ul>
<ul class="subNavList">
<li>Detail:&nbsp;</li>
<li><a href="#field.detail">Field</a>&nbsp;|&nbsp;</li>
<li><a href="#constructor.detail">Constr</a>&nbsp;|&nbsp;</li>
<li><a href="#method.detail">Method</a></li>
</ul>
</div>
<a name="skip.navbar.bottom">
<!-- -->
</a></div>
<!-- ======== END OF BOTTOM NAVBAR ======= -->
</body>
</html>
Raw
BubbleSorter.java
package org.duangsuse;
import java.util.Arrays;
/**
* A simple packaged bubble sort algorithm
*
* <br>
* <h2>Algorithm</h2>
* <br>
* "Quick" version of <a href="https://en.wikipedia.org/wiki/Bubble_sort">Bubble sort</a>
*
* <pre>{@code
* start = 0 end = 4
*
* [100, 10, 12 , 43, 223] // i = 0 j = 0
* [100, 10 <-> 12, 43, 223] // j = 1
* [100, 12, 10 <-> 43] // j = 2
* [100, 12, 43, 10 <-> 223] // j = 3
* [100, 12, 43, 223, 10]
*
* // Next iteration i = 1, end -= 1
* [100, 12 <-> 43, 223], 10 // j = 1
* [100, 43, 12 <-> 223], 10 // j = 2
* [100, 43, 223, 12], 10 // j = 3
*
* // Next iteration i = 2 end -= 2
* [100, 43 <-> 223], 12, 10 // j = 1
* [100, 223, 43], 12, 10 // j = 2
*
* // Next iteration i = 3 end -= 3
*
* [100 <-> 223], 43, 12, 10 // j = 0
* [220, 100], 43, 12, 10 // j = 1
*
* result: 200, 100, 43, 21, 10
* ...
* }</pre>
*
* <h2>Implementation</h2>
*
* <br>
* <pre>{@code
* for (i = start; i < end; i++) // For array size
* for (j = start; j < end - (i - start); j++) // Compare and swap
* // Swap if list[j] less than list[j + 1]
* }</pre>
* <br>
* <h2>Performance</h2>
*
* <br>
* <strong>O(n ^ 2)</strong> for <strong>worst case</strong> and <strong>best case</strong>
*
* @param <T> Item type of target array to sort
* @author duangsuse
* @version 0.1.0
*/
@SuppressWarnings("WeakerAccess")
public class BubbleSorter<T extends Comparable<? super T>> {
/**
* Should use debug println
*/
public boolean DEBUG = false;
/**
* Sort a list, bigger item result in front
* {@link BubbleSorter#bubbleSort(Comparable[], int, int)}
*
* @param list list to sort
* @return sorted list, or {@code null} if start or end index is illegal
*/
@SuppressWarnings("WeakerAccess")
public T[] bubbleSort(T[] list) {
return bubbleSort(list, 0, list.length - 1);
}
/**
* Sort a part of comparable list, bigger item result in front
*
* @param list list to sort
* @param start sort start position
* @param end sort end position
* @return sorted list, or {@code null} if start or end index is illegal
*/
@SuppressWarnings("WeakerAccess")
public T[] bubbleSort(T[] list, int start, int end) {
if (start > end || start >= list.length || end >= list.length)
return null;
T[] ret = list.clone();
int i, j;
T temp;
for (i = start; i < end; i++) {
debug(String.format("Iteration: %1$s", i));
for (j = start; j < end - (i - start); j++) {
debug(String.format("BIteration: %1$s", j));
if (ret[j].compareTo(ret[j + 1]) < 0) { // list[j] smaller than list[j + 1]
debug(String.format("Swap: %1$s %2$s", ret[j], ret[j + 1]));
temp = ret[j];
ret[j] = ret[j + 1];
ret[j + 1] = temp;
debug(String.format("Swapped: %1$s %2$s", ret[j], ret[j + 1]));
debug(String.format("Swapped: %1$s", Arrays.asList(ret).toString()));
}
}
}
return ret;
}
/**
* Put a debug message to console stdout
* {@link BubbleSorter#DEBUG}
*
* @param msg message to put
*/
private void debug(CharSequence msg) {
if (DEBUG)
System.out.println(msg);
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment