Advertisement
Guest User

Untitled

a guest
Jun 25th, 2017
85
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.78 KB | None | 0 0
  1. Bubble Sort O(N2) O(N2) O(N2)
  2. void bubbleSort( Comparable[] stuff ){
  3. for(int i=0; i<stuff.length-1; i++){ //two for loops
  4. for(int j=0; j<stuff.length-1; j++){
  5. if(stuff[ j].compareTo(stuff[ j+1]) > 0 ){
  6. Comparable temp = stuff[ j]; //lots of swaps
  7. stuff[ j] = stuff [ j+1];
  8. stuff [ j+1] = temp;
  9. }
  10. }
  11. }
  12. }
  13.  
  14.  
  15. Selection Sort O(N2) O(N2) O(N2)
  16. void selectionSort( int[] ray ){
  17. for(int i=0; i< ray.length-1; i++){
  18. int min = i;
  19. for(int j = i+1; j< ray.length; j++)
  20. {
  21. if(ray[j] < ray[min])
  22. min = j; //find location of smallest
  23. }
  24. if( min != i) {
  25. int temp = ray[min];
  26. ray[min] = ray[i];
  27. ray[i] = temp; //put smallest in pos i
  28. }
  29. }
  30. }
  31.  
  32. Selection Sort with Objects
  33. public void selSort(Comparable[] stuff){
  34. for(int i=0;i<stuff.length-1;i++)
  35. {
  36. int spot=i;
  37. for(int j=i;j<stuff.length;j++){
  38. if(stuff[j].compareTo(stuff[spot])>0)
  39. spot=j;
  40. }
  41. if(spot==i) continue;
  42. Comparable save=stuff[i];
  43. stuff[i]=stuff[spot];
  44. stuff[spot]=save;
  45. }
  46. }
  47.  
  48.  
  49. Insertion Sort O(N) (@) O(N2) O(N2)
  50. void insertionSort( int[] stuff)
  51. {
  52. for (int i=1; i< stuff.length; ++i)
  53. {
  54. int val = stuff[i];
  55. int j=i;
  56. while(j>0&&val<stuff[j-1]){
  57. stuff[j]=stuff[j-1];
  58. j--;
  59. }
  60. stuff[j]=val;
  61. }
  62. }
  63.  
  64. Insertion Sort with Objects
  65. void insertionSort( Comparable[] stuff){
  66. for (int i=1; i< stuff.length; ++i){
  67. int bot=0, top=i-1;
  68. while (bot<=top){
  69. int mid=(bot+top)/2;
  70. if (stuff[mid].compareTo(stuff[ i ])<0)
  71. bot=mid+1;
  72. else top=mid-1;
  73. }
  74. Comparable temp= stuff[i];
  75. for (int j=i; j>bot; --j)
  76. stuff[ j]= stuff[ j-1];
  77. stuff[bot]=temp;
  78. }
  79. }
  80.  
  81. Quick Sort O(N log2 N ) O(N log2 N ) O(N2) (@)
  82. void quickSort(Comparable[] stuff, int low, int high)
  83. {
  84. if (low < high)
  85. {
  86. int spot = partition(stuff, low, high);
  87. quickSort(stuff, low, spot); // has 2 recursion method calls
  88. quickSort(stuff, spot+1, high);
  89. }
  90. }
  91.  
  92. int partition(Comparable[] stuff, int low, int high)
  93. {
  94. Comparable pivot = stuff[low];
  95. int bot = low-1;
  96. int top = high+1;
  97. while(bot<top) {
  98. while (stuff[--top].compareTo(pivot) > 0);
  99. while (stuff[++bot].compareTo(pivot) < 0);
  100. if(bot >= top)
  101. return top;
  102. Comparable temp = stuff[bot];
  103. stuff[bot] = stuff[top];
  104. stuff[top] = temp;
  105. }
  106. }
  107.  
  108.  
  109. Merge Sort O(N log2 N ) O(N log2 N ) O(N log2 N )
  110. void mergeSort(Comparable[] stuff, int front, int back)
  111. {
  112. int mid = (front+back)/2;
  113. if(mid==front) return;
  114. mergeSort(stuff, front, mid); // has 3 recursive methods
  115. mergeSort(stuff, mid, back);
  116. merge(stuff, front, back);
  117. }
  118.  
  119. void merge(Comparable[] stuff, int front, int back)
  120. {
  121. Comparable[] temp = new Comparable[back-front];
  122. int i = front, j = (front+back)/2, k =0, mid =j;
  123. while( i<mid && j<back) {
  124. if(stuff[i].compareTo(stuff[j])<0)
  125. temp[k++]= stuff[i++];
  126. else
  127. temp[k++]= stuff[j++];
  128. }
  129. while(i<mid)
  130. temp[k++]= stuff[i++];
  131. while(j<back)
  132. temp[k++]= stuff[j++];
  133. for(i = 0; i<back-front; ++i)
  134. stuff[front+i]=temp[i];
  135. }
  136.  
  137.  
  138.  
  139.  
  140. Binary Search O(1) O( log2 N ) O( log2 N )
  141. int binarySearch (int [] stuff, int val )
  142. {
  143. int bot= 0, top = stuff.length-1;
  144. while(bot<=top)
  145. {
  146. int middle = (bot + top) / 2;
  147. if (stuff[middle] == val) return middle;
  148. else
  149. if (stuff[middle] > val)
  150. top = middle-1;
  151. else
  152. bot = middle+1;
  153. }
  154. return -1;
  155. }
  156.  
  157.  
  158.  
  159. Linear/Sequential Search O(1) O(N) O(N)
  160.  
  161. Binary Search O(1) O( log2 N ) O( log2 N )
  162.  
  163.  
  164. Selection Sort O(N2) O(N2) O(N2)
  165. Bubble Sort O(N2) O(N2) O(N2)
  166. Insertion Sort O(N) (@) O(N2) O(N2)
  167.  
  168.  
  169. Merge Sort O(N log2 N ) O(N log2 N ) O(N log2 N )
  170. QuickSort O(N log2 N ) O(N log2 N ) O(N2) (@)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement