Sorting : The most common and interesting area in algorithms

1. Dear Friends,
2. I like the sorting algorithms very much and want to share some simplest implementations of sorting algorithms.
4. 1)
5. Selection sort is a sorting algorithm, specifically an in-place comparison sort. It has O(n2) complexity, making it inefficient on large lists, and generally performs worse than the similar insertion sort. Selection sort is noted for its simplicity, and also has performance advantages over more complicated algorithms in certain situations.
6. Here is the implementation.
8. /*
9. * Main.java
10. *
11. * Copyright 2010 Ankush Bisht
12. *
13. * This program is free software; you can redistribute it and/or modify
14. * it under the terms of the GNU General Public License as published by
15. * the Free Software Foundation; either version 2 of the License, or
16. * (at your option) any later version.
17. *
18. * This program is distributed in the hope that it will be useful,
19. * but WITHOUT ANY WARRANTY; without even the implied warranty of
20. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
21. * GNU General Public License for more details.
22. *
23. * You should have received a copy of the GNU General Public License
24. * along with this program; if not, write to the Free Software
25. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
26. * MA 02110-1301, USA.
27. */
29. import java.util.Scanner;
31. public class Main {
33. public static void main (String args[]) {
34. Scanner in=new Scanner(System.in);
35. System.out.println("Enter number of elements in the array");
36. int n=in.nextInt();
37. int a[]=new int[n];
38. int i,j,temp;
39. System.out.println("Enter "+n+" numbers");
40. for(i=0;i<n;i++)
41. {
42. a[i]=in.nextInt();
43. }
45. for(i=0;i<n-1;i++)
46. {
47. for(j=i+1;j<n;j++)
48. {
49. if(a[i]>a[j])
50. {
51. temp=a[i];
52. a[i]=a[j];
53. a[j]=temp;
54. }
55. }
56. }
58. for(i=0;i<n;i++)
59. {
60. System.out.print(a[i]+" ");
61. }
62. }
63. }
66. 2)
67. Insertion sort is a simple sorting algorithm, a comparison sort in which the sorted array (or list) is built one entry at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, insertion sort provides several advantages:
69. * simple implementation
70. * efficient for (quite) small data sets
71. * adaptive, i.e. efficient for data sets that are already substantially sorted: the time complexity is O(n + d), where d is the number of inversions
72. * more efficient in practice than most other simple quadratic (i.e. O(n2)) algorithms such as selection sort or bubble sort: the average running time is n2/4[citation needed], and the running time is linear in the best case
73. * stable, i.e. does not change the relative order of elements with equal keys
74. * in-place, i.e. only requires a constant amount O(1) of additional memory space
75. * online, i.e. can sort a list as it receives it.
77. Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.
79. Here is the implementation.
81. /*
82. * Insertion.java
83. *
84. * Copyright 2010 Ankush
85. *
86. * This program is free software; you can redistribute it and/or modify
87. * it under the terms of the GNU General Public License as published by
88. * the Free Software Foundation; either version 2 of the License, or
89. * (at your option) any later version.
90. *
91. * This program is distributed in the hope that it will be useful,
92. * but WITHOUT ANY WARRANTY; without even the implied warranty of
93. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
94. * GNU General Public License for more details.
95. *
96. * You should have received a copy of the GNU General Public License
97. * along with this program; if not, write to the Free Software
98. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
99. * MA 02110-1301, USA.
100. */
102. import java.util.*;
103. public class Insertion {
104. public static void main (String args[]) {
105. Scanner in=new Scanner(System.in);
106. int i,key,j,n;
107. System.out.println("Enter number of elements in the array");
108. n=in.nextInt();
109. int []a=new int [n];
110. System.out.println("Enter "+n+" numbers");
111. for(i=0;i<n;i++)
112. {
113. a[i]=in.nextInt();
114. }
116. for(i=1;i<n;i++)
117. {
118. key=a[i];
119. for(j=i-1;j>=0&&a[j]>key;)
120. {
121. a[j+1]=a[j];
122. j--;
123. a[j+1]=key;
124. }
125. }
127. for(i=0;i<n;i++)
128. {
129. System.out.print(a[i]+" ");
130. }
131. }
132. }
135. 3)
136. Bubble sort is a simple sorting algorithm. It works by repeatedly stepping through the list to be sorted, comparing each pair of adjacent items and swapping them if they are in the wrong order. The pass through the list is repeated until no swaps are needed, which indicates that the list is sorted. The algorithm gets its name from the way smaller elements "bubble" to the top of the list. Because it only uses comparisons to operate on elements, it is a comparison sort.
138. Bubble sort has worst-case and average complexity both &#1054;(n²), where n is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of O(n log n). Even other О(n²) sorting algorithms, such as Insertion sort, tend to have better performance than bubble sort. Therefore bubble sort is not a practical sorting algorithm when n is large.
140. However, one significant advantage that bubble sort has over most other implementations, even QuickSort, is that the ability to detect that the list is sorted is efficiently built into the algorithm. Performance of bubble sort over an already-sorted list (best-case) is O(n). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex. However, Insertion sort also has this mechanism, and also performs better on a list that is substantially sorted (having a small number of inversions).
143. Here is its implementation
145. /*
146. * Main.java
147. *
148. * Copyright 2010 Ankush Bisht
149. *
150. * This program is free software; you can redistribute it and/or modify
151. * it under the terms of the GNU General Public License as published by
152. * the Free Software Foundation; either version 2 of the License, or
153. * (at your option) any later version.
154. *
155. * This program is distributed in the hope that it will be useful,
156. * but WITHOUT ANY WARRANTY; without even the implied warranty of
157. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
158. * GNU General Public License for more details.
159. *
160. * You should have received a copy of the GNU General Public License
161. * along with this program; if not, write to the Free Software
162. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
163. * MA 02110-1301, USA.
164. */
165. import java.util.Scanner;
167. public class Main {
169. public static void main (String args[]) {
170. Scanner in=new Scanner(System.in);
171. int i,temp,j,n,k;
172. System.out.println("Enter number of elements in the array");
173. n=in.nextInt();
174. int []a=new int [n];
175. System.out.println("Enter "+n+" numbers");
176. for(i=0;i<n;i++)
177. {
178. a[i]=in.nextInt();
179. }
181. for(i=1;i<n;i++)
182. {
183. for(j=0;j<n-i;j++)
184. {
185. if(a[j]>a[j+1])
186. {
187. temp=a[j];
188. a[j]=a[j+1];
189. a[j+1]=temp;
190. }
191. for(k=0;k<n;k++)
192. System.out.println(a[k]+" ");
193. }
194. }
196. for(i=0;i<n;i++)
197. {
198. System.out.print(a[i]+" ");
199. }
201. }
202. }
204. 4)
206. Quicksort is a well-known sorting algorithm developed by C. A. R. Hoare that, on average, makes &#920;(nlogn) (big O notation) comparisons to sort n items. In the worst case, it makes Θ(n2) comparisons, though if implemented correctly this behavior is rare. Typically, quicksort is significantly faster in practice than other Θ(nlogn) algorithms, because its inner loop can be efficiently implemented on most architectures, and in most real-world data, it is possible to make design choices which minimize the probability of requiring quadratic time. Additionally, QuickSort tends to make excellent usage of the memory hierarchy, taking perfect advantage of virtual memory and available caches. Coupled with the fact that QuickSort is an in-place sort and uses no temporary memory, it is very well suited to modern computer architectures.
208. Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort.
210. Here is its implementation
212. /*
213. * Main.java
214. *
215. * Copyright 2010 Ankush
216. *
217. * This program is free software; you can redistribute it and/or modify
218. * it under the terms of the GNU General Public License as published by
219. * the Free Software Foundation; either version 2 of the License, or
220. * (at your option) any later version.
221. *
222. * This program is distributed in the hope that it will be useful,
223. * but WITHOUT ANY WARRANTY; without even the implied warranty of
224. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
225. * GNU General Public License for more details.
226. *
227. * You should have received a copy of the GNU General Public License
228. * along with this program; if not, write to the Free Software
229. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
230. * MA 02110-1301, USA.
231. */
232. import java.util.Scanner;
234. public class Main {
236. /*This method partitions the array into two halves*/
238. public static int partition(int a[],int p,int q)
239. {
240. int temp;
241. int i=p;
242. for(int j=p+1;j<q;j++)
243. {
244. if(a[j]<=a[p]) /*a[p] is pivot. Here we are taking first element of the array as pivot*/
245. {
246. i=i+1;
247. temp=a[i]; /*shift elements to left those are less than the pivot and to right those are greater than the pivot*/
248. a[i]=a[j];
249. a[j]=temp;
250. }
251. }
252. temp=a[p]; /*shift the pivot to the middle of the array*/
253. a[p]=a[i];
254. a[i]=temp;
255. return i;
256. }
258. public static void quickSort(int a[],int p,int q)
259. {
260. if(p<q) /*If p=q then there is only one element or no element so the array is already sorted*/
261. {
262. int r=partition(a,p,q);
263. quickSort(a,p,r); /*recursive call to first half*/
264. quickSort(a,r+1,q); /*recursive call to second half*/
265. }
266. }
268. public static void main (String args[])
269. {
270. Scanner in=new Scanner(System.in);
271. System.out.println("Enter number of elements in the array");
272. int n=in.nextInt();
273. int a[]=new int[n];
274. int i;
275. System.out.println("Enter "+n+" numbers");
276. for(i=0;i<n;i++)
277. {
278. a[i]=in.nextInt();
279. }
281. System.out.println("Array before sorting");
282. for(i=0;i<n;i++)
283. {
285. System.out.print(a[i]+" ");
286. }
288. quickSort(a,0,n); /*Initial call to method quickSort*/
290. System.out.println();
292. System.out.println("Array after sorting");
294. for(i=0;i<n;i++)
295. {
297. System.out.print(a[i]+" ");
298. }
299. }
300. }
303. There are lot more algorithms to go. I will add them later. Please notify me if there is any error or mistake anywhere in my implementation and also if there is a better implementation of the same.