lec5

Sort.java

import java.lang.Math; // headers MUST be above the first class
import java.util.*;

// one class needs to have a main() method
public class Sort {
  // arguments are passed using the text field below this editor
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);

    System.out.println("Please insert array size of 10:");

    int[] inputArray = new int[10];
    for (int i = 0; i < 10; i++) {
      inputArray[i] = scanner.nextInt();
    }

    bubble_sort(inputArray);

    System.out.print("Enter the number of elements: ");
    int partitionCount = scanner.nextInt();

    System.out.print("Enter a list: ");
    int[] partitionInputArray = new int[partitionCount];
    for (int i = 0; i < partitionCount; i++) {
      partitionInputArray[i] = scanner.nextInt();
    }

    quickSortSinglePathRef(partitionInputArray, 0, partitionInputArray.length - 1);
    print_arr(partitionInputArray);

    scanner.close();

    // prob3();

    return;
  }

  public static void prob3() {
    int[][] arr = { { 2, 4, 3, 4, 5, 8, 8 }, { 7, 3, 4, 3, 3, 4, 4 }, { 3, 3, 4, 3, 3, 2, 2 }, { 9, 3, 4, 7, 3, 4, 1 },
        { 3, 5, 4, 3, 6, 3, 8 }, { 3, 4, 4, 6, 3, 4, 4 }, { 3, 7, 4, 8, 3, 8, 4 }, { 6, 3, 5, 9, 2, 7, 9 } };

    int[][] employee_wise_total = new int[arr.length][2];

    for (int i = 0; i < arr.length; i++) {
      employee_wise_total[i] = new int[] { i, sum(arr[i]) };
    }

    for (int i = 0; i < employee_wise_total.length - 1; i++) {
      for (int j = 0; j < employee_wise_total.length - 1; j++) {
        if (employee_wise_total[j][1] > employee_wise_total[j + 1][1]) {
          int[] total = employee_wise_total[j].clone();
          employee_wise_total[j] = employee_wise_total[j + 1].clone();
          employee_wise_total[j + 1] = total.clone();
        }
      }
    }

    for (int i = employee_wise_total.length - 1; i >= 0; i--) {
      System.out.printf("Employee %d: %d\n", employee_wise_total[i][0], employee_wise_total[i][1]);
    }
  }

  public static int sum(int[] arr) {
    int res = 0;
    for (int i = 0; i < arr.length; i++) {
      res += arr[i];
    }
    return res;
  }

  public static void quickSortSinglePathRef(int[] arr, int l, int r) {
    int len = arr.length;
    int pivot = arr[l];
    int left = l - 1;
    int right = r + 1;
    while (true) {
      do {
        left++;
      } while (arr[left] <= pivot && left < len - 1);

      do {
        right--;
      } while (arr[right] > pivot);

      if (left >= right) {
        int temp = arr[right];
        arr[right] = arr[l];
        arr[l] = temp;
        return;
      }
      int temp = arr[right];
      arr[right] = arr[left];
      arr[left] = temp;
    }
  }

  public static void quickSortSinglePath(int[] arr, int l, int r) {
    int left = l + 1;
    int right = r;
    int pivot = arr[l];
    while (left < right) {
      if (arr[left] < pivot) {
        left++;
      } else if (arr[right] > pivot) {
        right--;
      } else {
        int temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
      }
    }
    int pivotLoc = right - 1;
    int temp = arr[pivotLoc];
    arr[pivotLoc] = pivot;
    arr[l] = temp;
  }

  public static int partition(int[] arr) {
    int len = arr.length;
    int pivot = arr[0];
    int left = 1;
    int right = len - 1;
    while (left < right) {
      if (arr[left] < pivot) {
        left++;
      } else if (arr[right] > pivot) {
        right--;
      } else {
        int temp = arr[right];
        arr[right] = arr[left];
        arr[left] = temp;
      }
    }
    return right - 1;
  }

  public static void bubble_sort(int[] arr) {
    int len = arr.length;
    System.out.printf("Initial array: ");
    print_arr(arr);

    for (int i = 0; i < len - 1; i++) {
      for (int j = 0; j < len - 1; j++) {
        if (arr[j] > arr[j + 1]) {
          int temp = arr[j + 1];
          arr[j + 1] = arr[j];
          arr[j] = temp;
        }
      }
      System.out.printf("After pass #%d: ", i + 1);
      print_arr(arr);
    }
  }

  public static void print_arr(int[] arr) {
    int len = arr.length;
    for (int i = 0; i < len; i++) {
      System.out.printf("%d", arr[i]);
      if (i < len - 1) {
        System.out.printf(" ");
      }
    }
    System.out.printf("\n");
  }
}