Interchange Sort - Deft Blog

Mục lục

1 Minh hoạ
2 Implementation

Interchange sort hay còn gọi là thuật toán sắp xếp đổi chỗ trực tiếp. Ý tưởng của thuật toán này là bắt cặp tất cả các phần tử trong dãy cần sắp xếp và đổi chỗ hai phần tử trong cặp nếu chúng không thoả mãn điều kiện về thứ tự.

Các bước làm của Interchange Sort cho sắp xếp tăng dần.

B1: Loop i từ 0 đến n - 2
B2: Với mỗi giá trị tại Array[i] , 
    + loop j từ i + 1 đến n - 1
       $ nếu Arrary[i] > Array[j] swap Array[i] với Array[j].

Minh hoạ

Cho arr[] = {5, 1, 3, 2, 6}

Lần lặp 1:
i = 0, j = 1: arr[i] > arr[j] => swap arr[i] & arr[j], arr[] = {1, 5, 3, 2, 6}
i = 0, j = 2: arr[i] < arr[j] => bỏ qua
i = 0, j = 3: arr[i] < arr[j] => bỏ qua
i = 0, j = 4: arr[i] < arr[j] => bỏ qua

arr[] = {1, 5, 3, 2, 6}

Lần lặp 2:
i = 1, j = 2: arr[i] > arr[j] => swap arr[i] & arr[j], arr[] = {1, 3, 5, 2, 6}
i = 1, j = 3: arr[i] > arr[j] => swap arr[i] & arr[j], arr[] = {1, 2, 5, 3, 6}
i = 1, j = 4: arr[i] < arr[j] => bỏ qua

arr[] = {1, 2, 5, 3, 6}

Lần lặp 3:
i = 2, j = 3: arr[i] > arr[j] => swap arr[i] & arr[j], arr[] = {1, 2, 3, 5, 6}
i = 2, j = 4: arr[i] < arr[j] => bỏ qua

arr[] = {1, 2, 3, 5, 6}

Lần lặp 4:
i = 3, j = 4: arr[i] < arr[j] => bỏ qua

arr[] = {1, 2, 3, 5, 6}

Implementation

public static <T extends Comparable<T>> void sort(T[] arr, int n) {
        for(int i = 0; i < n - 1; i++) {
            for(int j = i + 1; j < n; j++) {
                if (arr[i].compareTo(arr[j]) > 0) {
                    T tmp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = tmp;
                }
            }
        }
    }

Với mọi độ dữ liệu thì Interchange vẫn sử dụng 2 vòng lặp để so sánh và hoán đổi từng cặp giá trị trong mảng, Ta có thể ước lượng số phép so sánh bằng (n-1) + (n-2) + … + 1 = n(n-1)/2, vậy độ phức tạp của InterchangeSort là θ(n²).

Link source code: InterchangeSort