Java Coding Test Course, Card Sorting

Problem Description

You are a card organization expert. Each card has a number from 1 to N written on it.
However, the cards are shuffled. Your goal is to sort the given cards in ascending order.
You can select one card at a time. The selected cards should be sorted in ascending order based on their numbers. You must sort the cards with the minimum number of comparisons.

Input

The first line contains the number of cards N (1 ≤ N ≤ 10^6).
The second line contains N integers A1, A2, …, AN (1 ≤ Ai ≤ 10^9).
This array represents the numbers on the cards.

Output

Output the numbers on each card sorted in ascending order, each on a new line.

Problem-Solving Strategy

To solve the card sorting problem, various sorting algorithms can be utilized.
In particular, it is good to implement efficient sorting algorithms such as Quick Sort or Merge Sort.
In this discussion, we will use Merge Sort to solve the problem.

Merge Sort

Merge Sort is a type of Divide and Conquer algorithm that sorts through the following steps:

  1. Split the array in half.
  2. Recursively sort each half.
  3. Merge the sorted two arrays to obtain the final sorted array.

Java Code

        
public class CardSorting {
    public static void main(String[] args) {
        int[] cards = {3, 2, 5, 4, 1}; // Example input
        mergeSort(cards, 0, cards.length - 1);
        System.out.println("Sorted cards:");
        for (int card : cards) {
            System.out.print(card + " ");
        }
    }

    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;

            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);

            merge(array, left, mid, right);
        }
    }

    public static void merge(int[] array, int left, int mid, int right) {
        int n1 = mid - left + 1;
        int n2 = right - mid;

        int[] L = new int[n1];
        int[] R = new int[n2];

        for (int i = 0; i < n1; i++) {
            L[i] = array[left + i];
        }
        for (int j = 0; j < n2; j++) {
            R[j] = array[mid + 1 + j];
        }

        int i = 0, j = 0;
        int k = left;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                array[k] = L[i];
                i++;
            } else {
                array[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            array[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            array[k] = R[j];
            j++;
            k++;
        }
    }
}

Complexity Analysis

The time complexity of Merge Sort is
O(N log N). This is because merging two sorted arrays takes O(N), and continually splitting the array takes log N.
Therefore, it can efficiently sort large card datasets.

Conclusion

In this article, we explored solving the card sorting problem using Merge Sort.
The implementation of Merge Sort in Java enhances understanding of the importance of various data structures and algorithms.
Keep addressing such problems to continuously improve your Java programming skills.

Further Reading