-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathbubble-sort.html
More file actions
206 lines (181 loc) · 50.2 KB
/
bubble-sort.html
File metadata and controls
206 lines (181 loc) · 50.2 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Bubble Sort</title>
<meta name="generator" content="VuePress 1.8.2">
<link rel="icon" type="image/png" sizes="32x32" href="/favicon-32x32.png">
<link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.png">
<link rel="manifest" href="/site.webmanifest">
<link rel="apple-touch-icon" sizes="180x180" href="/apple-touch-icon.png">
<link rel="mask-icon" href="/safari-pinned-tab.svg" color="#5bbad5">
<meta name="description" content="Bubble Sort, Implementation in C & C++, Implementation in Javascript, Implementation in C#, Implementation in Java, Python Implementation">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Bubble Sort">
<meta property="og:description" content="Bubble Sort, Implementation in C & C++, Implementation in Javascript, Implementation in C#, Implementation in Java, Python Implementation">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/bubble-sort.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Bubble Sort">
<meta name="twitter:description" content="Bubble Sort, Implementation in C & C++, Implementation in Javascript, Implementation in C#, Implementation in Java, Python Implementation">
<meta name="twitter:url" content="/algorithm/bubble-sort.html">
<meta name="twitter:card" content="summary_large_image">
<meta name="twitter:image" content="/logo.png">
<meta name="theme-color" content="#ffffff">
<meta name="apple-mobile-web-app-capable" content="yes">
<meta name="apple-mobile-web-app-status-bar-style" content="black">
<meta name="msapplication-TileImage" content="/mstile-150x150.png">
<meta name="msapplication-TileColor" content="#da532c">
<meta name="google-site-verification" content="76_rKXgwMVIjd-axJC_1zPV9OS4mEjvtgjYOWVkAdnQ">
<link rel="preload" href="/assets/css/0.styles.60619e34.css" as="style"><link rel="preload" href="/assets/js/app.1779e102.js" as="script"><link rel="preload" href="/assets/js/3.2cfa8016.js" as="script"><link rel="preload" href="/assets/js/22.ac8a50ef.js" as="script">
<link rel="stylesheet" href="/assets/css/0.styles.60619e34.css">
</head>
<body>
<div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">DevTut</span></a> <div class="links"><form id="search-form" role="search" class="algolia-search-wrapper search-box"><input id="algolia-search-input" class="search-query"></form> <nav class="nav-links can-hide"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"> <a href="https://github.com/devtut/generate" target="_blank" rel="noopener noreferrer" class="repo-link">
GitHub
<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></nav> <ul class="sidebar-links"><li><section class="sidebar-group depth-0"><p class="sidebar-heading open"><span>Algorithm</span> <!----></p> <ul class="sidebar-links sidebar-group-items"><li><a href="/algorithm/" aria-current="page" class="sidebar-link">Disclaimer</a></li><li><a href="/algorithm/getting-started-with-algorithm.html" class="sidebar-link">Getting started with algorithm</a></li><li><a href="/algorithm/algorithm-complexity.html" class="sidebar-link">Algorithm Complexity</a></li><li><a href="/algorithm/big-o-notation.html" class="sidebar-link">Big-O Notation</a></li><li><a href="/algorithm/trees.html" class="sidebar-link">Trees</a></li><li><a href="/algorithm/binary-search-trees.html" class="sidebar-link">Binary Search Trees</a></li><li><a href="/algorithm/check-if-a-tree-is-bst-or-not.html" class="sidebar-link">Check if a tree is BST or not</a></li><li><a href="/algorithm/binary-tree-traversals.html" class="sidebar-link">Binary Tree traversals</a></li><li><a href="/algorithm/lowest-common-ancestor-of-a-binary-tree.html" class="sidebar-link">Lowest common ancestor of a Binary Tree</a></li><li><a href="/algorithm/graph.html" class="sidebar-link">Graph</a></li><li><a href="/algorithm/graph-traversals.html" class="sidebar-link">Graph Traversals</a></li><li><a href="/algorithm/dijkstras-algorithm.html" class="sidebar-link">Dijkstra’s Algorithm</a></li><li><a href="/algorithm/a-pathfinding.html" class="sidebar-link">A* Pathfinding</a></li><li><a href="/algorithm/a-pathfinding-algorithm.html" class="sidebar-link">A* Pathfinding Algorithm</a></li><li><a href="/algorithm/dynamic-programming.html" class="sidebar-link">Dynamic Programming</a></li><li><a href="/algorithm/applications-of-dynamic-programming.html" class="sidebar-link">Applications of Dynamic Programming</a></li><li><a href="/algorithm/kruskal-s-algorithm.html" class="sidebar-link">Kruskal's Algorithm</a></li><li><a href="/algorithm/greedy-algorithms.html" class="sidebar-link">Greedy Algorithms</a></li><li><a href="/algorithm/applications-of-greedy-technique.html" class="sidebar-link">Applications of Greedy technique</a></li><li><a href="/algorithm/prim-s-algorithm.html" class="sidebar-link">Prim's Algorithm</a></li><li><a href="/algorithm/bellman-ford-algorithm.html" class="sidebar-link">Bellman–Ford Algorithm</a></li><li><a href="/algorithm/line-algorithm.html" class="sidebar-link">Line Algorithm</a></li><li><a href="/algorithm/floyd-warshall-algorithm.html" class="sidebar-link">Floyd-Warshall Algorithm</a></li><li><a href="/algorithm/catalan-number-algorithm.html" class="sidebar-link">Catalan Number Algorithm</a></li><li><a href="/algorithm/multithreaded-algorithms.html" class="sidebar-link">Multithreaded Algorithms</a></li><li><a href="/algorithm/knuth-morris-pratt-kmp-algorithm.html" class="sidebar-link">Knuth Morris Pratt (KMP) Algorithm</a></li><li><a href="/algorithm/edit-distance-dynamic-algorithm.html" class="sidebar-link">Edit Distance Dynamic Algorithm</a></li><li><a href="/algorithm/online-algorithms.html" class="sidebar-link">Online algorithms</a></li><li><a href="/algorithm/integer-partition-algorithm.html" class="sidebar-link">Integer Partition Algorithm</a></li><li><a href="/algorithm/maximum-path-sum-algorithm.html" class="sidebar-link">Maximum Path Sum Algorithm</a></li><li><a href="/algorithm/maximum-subarray-algorithm.html" class="sidebar-link">Maximum Subarray Algorithm</a></li><li><a href="/algorithm/sliding-window-algorithm.html" class="sidebar-link">Sliding Window Algorithm</a></li><li><a href="/algorithm/sorting.html" class="sidebar-link">Sorting</a></li><li><a href="/algorithm/bubble-sort.html" aria-current="page" class="active sidebar-link">Bubble Sort</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/bubble-sort.html#bubble-sort-2" class="sidebar-link">Bubble Sort</a></li><li class="sidebar-sub-header"><a href="/algorithm/bubble-sort.html#implementation-in-c-c" class="sidebar-link">Implementation in C & C++</a></li><li class="sidebar-sub-header"><a href="/algorithm/bubble-sort.html#implementation-in-javascript" class="sidebar-link">Implementation in Javascript</a></li><li class="sidebar-sub-header"><a href="/algorithm/bubble-sort.html#implementation-in-c" class="sidebar-link">Implementation in C#</a></li><li class="sidebar-sub-header"><a href="/algorithm/bubble-sort.html#implementation-in-java" class="sidebar-link">Implementation in Java</a></li><li class="sidebar-sub-header"><a href="/algorithm/bubble-sort.html#python-implementation" class="sidebar-link">Python Implementation</a></li></ul></li><li><a href="/algorithm/merge-sort.html" class="sidebar-link">Merge Sort</a></li><li><a href="/algorithm/insertion-sort.html" class="sidebar-link">Insertion Sort</a></li><li><a href="/algorithm/bucket-sort.html" class="sidebar-link">Bucket Sort</a></li><li><a href="/algorithm/quicksort.html" class="sidebar-link">Quicksort</a></li><li><a href="/algorithm/counting-sort.html" class="sidebar-link">Counting Sort</a></li><li><a href="/algorithm/heap-sort.html" class="sidebar-link">Heap Sort</a></li><li><a href="/algorithm/cycle-sort.html" class="sidebar-link">Cycle Sort</a></li><li><a href="/algorithm/odd-even-sort.html" class="sidebar-link">Odd-Even Sort</a></li><li><a href="/algorithm/selection-sort.html" class="sidebar-link">Selection Sort</a></li><li><a href="/algorithm/pigeonhole-sort.html" class="sidebar-link">Pigeonhole Sort</a></li><li><a href="/algorithm/radix-sort.html" class="sidebar-link">Radix Sort</a></li><li><a href="/algorithm/shell-sort.html" class="sidebar-link">Shell Sort</a></li><li><a href="/algorithm/pancake-sort.html" class="sidebar-link">Pancake Sort</a></li><li><a href="/algorithm/searching.html" class="sidebar-link">Searching</a></li><li><a href="/algorithm/substring-search.html" class="sidebar-link">Substring Search</a></li><li><a href="/algorithm/breadth-first-search.html" class="sidebar-link">Breadth-First Search</a></li><li><a href="/algorithm/depth-first-search.html" class="sidebar-link">Depth First Search</a></li><li><a href="/algorithm/hash-functions.html" class="sidebar-link">Hash Functions</a></li><li><a href="/algorithm/travelling-salesman.html" class="sidebar-link">Travelling Salesman</a></li><li><a href="/algorithm/shortest-common-supersequence-problem.html" class="sidebar-link">Shortest Common Supersequence Problem</a></li><li><a href="/algorithm/knapsack-problem.html" class="sidebar-link">Knapsack Problem</a></li><li><a href="/algorithm/equation-solving.html" class="sidebar-link">Equation Solving</a></li><li><a href="/algorithm/longest-common-subsequence.html" class="sidebar-link">Longest Common Subsequence</a></li><li><a href="/algorithm/longest-increasing-subsequence.html" class="sidebar-link">Longest Increasing Subsequence</a></li><li><a href="/algorithm/check-two-strings-are-anagrams.html" class="sidebar-link">Check two strings are anagrams</a></li><li><a href="/algorithm/pascal-s-triangle.html" class="sidebar-link">Pascal's Triangle</a></li><li><a href="/algorithm/algo-print-a-m-n-matrix-in-square-wise.html" class="sidebar-link">Algo:- Print a m*n matrix in square wise</a></li><li><a href="/algorithm/matrix-exponentiation.html" class="sidebar-link">Matrix Exponentiation</a></li><li><a href="/algorithm/polynomial-time-bounded-algorithm-for-minimum-vertex-cover.html" class="sidebar-link">polynomial-time bounded algorithm for Minimum Vertex Cover</a></li><li><a href="/algorithm/dynamic-time-warping.html" class="sidebar-link">Dynamic Time Warping</a></li><li><a href="/algorithm/fast-fourier-transform.html" class="sidebar-link">Fast Fourier Transform</a></li><li><a href="/algorithm/pseudocode.html" class="sidebar-link">Pseudocode</a></li><li><a href="/algorithm/contributors.html" class="sidebar-link">The Contributors</a></li></ul></section></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><h1 id="bubble-sort"><a href="#bubble-sort" class="header-anchor">#</a> Bubble Sort</h1> <h2 id="bubble-sort-2"><a href="#bubble-sort-2" class="header-anchor">#</a> Bubble Sort</h2> <p>The <code>BubbleSort</code> compares each successive pair of elements in an unordered list and inverts the elements if they are not in order.</p> <p>The following example illustrates the bubble sort on the list <code>{6,5,3,1,8,7,2,4}</code> (pairs that were compared in each step are encapsulated in '**'):</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token punctuation">{</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span>
<span class="token punctuation">{</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">5</span> <span class="token operator"><</span> <span class="token number">6</span> <span class="token operator">-></span> swap
<span class="token punctuation">{</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">3</span> <span class="token operator"><</span> <span class="token number">6</span> <span class="token operator">-></span> swap
<span class="token punctuation">{</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">1</span> <span class="token operator"><</span> <span class="token number">6</span> <span class="token operator">-></span> swap
<span class="token punctuation">{</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">8</span> <span class="token operator">></span> <span class="token number">6</span> <span class="token operator">-></span> no swap
<span class="token punctuation">{</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">7</span> <span class="token operator"><</span> <span class="token number">8</span> <span class="token operator">-></span> swap
<span class="token punctuation">{</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">2</span> <span class="token operator"><</span> <span class="token number">8</span> <span class="token operator">-></span> swap
<span class="token punctuation">{</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token operator">*</span><span class="token operator">*</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token operator">*</span><span class="token operator">*</span><span class="token punctuation">}</span> <span class="token operator">--</span> <span class="token number">4</span> <span class="token operator"><</span> <span class="token number">8</span> <span class="token operator">-></span> swap
</code></pre></div><p>After one iteration through the list, we have <code>{5,3,1,6,7,2,4,8}</code>. Note that the greatest unsorted value in the array (8 in this case) will always reach its final position. Thus, to be sure the list is sorted we must iterate n-1 times for lists of length n.</p> <p>Graphic:</p> <p><a href="http://i.stack.imgur.com/NJPXP.gif" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/NJPXP.gif" alt="BubbleSort"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <h2 id="implementation-in-c-c"><a href="#implementation-in-c-c" class="header-anchor">#</a> Implementation in C & C++</h2> <p>An example implementation of <code>BubbleSort</code> in <code>C++</code>:</p> <div class="language- extra-class"><pre class="language-text"><code>
void bubbleSort(vector<int>numbers)
{
for(int i = numbers.size() - 1; i >= 0; i--) {
for(int j = 1; j <= i; j++) {
if(numbers[j-1] > numbers[j]) {
swap(numbers[j-1],numbers(j));
}
}
}
}
</code></pre></div><p><strong>C Implementation</strong></p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">bubble_sort</span><span class="token punctuation">(</span><span class="token keyword">long</span> list<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token keyword">long</span> n<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">long</span> c<span class="token punctuation">,</span> d<span class="token punctuation">,</span> t<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>c <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> c <span class="token operator"><</span> <span class="token punctuation">(</span> n <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> c<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>d <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> d <span class="token operator"><</span> n <span class="token operator">-</span> c <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> d<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>list<span class="token punctuation">[</span>d<span class="token punctuation">]</span> <span class="token operator">></span> list<span class="token punctuation">[</span>d<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token comment">/* Swapping */</span>
t <span class="token operator">=</span> list<span class="token punctuation">[</span>d<span class="token punctuation">]</span><span class="token punctuation">;</span>
list<span class="token punctuation">[</span>d<span class="token punctuation">]</span> <span class="token operator">=</span> list<span class="token punctuation">[</span>d<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
list<span class="token punctuation">[</span>d<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> t<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><p><strong>Bubble Sort with pointer</strong></p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">void</span> <span class="token function">pointer_bubble_sort</span><span class="token punctuation">(</span><span class="token keyword">long</span> <span class="token operator">*</span> list<span class="token punctuation">,</span> <span class="token keyword">long</span> n<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">long</span> c<span class="token punctuation">,</span> d<span class="token punctuation">,</span> t<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>c <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> c <span class="token operator"><</span> <span class="token punctuation">(</span> n <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span> c<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>d <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> d <span class="token operator"><</span> n <span class="token operator">-</span> c <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> d<span class="token operator">++</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span> <span class="token operator">*</span> <span class="token punctuation">(</span>list <span class="token operator">+</span> d <span class="token punctuation">)</span> <span class="token operator">></span> <span class="token operator">*</span><span class="token punctuation">(</span>list<span class="token operator">+</span>d<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token comment">/* Swapping */</span>
t <span class="token operator">=</span> <span class="token operator">*</span> <span class="token punctuation">(</span>list <span class="token operator">+</span> d <span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token operator">*</span> <span class="token punctuation">(</span>list <span class="token operator">+</span> d <span class="token punctuation">)</span> <span class="token operator">=</span> <span class="token operator">*</span> <span class="token punctuation">(</span>list <span class="token operator">+</span> d <span class="token operator">+</span> <span class="token number">1</span> <span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token operator">*</span> <span class="token punctuation">(</span>list <span class="token operator">+</span> d <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">)</span> <span class="token operator">=</span> t<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="implementation-in-javascript"><a href="#implementation-in-javascript" class="header-anchor">#</a> Implementation in Javascript</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code>function <span class="token function">bubbleSort</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
var swapped<span class="token punctuation">;</span>
<span class="token keyword">do</span> <span class="token punctuation">{</span>
swapped <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>var i<span class="token operator">=</span><span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> a<span class="token punctuation">.</span>length<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>a<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span> a<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
var temp <span class="token operator">=</span> a<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
a<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> a<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
a<span class="token punctuation">[</span>i<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
swapped <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span> <span class="token keyword">while</span> <span class="token punctuation">(</span>swapped<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
var a <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">203</span><span class="token punctuation">,</span> <span class="token number">34</span><span class="token punctuation">,</span> <span class="token number">746</span><span class="token punctuation">,</span> <span class="token number">200</span><span class="token punctuation">,</span> <span class="token number">984</span><span class="token punctuation">,</span> <span class="token number">198</span><span class="token punctuation">,</span> <span class="token number">764</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token function">bubbleSort</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>a<span class="token punctuation">)</span><span class="token punctuation">;</span> <span class="token comment">//logs [ 3, 9, 34, 198, 200, 203, 746, 764, 984 ]</span>
</code></pre></div><h2 id="implementation-in-c"><a href="#implementation-in-c" class="header-anchor">#</a> Implementation in C#</h2> <p>Bubble sort is also known as <strong>Sinking Sort</strong>. It is a simple sorting algorithm that repeatedly steps through the list to be sorted, compares each pair of adjacent items and swaps them if they are in the wrong order.</p> <p><strong>Bubble sort example</strong> <a href="http://i.stack.imgur.com/SDHQM.jpg" target="_blank" rel="noopener noreferrer"><img src="http://i.stack.imgur.com/SDHQM.jpg" alt="Bubble sort example"><span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <p><strong>Implementation of Bubble Sort</strong><br>
I used C# language to implement bubble sort algorithm</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">BubbleSort</span>
<span class="token punctuation">{</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">SortBubble</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>var i <span class="token operator">=</span> input<span class="token punctuation">.</span>Length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> i<span class="token operator">--</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>var j <span class="token operator">=</span> input<span class="token punctuation">.</span>Length <span class="token operator">-</span> <span class="token number">1</span> <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> j<span class="token operator">--</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>input<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator"><=</span> input<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token keyword">continue</span><span class="token punctuation">;</span>
var temp <span class="token operator">=</span> input<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
input<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> input<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
input<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token function">Main</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token function">SortBubble</span><span class="token punctuation">(</span>input<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">return</span> input<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="implementation-in-java"><a href="#implementation-in-java" class="header-anchor">#</a> Implementation in Java</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token keyword">public</span> <span class="token keyword">class</span> <span class="token class-name">MyBubbleSort</span> <span class="token punctuation">{</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">bubble_srt</span><span class="token punctuation">(</span><span class="token keyword">int</span> array<span class="token punctuation">[</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span><span class="token comment">//main logic</span>
<span class="token keyword">int</span> n <span class="token operator">=</span> array<span class="token punctuation">.</span>length<span class="token punctuation">;</span>
<span class="token keyword">int</span> k<span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> m <span class="token operator">=</span> n<span class="token punctuation">;</span> m <span class="token operator">>=</span> <span class="token number">0</span><span class="token punctuation">;</span> m<span class="token operator">--</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> n <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
k <span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>array<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">></span> array<span class="token punctuation">[</span>k<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token function">swapNumbers</span><span class="token punctuation">(</span>i<span class="token punctuation">,</span> k<span class="token punctuation">,</span> array<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token function">printNumbers</span><span class="token punctuation">(</span>array<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">swapNumbers</span><span class="token punctuation">(</span><span class="token keyword">int</span> i<span class="token punctuation">,</span> <span class="token keyword">int</span> j<span class="token punctuation">,</span> <span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> array<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">int</span> temp<span class="token punctuation">;</span>
temp <span class="token operator">=</span> array<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
array<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> array<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
array<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">printNumbers</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">int</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> i <span class="token operator"><</span> input<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
System<span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">print</span><span class="token punctuation">(</span>input<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">+</span> <span class="token string">", "</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
System<span class="token punctuation">.</span>out<span class="token punctuation">.</span><span class="token function">println</span><span class="token punctuation">(</span><span class="token string">"\n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">main</span><span class="token punctuation">(</span>String<span class="token punctuation">[</span><span class="token punctuation">]</span> args<span class="token punctuation">)</span> <span class="token punctuation">{</span>
<span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> input <span class="token operator">=</span> <span class="token punctuation">{</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">,</span> <span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">23</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">34</span><span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">}</span><span class="token punctuation">;</span>
<span class="token function">bubble_srt</span><span class="token punctuation">(</span>input<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="python-implementation"><a href="#python-implementation" class="header-anchor">#</a> Python Implementation</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code>#<span class="token operator">!</span><span class="token operator">/</span>usr<span class="token operator">/</span>bin<span class="token operator">/</span>python
input_list <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">10</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">,</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">11</span><span class="token punctuation">]</span>
<span class="token keyword">for</span> i in <span class="token function">range</span><span class="token punctuation">(</span><span class="token function">len</span><span class="token punctuation">(</span>input_list<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">for</span> j in <span class="token function">range</span><span class="token punctuation">(</span>i<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> <span class="token keyword">int</span><span class="token punctuation">(</span>input_list<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token operator">></span> <span class="token keyword">int</span><span class="token punctuation">(</span>input_list<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token operator">:</span>
input_list<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">,</span>input_list<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> input_list<span class="token punctuation">[</span>j<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">,</span>input_list<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
print input_list
</code></pre></div><h4 id="parameters"><a href="#parameters" class="header-anchor">#</a> Parameters</h4> <table><thead><tr><th>Parameter</th> <th>Description</th></tr></thead> <tbody><tr><td>Stable</td> <td>Yes</td></tr> <tr><td>In place</td> <td>Yes</td></tr> <tr><td>Best case complexity</td> <td>O(n)</td></tr> <tr><td>Average case complexity</td> <td>O(n^2)</td></tr> <tr><td>Worst case complexity</td> <td>O(n^2)</td></tr> <tr><td>Space complexity</td> <td>O(1)</td></tr></tbody></table></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/bubble-sort.md" target="_blank" rel="noopener noreferrer">Edit this page on GitHub</a> <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></div> <!----></footer> <div class="page-nav"><p class="inner"><span class="prev">
←
<a href="/algorithm/sorting.html" class="prev">
Sorting
</a></span> <span class="next"><a href="/algorithm/merge-sort.html">
Merge Sort
</a>
→
</span></p></div> </main></div><div class="global-ui"><!----></div></div>
<script src="/assets/js/app.1779e102.js" defer></script><script src="/assets/js/3.2cfa8016.js" defer></script><script src="/assets/js/22.ac8a50ef.js" defer></script>
</body>
</html>