Sắp xếp thay thế

Cho một mảng số nguyên n phần tử. Xuất mạng theo dạng số lớn nhất – số bé nhất – số lớn thứ nhì – số bé thứ nhì cứ như vậy cho đến hết mảng.

Ví dụ:

Input: arr[] = {6, 2, 8, 4, 9, 3, 0, 4}

Output: 9 0 8 2 6 3 4 4

Chắc hẳn là chúng ta sẽ phải đụng gì đến sắp xếp mảng rồi phải không nào? 

B1: Sắp xếp mảng tăng dần

B2: Loop mảng từ 0 -> n/2.
      (1), Xuất arr[n – 1 – i](số lớn thứ i)
      (2), Xuất arr[i] (số bé nhất thứ i)

B3: if (n % 2 != 0) thì xuất arr[n/2] 

import java.util.Arrays;

public class Main {

    public static void alternativeSorted(int[] arr, int n) {
        Arrays.sort(arr);
        for(int i = 0; i < n/2; i++) {
            System.out.print(arr[n - 1 -i] + " ");
            System.out.print(arr[i] + " ");
        }
        if (n%2 != 0){
            System.out.println(arr[n/2]);
        }
    }
    public static void main(String[] args) {
        int[] arr = {6, 2, 8, 4, 9, 3, 0, 4};
        alternativeSorted(arr, arr.length);
    }
}

Output: 9 0 8 2 6 3 4 4

Độ phức tạp: O(nlog(n))

Note: Độ phức tạp phụ thuộc vào thuật toán sắp xếp mà bạn chọn. Ở đây của mình là QuickSort có độ phức tạp là O(nlog(n)). Nếu bạn chọn là selection sort thì độ phức tạp O(n^2).

Các bạn có thể chi tiết và độ phức tạp của các thuật toán sắp xếp tại đây.

Link tham khảo: https://www.geeksforgeeks.org/alternative-sorting/