Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- http://pastebin.com/0DT6aQJK
- import java.util.*;
- public class Sorts{
- private long steps;
- Sorts(){
- steps = 0;
- }
- public void bubbleSort(int[] list){
- steps++; // initialization of outer
- for (int outer = 0; outer < list.length - 1; outer++){
- steps += 3;
- // 1 - boundary check of outer loop;
- // 2 - increment, outer++
- // 3 - initialization of inner loop
- for (int inner = 0; inner < list.length - outer - 1; inner++){
- steps += 3;
- // 1 - boundary check of inner loop
- // 2 - increment, inner++
- // 3 - if comparison
- if (list[inner] > list[inner+1]){
- int temp = list[inner];
- list[inner] = list[inner + 1];
- list[inner + 1] = temp;
- steps += 3; // swap of list[inner] & list[inner + 1]
- }
- }
- }
- System.out.println();
- System.out.println("Bubble Sort");
- System.out.println();
- }
- public void selectionSort(int[] list){
- steps++;
- int min, temp;
- for (int outer = 0; outer < list.length - 1; outer++){
- min = outer;
- steps += 7;
- for (int inner = outer + 1; inner < list.length; inner++){
- steps += 3;
- if (list[inner] < list[min]){
- steps++;
- min = inner;
- }
- }
- //swap list[outer] & list[flag]
- temp = list[outer];
- list[outer] = list[min];
- list[min] = temp;
- }
- System.out.println();
- System.out.println("Selection Sort");
- System.out.println();
- }
- public void insertionSort(int[] list){
- steps++;
- for (int outer = 1; outer < list.length; outer++){
- steps += 5;
- int position = outer;
- int key = list[position];
- // Shift larger values to the right
- while (position > 0 && list[position - 1] > key){
- steps += 4;
- list[position] = list[position - 1];
- position--;
- }
- list[position] = key;
- }
- System.out.println();
- System.out.println("Insertion Sort");
- System.out.println();
- }
- /**
- * Takes in entire array 'a', but will merge the following subsections
- * together: Left sublist from a[first]..a[mid], right sublist from
- * a[mid+1]..a[last]. Precondition: each sublist is already in
- * ascending order
- */
- private void merge(int[] a, int first, int mid, int last){
- steps += 4;
- int[] temp = new int[last - first + 1];
- int i = first;
- int j = mid + 1;
- for(int k = 0; k < temp.length; k++){
- steps += 3;
- if(i > mid){
- temp[k] = a[j];
- j++;
- steps += 2;
- }
- else if(j > last){
- temp[k] = a[i];
- i++;
- steps += 2;
- }
- else {
- steps++;
- if(a[i] >= a[j]){
- temp[k] = a[j];
- j++;
- steps += 2;
- }
- else{
- temp[k] = a[i];
- i++;
- steps += 2;
- }
- }
- }
- steps++;
- for(int b = 0; b < temp.length; b++){
- a[b + first] = temp[b];
- steps += 3;
- }
- }
- public void mergeSort(int[] a, int first, int last){
- steps ++;
- int temp;
- if ((last - first) == 0);
- else if (last - first == 1){
- steps++;
- if (a[first] > a[last]){
- temp = a[first];
- a[first] = a[last];
- a[last] = temp;
- steps += 3;
- }
- }
- else
- {
- int mid = (last + first)/2;
- mergeSort(a, first, mid);
- mergeSort(a, mid + 1, last);
- merge(a, first, mid, last);
- steps += 4;
- }
- }
- public void quickSort(int[] list, int first, int last){
- steps += 3;
- int g = first, h = last;
- int midIndex = (first + last) / 2;
- int dividingValue = list[midIndex];
- do{
- steps ++;
- while (list[g] < dividingValue){
- g++;
- steps++;
- }
- while (list[h] > dividingValue){
- h--;
- steps ++;
- }
- steps++;
- if (g <= h){
- steps += 5;
- int temp = list[g];
- list[g] = list[h];
- list[h] = temp;
- g++;
- h--;
- }
- }
- while (g < h);
- steps++;
- if (h > first){
- quickSort (list,first,h);
- steps++;
- }
- if (g < last){
- quickSort (list,g,last);
- steps++;
- }
- }
- public long getStepCount(){
- return steps;
- }
- public void setStepCount(int stepCount){
- steps = stepCount;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment