-
Notifications
You must be signed in to change notification settings - Fork 28
/
quickSort.html
227 lines (184 loc) · 19 KB
/
quickSort.html
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
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<!-- <title>Document</title> -->
<title>Merge Sort</title>
<link
rel="stylesheet"
href="https://stackpath.bootstrapcdn.com/bootstrap/4.5.2/css/bootstrap.min.css"
integrity="sha384-JcKb8q3iqJ61gNV9KGb8thSsNjpSL0n8PARn9HuZOnIxN0hoP+VmmDGMN5t9UJ0Z"
crossorigin="anonymous"
/>
<link
href="https://maxcdn.bootstrapcdn.com/font-awesome/4.7.0/css/font-awesome.min.css"
rel="stylesheet"
/>
<link rel="stylesheet" href="src/home/css/style.css" />
<link rel="stylesheet" href="src/home/css/morebutton.css" />
<link rel="stylesheet" href="src\seive_Of_Eratosthenes\style.css" />
<script src="https://use.fontawesome.com/7ade57373d.js"></script>
<!-- Page icon -->
<link rel="icon" href="./src/assets/logo.png">
<link rel="stylesheet" href="https://cdnjs.cloudflare.com/ajax/libs/font-awesome/5.15.3/css/all.min.css">
</head>
<body>
<header>
<div id="header-inner">
<a href="#" id="logo"></a>
<a class="navbar-brand1" rel="home" href="#" title="Structurex">
<img src="src/assets/nlogo.png" class="main-logo">
<href="#" class="name">Structurex</a>
<div class="container1 blue" id="navbarNav">
<!-- ------HAMBURGER MENU -------->
<!-- -----------NEW CHANGES----------- -->
<i class="fas fa-2x fa-bars" style="color:white;display: none;" onclick="display();"></i>
<ul class="heck" id="heck">
<a href="index.html" class="link">Home</a>
<a href="sort.html" class="link">Sorting</a>
<a href="search.html" class="link">Searching</a>
<a href="./Path Finding/index.html" class="link">Path Finding</a>
<a href="tree.html" class="link" class="link">Graph</a>
<div class="dropdown">
<button onclick="show_hide()" class="Morebutton" > MORE</button>
<center>
<div id="list-items">
<!-- Add more list items here if required -->
<a href="seiveErato.html" >Sieve Of Eratosthenes</a>
</div>
</center>
</div>
</ul>
</div>
</div>
</header>
<div class="algo">
<br>
<br>
<h1>Quick Sort</h1>
<p>Quick sort is a highly efficient sorting algorithm and is based on partitioning of array of data into smaller arrays. A large array is partitioned into two arrays one of which holds values smaller than the specified value, say pivot, based on which the partition is made and another array holds values greater than the pivot value.
<br>
Quicksort partitions an array and then calls itself recursively twice to sort the two resulting subarrays. This algorithm is quite efficient for large-sized data sets as its average and worst-case complexity are O(n2), respectively.</p>
<br>
<br>
<div class="box1">
<div class="Process">
<h1>Partition in Quick Sort</h1>
<p>Following animated representation explains how to find the pivot value in an array.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif" alt="Quick Sort Partition Animation">
<p>The pivot value divides the list into two parts. And recursively, we find the pivot for each sub-lists until all lists contains only one element.</p>
<div class ="algorithm">
<h3>Quick Sort Pivot Algorithm</h3>
<p>Based on our understanding of partitioning in quick sort, we will now try to write an algorithm for it, which is as follows.</p>
<p>
<b>Step 1 −</b> Choose the highest index value has pivot <br>
<b>Step 2 −</b> Take two variables to point left and right of the list excluding pivot <br>
<b>Step 3 −</b> left points to the low index <br>
<b>Step 4 − </b>right points to the high <br>
<b>Step 5 − </b>while value at left is less than pivot move right <br>
<b>Step 6 −</b> while value at right is greater than pivot move left <br>
<b>Step 7 − </b>if both step 5 and step 6 does not match swap left and right <br>
<b>Step 8 −</b> if left ≥ right, the point where they met is new pivot <br>
</p>
<h3>Quick Sort Algorithm</h3>
<p>Using pivot algorithm recursively, we end up with smaller possible partitions. Each partition is then processed for quick sort. We define recursive algorithm for quicksort as follows −</p>
<b>Step 1 −</b> Make the right-most index value pivot <br>
<b>Step 2 −</b>partition the array using pivot value<br>
<b>Step 3 −</b> partition the array using pivot value <br>
<b>Step 4 − </b>quicksort right partition recursively <br>
</div>
</div>
<div class = "code">
<pre class="prettyprint notranslate prettyprinted" style=""><span class="com">#include</span><span class="pln"> </span><span class="str"><stdio.h></span><span class="pln">
</span><span class="com">#include</span><span class="pln"> </span><span class="str"><stdbool.h></span><span class="pln">
</span><span class="com">#define</span><span class="pln"> MAX </span><span class="lit">7</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">MAX</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> </span><span class="pun">{</span><span class="lit">4</span><span class="pun">,</span><span class="lit">6</span><span class="pun">,</span><span class="lit">3</span><span class="pun">,</span><span class="lit">2</span><span class="pun">,</span><span class="lit">1</span><span class="pun">,</span><span class="lit">9</span><span class="pun">,</span><span class="lit">7</span><span class="pun">};</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> printline</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> count</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> i</span><span class="pun">;</span><span class="pln">
</span><span class="kwd">for</span><span class="pun">(</span><span class="pln">i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln">i </span><span class="pun"><</span><span class="pln"> count</span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln">i</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"="</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"=\n"</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> display</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> i</span><span class="pun">;</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"["</span><span class="pun">);</span><span class="pln">
</span><span class="com">// navigate through all items </span><span class="pln">
</span><span class="kwd">for</span><span class="pun">(</span><span class="pln">i </span><span class="pun">=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">;</span><span class="pln">i </span><span class="pun"><</span><span class="pln"> MAX</span><span class="pun">;</span><span class="pln">i</span><span class="pun">++)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"%d "</span><span class="pun">,</span><span class="pln">intArray</span><span class="pun">[</span><span class="pln">i</span><span class="pun">]);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"]\n"</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> swap</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> num1</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> num2</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> temp </span><span class="pun">=</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">num1</span><span class="pun">];</span><span class="pln">
intArray</span><span class="pun">[</span><span class="pln">num1</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">num2</span><span class="pun">];</span><span class="pln">
intArray</span><span class="pun">[</span><span class="pln">num2</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> temp</span><span class="pun">;</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> partition</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> left</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> right</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> pivot</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> leftPointer </span><span class="pun">=</span><span class="pln"> left </span><span class="pun">-</span><span class="lit">1</span><span class="pun">;</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> rightPointer </span><span class="pun">=</span><span class="pln"> right</span><span class="pun">;</span><span class="pln">
</span><span class="kwd">while</span><span class="pun">(</span><span class="kwd">true</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">while</span><span class="pun">(</span><span class="pln">intArray</span><span class="pun">[++</span><span class="pln">leftPointer</span><span class="pun">]</span><span class="pln"> </span><span class="pun"><</span><span class="pln"> pivot</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="com">//do nothing</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">while</span><span class="pun">(</span><span class="pln">rightPointer </span><span class="pun">></span><span class="pln"> </span><span class="lit">0</span><span class="pln"> </span><span class="pun">&&</span><span class="pln"> intArray</span><span class="pun">[--</span><span class="pln">rightPointer</span><span class="pun">]</span><span class="pln"> </span><span class="pun">></span><span class="pln"> pivot</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="com">//do nothing</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">if</span><span class="pun">(</span><span class="pln">leftPointer </span><span class="pun">>=</span><span class="pln"> rightPointer</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">break</span><span class="pun">;</span><span class="pln">
</span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">" item swapped :%d,%d\n"</span><span class="pun">,</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">leftPointer</span><span class="pun">],</span><span class="pln">intArray</span><span class="pun">[</span><span class="pln">rightPointer</span><span class="pun">]);</span><span class="pln">
swap</span><span class="pun">(</span><span class="pln">leftPointer</span><span class="pun">,</span><span class="pln">rightPointer</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">" pivot swapped :%d,%d\n"</span><span class="pun">,</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">leftPointer</span><span class="pun">],</span><span class="pln">intArray</span><span class="pun">[</span><span class="pln">right</span><span class="pun">]);</span><span class="pln">
swap</span><span class="pun">(</span><span class="pln">leftPointer</span><span class="pun">,</span><span class="pln">right</span><span class="pun">);</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"Updated Array: "</span><span class="pun">);</span><span class="pln">
display</span><span class="pun">();</span><span class="pln">
</span><span class="kwd">return</span><span class="pln"> leftPointer</span><span class="pun">;</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">void</span><span class="pln"> quickSort</span><span class="pun">(</span><span class="kwd">int</span><span class="pln"> left</span><span class="pun">,</span><span class="pln"> </span><span class="kwd">int</span><span class="pln"> right</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">if</span><span class="pun">(</span><span class="pln">right</span><span class="pun">-</span><span class="pln">left </span><span class="pun"><=</span><span class="pln"> </span><span class="lit">0</span><span class="pun">)</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">return</span><span class="pun">;</span><span class="pln">
</span><span class="pun">}</span><span class="pln"> </span><span class="kwd">else</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> pivot </span><span class="pun">=</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">right</span><span class="pun">];</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> partitionPoint </span><span class="pun">=</span><span class="pln"> partition</span><span class="pun">(</span><span class="pln">left</span><span class="pun">,</span><span class="pln"> right</span><span class="pun">,</span><span class="pln"> pivot</span><span class="pun">);</span><span class="pln">
quickSort</span><span class="pun">(</span><span class="pln">left</span><span class="pun">,</span><span class="pln">partitionPoint</span><span class="pun">-</span><span class="lit">1</span><span class="pun">);</span><span class="pln">
quickSort</span><span class="pun">(</span><span class="pln">partitionPoint</span><span class="pun">+</span><span class="lit">1</span><span class="pun">,</span><span class="pln">right</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="pun">}</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> main</span><span class="pun">()</span><span class="pln"> </span><span class="pun">{</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"Input Array: "</span><span class="pun">);</span><span class="pln">
display</span><span class="pun">();</span><span class="pln">
printline</span><span class="pun">(</span><span class="lit">50</span><span class="pun">);</span><span class="pln">
quickSort</span><span class="pun">(</span><span class="lit">0</span><span class="pun">,</span><span class="pln">MAX</span><span class="pun">-</span><span class="lit">1</span><span class="pun">);</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">"Output Array: "</span><span class="pun">);</span><span class="pln">
display</span><span class="pun">();</span><span class="pln">
printline</span><span class="pun">(</span><span class="lit">50</span><span class="pun">);</span><span class="pln">
</span><span class="pun">}</span></pre>
</div>
</div>
<p style=" margin-left: 50%;"> If we compile and run the above program, it will produce the following result −</p>
<h2 style=" margin-left: 50%;">Output</h2>
<div class="output">
<pre class="result notranslate">Input Array: [4 6 3 2 1 9 7 ]
==================================================
pivot swapped :9,7
Updated Array: [4 6 3 2 1 7 9 ]
pivot swapped :4,1
Updated Array: [1 6 3 2 4 7 9 ]
item swapped :6,2
pivot swapped :6,4
Updated Array: [1 2 3 4 6 7 9 ]
pivot swapped :3,3
Updated Array: [1 2 3 4 6 7 9 ]
Output Array: [1 2 3 4 6 7 9 ]
==================================================
</pre>
</div>
</div>
<script src="src/home/js/morebutton.js"></script>
<script src="src/home/js/script.js"></script>
</body>
</html>