kap12

kap12.java

package kap12;

public class Kap12 {
  static int[] array = {
    1,
    2,
    3,
    4,
    5,
    6,
    7,
    8,
    9,
    10
  };
  
  static int[] array_unsorted = {
    8,
    1,
    3,
    5,
    10,
    7,
    4,
    9,
    2,
    6
  };

  public static void main(String[] args) {
//    Suchen suchen = new Suchen();
//    System.out.println(array.length + " " + suchen.findMax(array));
//    System.out.println(suchen.findElement(array, 7));
//    System.out.println(suchen.findElement(array, 11));   
//    System.out.println(suchen.findElementBin(array, 10));
//    System.out.println(suchen.findElementBin(array, 11));
//    
    Sortieren sortieren = new Sortieren();
//    sortieren.bubbleSort(array_unsorted);
//    for (int i = 0; i < array_unsorted.length; i++) {
//      System.out.print(array_unsorted[i] + " ");
//    }
//    System.out.println();
//    
//    sortieren.insertionSort(array_unsorted);
//    for (int i = 0; i < array_unsorted.length; i++) {
//      System.out.print(array_unsorted[i] + " ");
//    }
//    System.out.println();
//    
//    sortieren.shellSort(array_unsorted);
//    for (int i = 0; i < array_unsorted.length; i++) {
//      System.out.print(array_unsorted[i] + " ");
//    }
//    System.out.println();
    
    sortieren.quickSort(array_unsorted, 0, 9);
    for (int i = 0; i < array_unsorted.length; i++) {
      System.out.print(array_unsorted[i] + " ");
    }
    System.out.println();
  }
  
}

sortieren.java

package kap12;

public class Sortieren {
  
  private int divideAndSort(int[] field, int left, int right) {
    int divider = field[left];
    int i = left + 1;
    int j = right;
    boolean isFinished = false;
    int tmp = 0;
    
    while (!isFinished) {
      while ((field[i] <= divider) && (i < right)) {
        i++;
      }
      while ((field[j] >= divider) && (j > left)) {
        j--;
      }
      if (i >= j) {
        isFinished = true;
      } else {
        tmp = field[i];
        field[i] = field[j];
        field[j] = tmp;     
      }
    }
    
    tmp = field[j];
    field[j] = field[left];
    field[left] = tmp;
    
    return j;
  }
  
  public void quickSort(int[] field, int left, int right) {
    if (right > left) {
      int p = divideAndSort(field, left, right);
      
      quickSort(field, left, p - 1);
      quickSort(field, p + 1, right);
    }
  }
  
  public void shellSort(int[] field) {
    int tmp;
    int h = 1;
    int j;
    
    do {
      h = 3 * h + 1;
    } while (h < field.length);
        
    do {
      h = h / 3;
      for (int i = h; i < field.length; i++) {
        tmp = field[i];
        j = i;
        while ((j >= h) && (field[j - h] > tmp)) {
          field[j] = field[j - h];
          j -= h;
        }
        field[j] = tmp;
      }
    } while (h != 1);
  }
  
  public void insertionSort(int[] field) {
    int tmp;
    int j;
    
    for (int i = 1; i < field.length; i++) {
      tmp = field[i];
      j = i;
      while ((j > 0) && (field[j - 1] > tmp)) {
        field[j] = field[j - 1];
        j -= 1;
      }
      field[j] = tmp;
    }
  }
  
  public void bubbleSort(int [] field) {
    int tmp;
    
    for (int i = field.length - 1; i > -1; i--) {
      for (int j = 0; j < i; j++) {
        if (field[j] > field[j + 1]) {
          tmp = field[j];
          field[j] = field[j + 1];
          field[j + 1] = tmp;
        }
      }
    }
  }
}

suchen.java

package kap12;

public class Suchen {
  public static int findElementBin(int[] field, int element) {
    int left = 0;
    int right = field.length - 1;
    int middle = 0; 
    
    while (left <= right) {
      middle = (left + right) / 2;
      if (field[middle] == element) {
        return middle;
      } else if (field[middle] > element) {
        right = middle - 1;
      } else {
        left = middle + 1;
      }
    }
    
    return -1;
  }
  
  public static int findElement(int[] field, int element) {
    int pos = 0;
    
    for (int i = 0; i < field.length; i++) {
      if (field[pos] == element) {
        return pos;
      } else {
          pos++;
      }
    }
    
    return -1;
  }
  
  public static int findMax(int[] field) {
    int max = 0;
    
    for (int i = 1; i < field.length; i++) {
      if (field[i] > field[max]) {
        max = i;
      }
    }
    
    return max;
  }
}