Bài tập về các thuật toán sắp xếp trong Java có lời giải

package vn.eLib.array;

public class SapXepNoBot {

  public void bubbleSort(int arr[]) {
    int temp;
    int i,
    j;

    boolean swapped = false;

    // lap qua tat ca cac so
    for (i = 0; i < arr.length - 1; i++) {
      swapped = false;

      // vong lap thu hai
      for (j = 0; j < arr.length - 1 - i; j++) {
        System.out.print("So sanh cac phan tu: [" + arr[j] + ", " + arr[j + 1] + "]");

        // kiem xa xem so ke tiep co nho hon so hien tai hay khong
        // trao doi cac so.
        // (Muc dich: lam noi bot (bubble) so lon nhat)
        if (arr[j] > arr[j + 1]) {
          temp = arr[j];
          arr[j] = arr[j + 1];
          arr[j + 1] = temp;

          swapped = true;
          System.out.println(" => trao doi [" + arr[j] + ", " + arr[j + 1] + "]");
        } else {
          System.out.println(" => khong can trao doi.");
        }
      }

      // neu khong can trao doi nua, tuc la
      // mang da duoc sap xep va thoat khoi vong lap.
      if (!swapped) {
        break;
      }

      System.out.println("Vong lap thu " + (i + 1));
      display(arr);
    }
  }

  public void display(int arr[]) {
    int i;
    System.out.print("[");

    // Duyet qua tat ca phan tu
    for (i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }

    System.out.print("]\n");
  }

  public static void main(String[] args) {
    // khoi tao mang arr
    int arr[] = {
      6,
      7,
      0,
      2,
      8,
      1,
      3,
      9,
      4,
      5
    };

    SapXepNoBot sapXepNoBot = new SapXepNoBot();
    System.out.println("Mang du lieu dau vao: ");
    sapXepNoBot.display(arr);
    System.out.println("-----------------------------");
    sapXepNoBot.bubbleSort(arr);
    System.out.println("-----------------------------");
    System.out.println("\nMang sau khi da sap xep: ");
    sapXepNoBot.display(arr);
  }
}

package vn.eLib.array;
public class SapXepChon {
  public void selectionSort(int arr[]) {
    int indexMin,
    i,
    j;
    // lap qua ta ca cac so
    for (i = 0; i < arr.length - 1; i++) {
      // thiet lap phan tu hien tai la min
      indexMin = i;
      // kiem tra phan tu hien tai co phai la nho nhat khong
      for (j = i + 1; j < arr.length; j++) {
        if (arr[j] < arr[indexMin]) {
          indexMin = j;
        }
      }
      if (indexMin != i) {
        System.out.println(" ==> Trao doi phan tu: [" + arr[i] + ", " + arr[indexMin] + "]");
        // Trao doi cac so
        int temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
      }
      System.out.println("Vong lap thu " + (i + 1));
      display(arr);
    }
  }
  public void display(int arr[]) {
    int i;
    System.out.print("[");
    // Duyet qua tat ca phan tu
    for (i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.print("]\n");
  }
  public static void main(String[] args) {
    // khoi tao mang arr
    int arr[] = {
      6,
      7,
      0,
      2,
      8,
      1,
      3,
      9,
      4,
      5
    };

    SapXepChon sapXepChon = new SapXepChon();
    System.out.println("Mang du lieu dau vao: ");
    sapXepChon.display(arr);
    System.out.println("-----------------------------");
    sapXepChon.selectionSort(arr);
    System.out.println("-----------------------------");
    System.out.println("\nMang sau khi da sap xep: ");
    sapXepChon.display(arr);
  }

package vn.eLib.array;
public class SapXepChen {
  public void insertionSort(int arr[]) {
    int valueToInsert;
    int holePosition;
    int i;
    // lap qua tat ca cac so
    for (i = 1; i < arr.length; i++) {
      // chon mot gia tri de chen
      valueToInsert = arr[i];
      // lua chon vi tri de chen
      holePosition = i;
      // kiem tra xem so lien truoc co lon hon gia tri duoc chen khong
      while (holePosition > 0 && arr[holePosition - 1] > valueToInsert) {
        arr[holePosition] = arr[holePosition - 1];
        holePosition--;
        System.out.println("Di chuyen phan tu: " + arr[holePosition]);
      }
      if (holePosition != i) {
        System.out.println(" Chen phan tu: " + valueToInsert + ", tai vi tri: " + holePosition);
        // chen phan tu tai vi tri chen
        arr[holePosition] = valueToInsert;
      }
      System.out.println("Vong lap thu " + i);
      display(arr);
    }
  }
  public void display(int arr[]) {
    int i;
    System.out.print("[");
    // Duyet qua tat ca phan tu
    for (i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.print("]\n");
  }
  public static void main(String[] args) {
    // khoi tao mang arr
    int arr[] = {
      6,
      7,
      0,
      2,
      8,
      1,
      3,
      9,
      4,
      5
    };
    SapXepChen sapXepChen = new SapXepChen();
    System.out.println("Mang du lieu dau vao: ");
    sapXepChen.display(arr);
    System.out.println("-----------------------------");
    sapXepChen.insertionSort(arr);
    System.out.println("-----------------------------");
    System.out.println("\nMang sau khi da sap xep: ");
    sapXepChen.display(arr);
  }
}

package vn.eLib.array;
public class SapXepTron {
  public void merging(int arr[], int temp[], int low, int mid, int high) {
    int l1,
    l2,
    i;
    l1 = low;
    l2 = mid + 1;
    for (i = low; l1 <= mid && l2 <= high; i++) {
      if (arr[l1] <= arr[l2]) {
        temp[i] = arr[l1++];
      } else {
        temp[i] = arr[l2++];
      }
    }
    while (l1 <= mid) {
      temp[i++] = arr[l1++];
    }
    while (l2 <= high) {
      temp[i++] = arr[l2++];
    }
    for (i = low; i <= high; i++) {
      arr[i] = temp[i];
    }
  }
  public void sort(int arr[], int temp[], int low, int high) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      sort(arr, temp, low, mid);
      sort(arr, temp, mid + 1, high);
      merging(arr, temp, low, mid, high);
      // hien thi mang
      display(arr);
    } else {
      return;
    }
  }
  public void display(int arr[]) {
    int i;
    System.out.print("[");
    // Duyet qua tat ca phan tu
    for (i = 0; i < arr.length; i++) {
      System.out.print(arr[i] + " ");
    }
    System.out.print("]\n");
  }
  public static void main(String[] args) {
    // khoi tao mang arr
    int arr[] = {
      6,
      7,
      0,
      2,
      8,
      1,
      3,
      9,
      4,
      5
    };
    int temp[] = new int[10];
    SapXepTron sapXeptron = new SapXepTron();
    System.out.println("Mang du lieu dau vao: ");
    sapXeptron.display(arr);
    System.out.println("-----------------------------");
    sapXeptron.sort(arr, temp, 0, arr.length - 1);
    System.out.println("-----------------------------");
    System.out.println("\nMang sau khi da sap xep: ");
    sapXeptron.display(arr);
  }
}