Sắp xếp mảng theo trị tuyệt đối của X – arr[i]

Cho mảng số nguyên n phần tử. Sắp xếp mảng tăng dần theo giá trị tuyệt đối |x – arr[i]| với x là phần tử cho trước, arr[i] là các phần tử của mảng.

Ví dụ: arr[] = {10, 5, 3, 9, 2}, n = 5, x = 7

Output: arr[] = {5, 9, 10, 3, 2}

Giải thích

|7 – 10| = 3 => index = 2

|7 – 5| = 2 => 2 nhỏ nhất => 5 xếp ở index = 0 or 

|7 – 3| = 4 => index = 3

|7 – 9| = 2 => index = 1 or 0

|7 – 2| = 5 => index = 4

Bài này có rất nhiều cách giải. Mình đã tham khảo cách giải trên https://www.geeksforgeeks.org/sort-an-array-according-to-absolute-difference-with-given-value/.

Nhưng mà thấy nó sao sao ấy =). Mình thử suy nghĩ một chút.

Các thuật toán sắp xếp đều dựa trên nguyên tắc so sánh giá trị mà tìm ra vị trí hợp lý cho từng phần tử. Vậy trong trường hợp này chúng ta chỉ sửa lại những phép so sánh của thuật toán sắp xếp từ so sánh giá trị thành |x – giá trị| là xong rồi =).

Có rất nhiều thuật toán sắp xếp, mình sẽ chọn Quick sort để demo. Các bạn có thể chọn các thuật toán sắp xếp để custom nhé. 

public class Main {
    public static int partition(int[] arr, int low, int high, int x) {
        int pivot = arr[high];

        int i = low - 1;
        for (int index = low; index < high; index++) {
            // Custom condition compare
            if (Math.abs(x - arr[index]) <= (Math.abs(x - pivot))) {
                i++;
                int temp = arr[i];
                arr[i] = arr[index];
                arr[index] = temp;
            }
        }

        int temp1 = arr[i + 1];
        arr[i + 1] = arr[high];
        arr[high] = temp1;
        return i + 1;
    }

    public static void sort(int[] arr, int low, int high, int x) {
        if (low < high) {
            int pi = partition(arr, low, high, x);
            sort(arr, low, pi - 1, x);
            sort(arr, pi + 1, high, x);
        }
    }


    public static void main(String[] args) {
        int[] arr = {10, 5, 3, 9, 2};
        int x = 7;
        sort(arr, 0, arr.length -1, x);

        for (int value: arr) {
            System.out.println(value);
        }
    }
}

Output: arr[] = {5, 9, 10, 3, 2}

Độ phức tạp: O(nlogn).