-
Notifications
You must be signed in to change notification settings - Fork 28
/
insertionsort.html
214 lines (169 loc) · 15.5 KB
/
insertionsort.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
<!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>Insertion 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" />
<script src="https://use.fontawesome.com/7ade57373d.js"></script>
<link rel="stylesheet" href="src/home/css/morebutton.css" />
<link rel="stylesheet" href="src\seive_Of_Eratosthenes\style.css" />
<!-- 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>Insertion Sort</h1>
<p>This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort.
<br> The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array). This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2), where n is the number of items.</p>
<br>
<div class="box1">
<div class="Process">
<h1>How Insertion Sort Works?</h1>
<p>We take an unsorted array for our example. </p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/unsorted_array.jpg">
<br>
<p>Insertion sort compares the first two elements.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_1.jpg" alt="">
<br>
<p>It finds that both 14 and 33 are already in ascending order. For now, 14 is in sorted sub-list.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_2.jpg" alt="">
<br>
<p>Insertion sort moves ahead and compares 33 with 27. </p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_3.jpg" alt="">
<br>
<p>And finds that 33 is not in the correct position. </p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_4.jpg" alt="">
<br>
<p>It swaps 33 with 27. It also checks with all the elements of sorted sub-list. Here we see that the sorted sub-list has only one element 14, and 27 is greater than 14. Hence, the sorted sub-list remains sorted after swapping.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_5.jpg" alt="">
<br>
<p>By now we have 14 and 27 in the sorted sub-list. Next, it compares 33 with 10.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_6.jpg" alt="">
<br>
<p>These values are not in a sorted order.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_7.jpg" alt="">
<br>
<p>So we swap them.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_8.jpg" alt="">
<br>
<p>However, swapping makes 27 and 10 unsorted.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_9.jpg" alt="">
<br>
<p>Hence, we swap them too </p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_10.jpg" alt="">
<br>
<p>Again we find 14 and 10 in an unsorted order.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_11.jpg" alt="">
<br>
<p>We swap them again. By the end of third iteration, we have a sorted sub-list of 4 items.</p>
<img src="https://www.tutorialspoint.com/data_structures_algorithms/images/insertion_sort_12.jpg" alt="">
<br>
<p>This process goes on until all the unsorted values are covered in a sorted sub-list. Now we shall see some programming aspects of insertion sort.</p>
<br>
</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"> insertionSort</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"> valueToInsert</span><span class="pun">;</span><span class="pln">
</span><span class="kwd">int</span><span class="pln"> holePosition</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="com">// loop through all numbers </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">1</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">
</span><span class="com">// select a value to be inserted. </span><span class="pln">
valueToInsert </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="com">// select the hole position where number is to be inserted </span><span class="pln">
holePosition </span><span class="pun">=</span><span class="pln"> i</span><span class="pun">;</span><span class="pln">
</span><span class="com">// check if previous no. is larger than value to be inserted </span><span class="pln">
</span><span class="kwd">while</span><span class="pln"> </span><span class="pun">(</span><span class="pln">holePosition </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">holePosition</span><span class="pun">-</span><span class="lit">1</span><span class="pun">]</span><span class="pln"> </span><span class="pun">></span><span class="pln"> valueToInsert</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">holePosition</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">holePosition</span><span class="pun">-</span><span class="lit">1</span><span class="pun">];</span><span class="pln">
holePosition</span><span class="pun">--;</span><span class="pln">
printf</span><span class="pun">(</span><span class="str">" item moved : %d\n"</span><span class="pln"> </span><span class="pun">,</span><span class="pln"> intArray</span><span class="pun">[</span><span class="pln">holePosition</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">holePosition </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">" item inserted : %d, at position : %d\n"</span><span class="pln"> </span><span class="pun">,</span><span class="pln"> valueToInsert</span><span class="pun">,</span><span class="pln">holePosition</span><span class="pun">);</span><span class="pln">
</span><span class="com">// insert the number at hole position </span><span class="pln">
intArray</span><span class="pun">[</span><span class="pln">holePosition</span><span class="pun">]</span><span class="pln"> </span><span class="pun">=</span><span class="pln"> valueToInsert</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">"Iteration %d#:"</span><span class="pun">,</span><span class="pln">i</span><span class="pun">);</span><span class="pln">
display</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">void</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">
insertionSort</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>
</div>
<script src="src/home/js/morebutton.js"></script>
<script src="src/home/js/script.js"></script>
</body>
</html>