aznishboy

Sorts

Dec 15th, 2011
187
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 3.98 KB | None | 0 0
  1. http://pastebin.com/0DT6aQJK
  2. import java.util.*;
  3.  
  4. public class Sorts{
  5.     private long steps;
  6.     Sorts(){
  7.         steps = 0;
  8.     }
  9.     public void bubbleSort(int[] list){
  10.         steps++;     // initialization of outer
  11.         for (int outer = 0; outer < list.length - 1; outer++){
  12.             steps += 3;
  13.             //  1 - boundary check of outer loop;
  14.             //  2 - increment, outer++
  15.             //  3 - initialization of inner loop
  16.             for (int inner = 0; inner < list.length - outer - 1; inner++){
  17.                 steps += 3;
  18.                 //  1 - boundary check of inner loop
  19.                 //  2 - increment, inner++
  20.                 //  3 - if comparison
  21.                 if (list[inner] > list[inner+1]){
  22.                     int temp = list[inner];
  23.                     list[inner] = list[inner + 1];
  24.                     list[inner + 1] = temp;
  25.                     steps += 3;    // swap of list[inner] & list[inner + 1]
  26.                 }
  27.             }
  28.         }
  29.         System.out.println();
  30.         System.out.println("Bubble Sort");
  31.         System.out.println();
  32.     }
  33.     public void selectionSort(int[] list){
  34.         steps++;
  35.         int min, temp;
  36.         for (int outer = 0; outer < list.length - 1; outer++){
  37.             min = outer;
  38.             steps += 7;
  39.             for (int inner = outer + 1; inner < list.length; inner++){
  40.                 steps += 3;
  41.                 if (list[inner] < list[min]){
  42.                     steps++;
  43.                     min = inner;
  44.                 }
  45.             }
  46.             //swap list[outer] & list[flag]
  47.             temp = list[outer];
  48.             list[outer] = list[min];
  49.             list[min] = temp;
  50.         }
  51.         System.out.println();
  52.         System.out.println("Selection Sort");
  53.         System.out.println();
  54.     }
  55.     public void insertionSort(int[] list){
  56.         steps++;
  57.         for (int outer = 1; outer < list.length; outer++){
  58.             steps += 5;
  59.             int position = outer;
  60.             int key = list[position];
  61.             // Shift larger values to the right
  62.             while (position > 0 && list[position - 1] > key){
  63.                 steps += 4;
  64.                 list[position] = list[position - 1];
  65.                 position--;
  66.             }
  67.             list[position] = key;
  68.         }
  69.         System.out.println();
  70.         System.out.println("Insertion Sort");
  71.         System.out.println();
  72.     }
  73.     /**
  74.     *  Takes in entire array 'a', but will merge the following subsections
  75.     *  together:  Left sublist from a[first]..a[mid], right sublist from
  76.     *  a[mid+1]..a[last].  Precondition:  each sublist is already in
  77.     *  ascending order
  78.     */
  79.     private void merge(int[] a, int first, int mid, int last){
  80.         steps += 4;
  81.         int[] temp = new int[last - first + 1];
  82.         int i = first;
  83.         int j = mid + 1;
  84.         for(int k = 0; k < temp.length; k++){
  85.             steps += 3;
  86.             if(i > mid){
  87.                 temp[k] = a[j];
  88.                 j++;
  89.                 steps += 2;
  90.             }
  91.             else if(j > last){
  92.                 temp[k] = a[i];
  93.                 i++;
  94.                 steps += 2;
  95.             }
  96.             else {
  97.                 steps++;
  98.                 if(a[i] >= a[j]){
  99.                     temp[k] = a[j];
  100.                     j++;
  101.                     steps += 2;
  102.                 }
  103.                 else{
  104.                     temp[k] = a[i];
  105.                     i++;
  106.                     steps += 2;
  107.                 }
  108.             }
  109.         }
  110.         steps++;
  111.         for(int b = 0; b < temp.length; b++){
  112.             a[b + first] = temp[b];
  113.             steps += 3;
  114.         }
  115.     }
  116.     public void mergeSort(int[] a, int first, int last){
  117.         steps ++;
  118.         int temp;
  119.         if ((last - first) == 0);
  120.         else if (last - first == 1){
  121.             steps++;
  122.             if (a[first] > a[last]){
  123.                 temp = a[first];
  124.                 a[first] = a[last];
  125.                 a[last] = temp;
  126.                 steps += 3;
  127.             }
  128.         }
  129.         else
  130.             {
  131.                 int mid = (last + first)/2;
  132.                 mergeSort(a, first, mid);
  133.                 mergeSort(a, mid + 1, last);
  134.                 merge(a, first, mid, last);
  135.                 steps += 4;                
  136.             }
  137.     }
  138.     public void quickSort(int[] list, int first, int last){
  139.         steps += 3;
  140.         int g = first, h = last;
  141.         int midIndex = (first + last) / 2;
  142.         int dividingValue = list[midIndex];
  143.         do{
  144.             steps ++;
  145.             while (list[g] < dividingValue){
  146.                 g++;
  147.                 steps++;
  148.             }
  149.             while (list[h] > dividingValue){
  150.                 h--;
  151.                 steps ++;
  152.             }
  153.             steps++;
  154.             if (g <= h){
  155.                 steps += 5;
  156.                 int temp = list[g];
  157.                 list[g] = list[h];
  158.                 list[h] = temp;
  159.                 g++;
  160.                 h--;
  161.             }
  162.         }
  163.         while (g < h);
  164.         steps++;
  165.         if (h > first){
  166.             quickSort (list,first,h);
  167.             steps++;
  168.         }
  169.         if (g < last){
  170.             quickSort (list,g,last);
  171.             steps++;
  172.         }
  173.     }
  174.     public long getStepCount(){
  175.         return steps;
  176.     }
  177.     public void setStepCount(int stepCount){
  178.         steps = stepCount;
  179.     }
  180. }
Advertisement
Add Comment
Please, Sign In to add comment