About Me

My photo
#Engineer #Writer #Optimist #Traveler #PumpingIron

Sunday, February 14, 2010

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.
Posted by at No comments:

EratosthenesSieve : A very fast algorithm for finding Prime numbers.


  1. /*
  2. * EratosthenesSieve.java
  3. *
  4. * Copyright 2010 Ankush Bisht
  5. *
  6. * This program is free software; you can redistribute it and/or modify
  7. * it under the terms of the GNU General Public License as published by
  8. * the Free Software Foundation; either version 2 of the License, or
  9. * (at your option) any later version.
  10. *
  11. * This program is distributed in the hope that it will be useful,
  12. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  14. * GNU General Public License for more details.
  15. *
  16. * You should have received a copy of the GNU General Public License
  17. * along with this program; if not, write to the Free Software
  18. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  19. * MA 02110-1301, USA.
  20. */
  22. public class EratosthenesSieve {
  24. public static void main (String args[]) {
  25. System.out.println("Enter the Number till you want to print the Primes");
  26. int a[]=new int[new java.util.Scanner(System.in).nextInt()];
  27. for(int i=0;i<a.length;i++)
  28. a[i]=i+1;
  29. int i,j,k,step;
  30. for(i=1;i<a.length;i++)
  31. {
  32. if(a[i]!=0)
  33. {
  34. k=a[i]*2-1;
  35. step=a[i];
  36. for(j=k;j<a.length;j+=step)
  37. a[j]=0;
  38. }
  39. }
  40. System.out.println("Prime Numbers between 1 and "+a.length+" are: ");
  41. for(i=0;i<a.length;i++)
  42. {
  43. if(a[i]!=0)
  44. System.out.println(a[i]+" ");
  45. }
  46. }
  47. }

Posted by at No comments:
Subscribe to: Posts (Atom)