-
Notifications
You must be signed in to change notification settings - Fork 13
Expand file tree
/
Copy pathquicksort.html
More file actions
194 lines (176 loc) · 42.2 KB
/
quicksort.html
File metadata and controls
194 lines (176 loc) · 42.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
<!DOCTYPE html>
<html lang="en-US">
<head>
<meta charset="utf-8">
<meta name="viewport" content="width=device-width,initial-scale=1">
<title>Algorithm - Quicksort</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="Quicksort Basics, Quicksort in Python, Lomuto partition java implementation, Haskell Implementation, C# Implementation">
<meta property="og:site_name" content="DevTut">
<meta property="og:title" content="Algorithm - Quicksort">
<meta property="og:description" content="Quicksort Basics, Quicksort in Python, Lomuto partition java implementation, Haskell Implementation, C# Implementation">
<meta property="og:type" content="article">
<meta property="og:url" content="/algorithm/quicksort.html">
<meta property="og:image" content="/logo.png">
<meta name="twitter:title" content="Algorithm - Quicksort">
<meta name="twitter:description" content="Quicksort Basics, Quicksort in Python, Lomuto partition java implementation, Haskell Implementation, C# Implementation">
<meta name="twitter:url" content="/algorithm/quicksort.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/66.9d52ad71.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" class="sidebar-link">Bubble Sort</a></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" aria-current="page" class="active sidebar-link">Quicksort</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/algorithm/quicksort.html#quicksort-basics" class="sidebar-link">Quicksort Basics</a></li><li class="sidebar-sub-header"><a href="/algorithm/quicksort.html#quicksort-in-python" class="sidebar-link">Quicksort in Python</a></li><li class="sidebar-sub-header"><a href="/algorithm/quicksort.html#lomuto-partition-java-implementation" class="sidebar-link">Lomuto partition java implementation</a></li><li class="sidebar-sub-header"><a href="/algorithm/quicksort.html#haskell-implementation" class="sidebar-link">Haskell Implementation</a></li><li class="sidebar-sub-header"><a href="/algorithm/quicksort.html#c-implementation" class="sidebar-link">C# Implementation</a></li></ul></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="quicksort"><a href="#quicksort" class="header-anchor">#</a> Quicksort</h1> <h2 id="quicksort-basics"><a href="#quicksort-basics" class="header-anchor">#</a> Quicksort Basics</h2> <p><a href="https://en.wikipedia.org/wiki/Quicksort" target="_blank" rel="noopener noreferrer"><strong>Quicksort</strong><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> is a sorting algorithm that picks an element ("the pivot") and reorders the array forming two partitions such that all elements less than the pivot come before it and all elements greater come after. The algorithm is then applied recursively to the partitions until the list is sorted.</p> <p><strong>1. Lomuto partition scheme mechanism :<br></strong></p> <p>This scheme chooses a pivot which is typically the last element in the array. The algorithm maintains the index to put the pivot in variable i and each time it finds an element less than or equal to pivot, this index is incremented and that element would be placed before the pivot.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">partition</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">)</span> is
pivot <span class="token operator">:</span><span class="token operator">=</span> A<span class="token punctuation">[</span>high<span class="token punctuation">]</span>
i <span class="token operator">:</span><span class="token operator">=</span> low
<span class="token keyword">for</span> j <span class="token operator">:</span><span class="token operator">=</span> low to high – <span class="token number">1</span> <span class="token keyword">do</span>
<span class="token keyword">if</span> A<span class="token punctuation">[</span>j<span class="token punctuation">]</span> ≤ pivot then
swap A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> with A<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
i <span class="token operator">:</span><span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span>
swap A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> with A<span class="token punctuation">[</span>high<span class="token punctuation">]</span>
<span class="token keyword">return</span> i
</code></pre></div><p>Quick Sort mechanism :</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">quicksort</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">)</span> is
<span class="token keyword">if</span> low <span class="token operator"><</span> high then
p <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">partition</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">)</span>
<span class="token function">quicksort</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> low<span class="token punctuation">,</span> p – <span class="token number">1</span><span class="token punctuation">)</span>
<span class="token function">quicksort</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> p <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> high<span class="token punctuation">)</span>
</code></pre></div><p><strong>Example of quick sort:</strong> <a href="https://i.stack.imgur.com/UWJZY.gif" target="_blank" rel="noopener noreferrer"><img src="https://i.stack.imgur.com/UWJZY.gif" alt="Example of Quick Sort"><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>2. Hoare partition scheme: <br></strong></p> <p>It uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater or equal than the pivot, one lesser or equal, that are in the wrong order relative to each other. The inverted elements are then swapped. When the indices meet, the algorithm stops and returns the final index.
Hoare's scheme is more efficient than Lomuto's partition scheme because it does three times fewer swaps on average, and it creates efficient partitions even when all values are equal.</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">quicksort</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> lo<span class="token punctuation">,</span> hi<span class="token punctuation">)</span> is
<span class="token keyword">if</span> lo <span class="token operator"><</span> hi then
p <span class="token operator">:</span><span class="token operator">=</span> <span class="token function">partition</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> lo<span class="token punctuation">,</span> hi<span class="token punctuation">)</span>
<span class="token function">quicksort</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> lo<span class="token punctuation">,</span> p<span class="token punctuation">)</span>
<span class="token function">quicksort</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> p <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">,</span> hi<span class="token punctuation">)</span>
</code></pre></div><p>Partition :</p> <div class="language-cpp extra-class"><pre class="language-cpp"><code><span class="token function">partition</span><span class="token punctuation">(</span>A<span class="token punctuation">,</span> lo<span class="token punctuation">,</span> hi<span class="token punctuation">)</span> is
pivot <span class="token operator">:</span><span class="token operator">=</span> A<span class="token punctuation">[</span>lo<span class="token punctuation">]</span>
i <span class="token operator">:</span><span class="token operator">=</span> lo <span class="token operator">-</span> <span class="token number">1</span>
j <span class="token operator">:</span><span class="token operator">=</span> hi <span class="token operator">+</span> <span class="token number">1</span>
loop forever
<span class="token keyword">do</span><span class="token operator">:</span>
i <span class="token operator">:</span><span class="token operator">=</span> i <span class="token operator">+</span> <span class="token number">1</span>
<span class="token keyword">while</span> A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator"><</span> pivot <span class="token keyword">do</span>
<span class="token keyword">do</span><span class="token operator">:</span>
j <span class="token operator">:</span><span class="token operator">=</span> j <span class="token operator">-</span> <span class="token number">1</span>
<span class="token keyword">while</span> A<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">></span> pivot <span class="token keyword">do</span>
<span class="token keyword">if</span> i <span class="token operator">>=</span> j then
<span class="token keyword">return</span> j
swap A<span class="token punctuation">[</span>i<span class="token punctuation">]</span> with A<span class="token punctuation">[</span>j<span class="token punctuation">]</span>
</code></pre></div><h2 id="quicksort-in-python"><a href="#quicksort-in-python" class="header-anchor">#</a> Quicksort in Python</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code>def <span class="token function">quicksort</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span><span class="token operator">:</span>
<span class="token keyword">if</span> <span class="token function">len</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span> <span class="token operator"><=</span> <span class="token number">1</span><span class="token operator">:</span>
<span class="token keyword">return</span> arr
pivot <span class="token operator">=</span> arr<span class="token punctuation">[</span><span class="token function">len</span><span class="token punctuation">(</span>arr<span class="token punctuation">)</span> <span class="token operator">/</span> <span class="token number">2</span><span class="token punctuation">]</span>
left <span class="token operator">=</span> <span class="token punctuation">[</span>x <span class="token keyword">for</span> x in arr <span class="token keyword">if</span> x <span class="token operator"><</span> pivot<span class="token punctuation">]</span>
middle <span class="token operator">=</span> <span class="token punctuation">[</span>x <span class="token keyword">for</span> x in arr <span class="token keyword">if</span> x <span class="token operator">==</span> pivot<span class="token punctuation">]</span>
right <span class="token operator">=</span> <span class="token punctuation">[</span>x <span class="token keyword">for</span> x in arr <span class="token keyword">if</span> x <span class="token operator">></span> pivot<span class="token punctuation">]</span>
<span class="token keyword">return</span> <span class="token function">quicksort</span><span class="token punctuation">(</span>left<span class="token punctuation">)</span> <span class="token operator">+</span> middle <span class="token operator">+</span> <span class="token function">quicksort</span><span class="token punctuation">(</span>right<span class="token punctuation">)</span>
print <span class="token function">quicksort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">8</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">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
</code></pre></div><h3 id="prints-1-1-2-3-6-8-10"><a href="#prints-1-1-2-3-6-8-10" class="header-anchor">#</a> Prints "[1, 1, 2, 3, 6, 8, 10]"</h3> <h2 id="lomuto-partition-java-implementation"><a href="#lomuto-partition-java-implementation" class="header-anchor">#</a> Lomuto partition java implementation</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">Solution</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>
Scanner sc <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token function">Scanner</span><span class="token punctuation">(</span>System<span class="token punctuation">.</span>in<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> n <span class="token operator">=</span> sc<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><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> ar <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token keyword">int</span><span class="token punctuation">[</span>n<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 punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span>
ar<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> sc<span class="token punctuation">.</span><span class="token function">nextInt</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">quickSort</span><span class="token punctuation">(</span>ar<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> ar<span class="token punctuation">.</span>length<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 keyword">public</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">quickSort</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> ar<span class="token punctuation">,</span> <span class="token keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span><span class="token punctuation">(</span>low<span class="token operator"><</span>high<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> p <span class="token operator">=</span> <span class="token function">partition</span><span class="token punctuation">(</span>ar<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">quickSort</span><span class="token punctuation">(</span>ar<span class="token punctuation">,</span> <span class="token number">0</span> <span class="token punctuation">,</span> p<span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">quickSort</span><span class="token punctuation">(</span>ar<span class="token punctuation">,</span> p<span class="token operator">+</span><span class="token number">1</span><span class="token punctuation">,</span> high<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 function">partition</span><span class="token punctuation">(</span><span class="token keyword">int</span><span class="token punctuation">[</span><span class="token punctuation">]</span> ar<span class="token punctuation">,</span> <span class="token keyword">int</span> l<span class="token punctuation">,</span> <span class="token keyword">int</span> r<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> pivot <span class="token operator">=</span> ar<span class="token punctuation">[</span>r<span class="token punctuation">]</span><span class="token punctuation">;</span>
<span class="token keyword">int</span> i <span class="token operator">=</span>l<span class="token punctuation">;</span>
<span class="token keyword">for</span><span class="token punctuation">(</span><span class="token keyword">int</span> j<span class="token operator">=</span>l<span class="token punctuation">;</span> j<span class="token operator"><</span>r<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>ar<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator"><=</span> pivot<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">int</span> t <span class="token operator">=</span> ar<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
ar<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> ar<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
ar<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> t<span class="token punctuation">;</span>
i<span class="token operator">++</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
<span class="token keyword">int</span> t <span class="token operator">=</span> ar<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
ar<span class="token punctuation">[</span>i<span class="token punctuation">]</span> <span class="token operator">=</span> ar<span class="token punctuation">[</span>r<span class="token punctuation">]</span><span class="token punctuation">;</span>
ar<span class="token punctuation">[</span>r<span class="token punctuation">]</span> <span class="token operator">=</span> t<span class="token punctuation">;</span>
<span class="token keyword">return</span> i<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
</code></pre></div><h2 id="haskell-implementation"><a href="#haskell-implementation" class="header-anchor">#</a> Haskell Implementation</h2> <div class="language-cpp extra-class"><pre class="language-cpp"><code>quickSort <span class="token double-colon punctuation">::</span> Ord a <span class="token operator">=</span><span class="token operator">></span> <span class="token punctuation">[</span>a<span class="token punctuation">]</span> <span class="token operator">-></span> <span class="token punctuation">[</span>a<span class="token punctuation">]</span>
quickSort <span class="token punctuation">[</span><span class="token punctuation">]</span> <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">]</span>
<span class="token function">quickSort</span> <span class="token punctuation">(</span>x<span class="token operator">:</span>xs<span class="token punctuation">)</span> <span class="token operator">=</span> quickSort <span class="token punctuation">[</span> y <span class="token operator">|</span> y <span class="token operator"><</span><span class="token operator">-</span> xs<span class="token punctuation">,</span> y <span class="token operator"><=</span> x <span class="token punctuation">]</span>
<span class="token operator">++</span> <span class="token punctuation">[</span>x<span class="token punctuation">]</span>
<span class="token operator">++</span> quickSort <span class="token punctuation">[</span> z <span class="token operator">|</span> z <span class="token operator"><</span><span class="token operator">-</span> xs<span class="token punctuation">,</span> z <span class="token operator">></span> x <span class="token punctuation">]</span>
</code></pre></div><h2 id="c-implementation"><a href="#c-implementation" class="header-anchor">#</a> C# Implementation</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">QuickSort</span>
<span class="token punctuation">{</span>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">int</span> <span class="token function">Partition</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 keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
var pivot <span class="token operator">=</span> input<span class="token punctuation">[</span>high<span class="token punctuation">]</span><span class="token punctuation">;</span>
var i <span class="token operator">=</span> low <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">for</span> <span class="token punctuation">(</span>var j <span class="token operator">=</span> low<span class="token punctuation">;</span> j <span class="token operator"><=</span> high <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 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> pivot<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
i<span class="token operator">++</span><span class="token punctuation">;</span>
var temp <span class="token operator">=</span> input<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">;</span>
input<span class="token punctuation">[</span>i<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>
var tmp <span class="token operator">=</span> input<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>
input<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> input<span class="token punctuation">[</span>high<span class="token punctuation">]</span><span class="token punctuation">;</span>
input<span class="token punctuation">[</span>high<span class="token punctuation">]</span> <span class="token operator">=</span> tmp<span class="token punctuation">;</span>
<span class="token keyword">return</span> <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>
<span class="token keyword">private</span> <span class="token keyword">static</span> <span class="token keyword">void</span> <span class="token function">SortQuick</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 keyword">int</span> low<span class="token punctuation">,</span> <span class="token keyword">int</span> high<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">while</span> <span class="token punctuation">(</span><span class="token boolean">true</span><span class="token punctuation">)</span>
<span class="token punctuation">{</span>
<span class="token keyword">if</span> <span class="token punctuation">(</span>low <span class="token operator"><</span> high<span class="token punctuation">)</span>
<span class="token punctuation">{</span>
var pi <span class="token operator">=</span> <span class="token function">Partition</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> low<span class="token punctuation">,</span> high<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">SortQuick</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> low<span class="token punctuation">,</span> pi <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
low <span class="token operator">=</span> pi <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">;</span>
<span class="token keyword">continue</span><span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token keyword">break</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">SortQuick</span><span class="token punctuation">(</span>input<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> input<span class="token punctuation">.</span>Length <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">return</span> input<span class="token punctuation">;</span>
<span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre></div><h4 id="remarks"><a href="#remarks" class="header-anchor">#</a> Remarks</h4> <p>Sometimes Quicksort is also known as Partition-Exchange sort.<br> <strong>Auxiliary Space:</strong> <code>O(n)</code><br> <strong>Time complexity:</strong> worst <code>O(n²)</code>, best<code>O(nlogn)</code></p></div> <footer class="page-edit"><div class="edit-link"><a href="https://github.com/devtut/generate/edit/master/docs/algorithm/quicksort.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/bucket-sort.html" class="prev">
Bucket Sort
</a></span> <span class="next"><a href="/algorithm/counting-sort.html">
Counting 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/66.9d52ad71.js" defer></script>
</body>
</html>