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.
  3. 1)
  4. 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.
  5. Here is the implementation.
  6. /*
  7. * Main.java
  8. *
  9. * Copyright 2010 Ankush Bisht
  10. *
  11. * This program is free software; you can redistribute it and/or modify
  12. * it under the terms of the GNU General Public License as published by
  13. * the Free Software Foundation; either version 2 of the License, or
  14. * (at your option) any later version.
  15. *
  16. * This program is distributed in the hope that it will be useful,
  17. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  19. * GNU General Public License for more details.
  20. *
  21. * You should have received a copy of the GNU General Public License
  22. * along with this program; if not, write to the Free Software
  23. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  24. * MA 02110-1301, USA.
  25. */
  26. import java.util.Scanner;
  27. public class Main {
  28. public static void main (String args[]) {
  29. Scanner in=new Scanner(System.in);
  30. System.out.println("Enter number of elements in the array");
  31. int n=in.nextInt();
  32. int a[]=new int[n];
  33. int i,j,temp;
  34. System.out.println("Enter "+n+" numbers");
  35. for(i=0;i<n;i++)
  36. {
  37. a[i]=in.nextInt();
  38. }
  39. for(i=0;i<n-1;i++)
  40. {
  41. for(j=i+1;j<n;j++)
  42. {
  43. if(a[i]>a[j])
  44. {
  45. temp=a[i];
  46. a[i]=a[j];
  47. a[j]=temp;
  48. }
  49. }
  50. }
  51. for(i=0;i<n;i++)
  52. {
  53. System.out.print(a[i]+" ");
  54. }
  55. }
  56. }
  57. 2)
  58. 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:
  59. * simple implementation
  60. * efficient for (quite) small data sets
  61. * 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
  62. * 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
  63. * stable, i.e. does not change the relative order of elements with equal keys
  64. * in-place, i.e. only requires a constant amount O(1) of additional memory space
  65. * online, i.e. can sort a list as it receives it.
  66. Most humans when sorting—ordering a deck of cards, for example—use a method that is similar to insertion sort.
  67. Here is the implementation.
  68. /*
  69. * Insertion.java
  70. *
  71. * Copyright 2010 Ankush
  72. *
  73. * This program is free software; you can redistribute it and/or modify
  74. * it under the terms of the GNU General Public License as published by
  75. * the Free Software Foundation; either version 2 of the License, or
  76. * (at your option) any later version.
  77. *
  78. * This program is distributed in the hope that it will be useful,
  79. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  80. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  81. * GNU General Public License for more details.
  82. *
  83. * You should have received a copy of the GNU General Public License
  84. * along with this program; if not, write to the Free Software
  85. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  86. * MA 02110-1301, USA.
  87. */
  88. import java.util.*;
  89. public class Insertion {
  90. public static void main (String args[]) {
  91. Scanner in=new Scanner(System.in);
  92. int i,key,j,n;
  93. System.out.println("Enter number of elements in the array");
  94. n=in.nextInt();
  95. int []a=new int [n];
  96. System.out.println("Enter "+n+" numbers");
  97. for(i=0;i<n;i++)
  98. {
  99. a[i]=in.nextInt();
  100. }
  101. for(i=1;i<n;i++)
  102. {
  103. key=a[i];
  104. for(j=i-1;j>=0&&a[j]>key;)
  105. {
  106. a[j+1]=a[j];
  107. j--;
  108. a[j+1]=key;
  109. }
  110. }
  111. for(i=0;i<n;i++)
  112. {
  113. System.out.print(a[i]+" ");
  114. }
  115. }
  116. }
  117. 3)
  118. 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.
  119. 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.
  120. 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).
  121. Here is its implementation
  122. /*
  123. * Main.java
  124. *
  125. * Copyright 2010 Ankush Bisht
  126. *
  127. * This program is free software; you can redistribute it and/or modify
  128. * it under the terms of the GNU General Public License as published by
  129. * the Free Software Foundation; either version 2 of the License, or
  130. * (at your option) any later version.
  131. *
  132. * This program is distributed in the hope that it will be useful,
  133. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  134. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  135. * GNU General Public License for more details.
  136. *
  137. * You should have received a copy of the GNU General Public License
  138. * along with this program; if not, write to the Free Software
  139. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  140. * MA 02110-1301, USA.
  141. */
  142. import java.util.Scanner;
  143. public class Main {
  144. public static void main (String args[]) {
  145. Scanner in=new Scanner(System.in);
  146. int i,temp,j,n,k;
  147. System.out.println("Enter number of elements in the array");
  148. n=in.nextInt();
  149. int []a=new int [n];
  150. System.out.println("Enter "+n+" numbers");
  151. for(i=0;i<n;i++)
  152. {
  153. a[i]=in.nextInt();
  154. }
  155. for(i=1;i<n;i++)
  156. {
  157. for(j=0;j<n-i;j++)
  158. {
  159. if(a[j]>a[j+1])
  160. {
  161. temp=a[j];
  162. a[j]=a[j+1];
  163. a[j+1]=temp;
  164. }
  165. for(k=0;k<n;k++)
  166. System.out.println(a[k]+" ");
  167. }
  168. }
  169. for(i=0;i<n;i++)
  170. {
  171. System.out.print(a[i]+" ");
  172. }
  173. }
  174. }
  175. 4)
  176. 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.
  177. Quicksort (also known as "partition-exchange sort") is a comparison sort and, in efficient implementations, is not a stable sort.
  178. Here is its implementation
  179. /*
  180. * Main.java
  181. *
  182. * Copyright 2010 Ankush
  183. *
  184. * This program is free software; you can redistribute it and/or modify
  185. * it under the terms of the GNU General Public License as published by
  186. * the Free Software Foundation; either version 2 of the License, or
  187. * (at your option) any later version.
  188. *
  189. * This program is distributed in the hope that it will be useful,
  190. * but WITHOUT ANY WARRANTY; without even the implied warranty of
  191. * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  192. * GNU General Public License for more details.
  193. *
  194. * You should have received a copy of the GNU General Public License
  195. * along with this program; if not, write to the Free Software
  196. * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  197. * MA 02110-1301, USA.
  198. */
  199. import java.util.Scanner;
  200. public class Main {
  201. /*This method partitions the array into two halves*/
  202. public static int partition(int a[],int p,int q)
  203. {
  204. int temp;
  205. int i=p;
  206. for(int j=p+1;j<q;j++)
  207. {
  208. if(a[j]<=a[p]) /*a[p] is pivot. Here we are taking first element of the array as pivot*/
  209. {
  210. i=i+1;
  211. temp=a[i]; /*shift elements to left those are less than the pivot and to right those are greater than the pivot*/
  212. a[i]=a[j];
  213. a[j]=temp;
  214. }
  215. }
  216. temp=a[p]; /*shift the pivot to the middle of the array*/
  217. a[p]=a[i];
  218. a[i]=temp;
  219. return i;
  220. }
  221. public static void quickSort(int a[],int p,int q)
  222. {
  223. if(p<q) /*If p=q then there is only one element or no element so the array is already sorted*/
  224. {
  225. int r=partition(a,p,q);
  226. quickSort(a,p,r); /*recursive call to first half*/
  227. quickSort(a,r+1,q); /*recursive call to second half*/
  228. }
  229. }
  230. public static void main (String args[])
  231. {
  232. Scanner in=new Scanner(System.in);
  233. System.out.println("Enter number of elements in the array");
  234. int n=in.nextInt();
  235. int a[]=new int[n];
  236. int i;
  237. System.out.println("Enter "+n+" numbers");
  238. for(i=0;i<n;i++)
  239. {
  240. a[i]=in.nextInt();
  241. }
  242. System.out.println("Array before sorting");
  243. for(i=0;i<n;i++)
  244. {
  245. System.out.print(a[i]+" ");
  246. }
  247. quickSort(a,0,n); /*Initial call to method quickSort*/
  248. System.out.println();
  249. System.out.println("Array after sorting");
  250. for(i=0;i<n;i++)
  251. {
  252. System.out.print(a[i]+" ");
  253. }
  254. }
  255. }
  256. 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.

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. */
  21. public class EratosthenesSieve {
  22. public static void main (String args[]) {
  23. System.out.println("Enter the Number till you want to print the Primes");
  24. int a[]=new int[new java.util.Scanner(System.in).nextInt()];
  25. for(int i=0;i<a.length;i++)
  26. a[i]=i+1;
  27. int i,j,k,step;
  28. for(i=1;i<a.length;i++)
  29. {
  30. if(a[i]!=0)
  31. {
  32. k=a[i]*2-1;
  33. step=a[i];
  34. for(j=k;j<a.length;j+=step)
  35. a[j]=0;
  36. }
  37. }
  38. System.out.println("Prime Numbers between 1 and "+a.length+" are: ");
  39. for(i=0;i<a.length;i++)
  40. {
  41. if(a[i]!=0)
  42. System.out.println(a[i]+" ");
  43. }
  44. }
  45. }