Sắp xếp mảng theo dạng sóng

Cho một mảng số nguyên có n phần tử, sắp xếp mảng theo dạng sóng. Mảng có dạng sóng : arr[0] >= arr[1] <= arr[2] <= arr[3] >= …

Ví dụ

Input: arr[] = {4, 1, 8, 5, 9}

Output: arr[] ={4, 1, 8, 5, 9}

Cách 1: Sắp xếp

Sau khi chúng ta sắp xếp được mảng tăng dần, chúng ta chỉ cần swap từng đôi một trong mảng là chúng ta sẽ có mảng có dạng sóng rồi đó các bạn.

Các bạn có thể dùng thuật toán sắp xếp nào tuỳ ý nhé. Còn mình dùng thư viện hỗ trợ sẵn của java =). 

import java.util.Arrays;

public class Main {

   public static void swap(int arr[], int a, int b)
    {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

   public static void sortInWaveSorted(int arr[], int n) {
        Arrays.sort(arr);
        int i = 0;
        while (i < n - 1) {
            swap(arr, i, i + 1);
            i+=2;
        }
    }

    public static void main(String[] args) {
        int arr[] = {4, 6, 1, 8, 5, 9};
        int n = arr.length;
        sortInWaveSorted(arr, n);
        for (int i : arr)
            System.out.print(i+" ");

    }
}

Output: arr[] = {4, 1, 8, 5, 9}

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

Cách 2: Tính chất dãy số arr[i] >= arr[i+1] <= arr[i + 2]

Chúng ta thấy mỗi bộ 3 trong mảng chỉ cần làm cho chúng thoả điều kiện arr[i – 1] >= arr[i] <= arr[i+ 1]

Với cách này chúng ta chỉ cần duyệt qua mảng một lần nên độ phức tạp là O(n)  nhé.

import java.util.Arrays;

public class Main {
    public static void swap(int arr[], int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void sortInWave(int arr[], int n) {
        for (int i = 0; i < n; i += 2) {

            // Sure arr[i] <= arr[i - 1
            if (i > 0 && arr[i - 1] > arr[i])
                swap(arr, i - 1, i);

            // Make sure arr[i] >= arr[i + 1]
            if (i < n - 1 && arr[i] < arr[i + 1])
                swap(arr, i, i + 1);
        }
    }

   public static void main(String[] args) {
        int arr[] = {6, 2, 4, 9, 10, 100, 55, 2, 77};
        sortInWave(arr, arr.length);
        for (int i : arr)
            System.out.print(i + " ");

    }
}

Output: arr[] = {6, 2, 9, 4, 100, 10, 55, 2, 77 }

Full source: source

Link tham khảo: https://gitlab.com/exercise_array/sort_arrray_wave_form/blob/master/Main.java