Mục lục
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à θ(n2).
Link source code: InterchangeSort