{"id":33516,"date":"2024-11-01T09:17:21","date_gmt":"2024-11-01T09:17:21","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=33516"},"modified":"2024-11-01T11:38:13","modified_gmt":"2024-11-01T11:38:13","slug":"java-coding-test-course-card-sorting","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/33516\/","title":{"rendered":"Java Coding Test Course, Card Sorting"},"content":{"rendered":"

<\/p>\n

Problem Description<\/h2>\n

\n You are a card organization expert. Each card has a number from 1 to N written on it.
\n However, the cards are shuffled. Your goal is to sort the given cards in ascending order.
\n 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.<\/strong>\n<\/p>\n

Input<\/h3>\n

\n The first line contains the number of cards N (1 \u2264 N \u2264 10^6).
\n The second line contains N integers A1, A2, …, AN (1 \u2264 Ai \u2264 10^9).
\n This array represents the numbers on the cards.\n <\/p>\n

Output<\/h3>\n

\n Output the numbers on each card sorted in ascending order, each on a new line.\n <\/p>\n

Problem-Solving Strategy<\/h2>\n

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

Merge Sort<\/h3>\n

\n Merge Sort is a type of Divide and Conquer algorithm that sorts through the following steps:\n <\/p>\n

    \n
  1. Split the array in half.<\/li>\n
  2. Recursively sort each half.<\/li>\n
  3. Merge the sorted two arrays to obtain the final sorted array.<\/li>\n<\/ol>\n

    Java Code<\/h3>\n
    \n        \npublic class CardSorting {\n    public static void main(String[] args) {\n        int[] cards = {3, 2, 5, 4, 1}; \/\/ Example input\n        mergeSort(cards, 0, cards.length - 1);\n        System.out.println(\"Sorted cards:\");\n        for (int card : cards) {\n            System.out.print(card + \" \");\n        }\n    }\n\n    public static void mergeSort(int[] array, int left, int right) {\n        if (left < right) {\n            int mid = (left + right) \/ 2;\n\n            mergeSort(array, left, mid);\n            mergeSort(array, mid + 1, right);\n\n            merge(array, left, mid, right);\n        }\n    }\n\n    public static void merge(int[] array, int left, int mid, int right) {\n        int n1 = mid - left + 1;\n        int n2 = right - mid;\n\n        int[] L = new int[n1];\n        int[] R = new int[n2];\n\n        for (int i = 0; i < n1; i++) {\n            L[i] = array[left + i];\n        }\n        for (int j = 0; j < n2; j++) {\n            R[j] = array[mid + 1 + j];\n        }\n\n        int i = 0, j = 0;\n        int k = left;\n        while (i < n1 && j < n2) {\n            if (L[i] <= R[j]) {\n                array[k] = L[i];\n                i++;\n            } else {\n                array[k] = R[j];\n                j++;\n            }\n            k++;\n        }\n\n        while (i < n1) {\n            array[k] = L[i];\n            i++;\n            k++;\n        }\n\n        while (j < n2) {\n            array[k] = R[j];\n            j++;\n            k++;\n        }\n    }\n}\n        <\/code>\n    <\/pre>\n
    Complexity Analysis<\/h2>\n
    \n        The time complexity of Merge Sort is
    \n        O(N log N)<\/strong>. This is because merging two sorted arrays takes O(N), and continually splitting the array takes log N.
    \n        Therefore, it can efficiently sort large card datasets.\n    <\/p>\n
    Conclusion<\/h2>\n
    \n        In this article, we explored solving the card sorting problem using Merge Sort.
    \n        The implementation of Merge Sort in Java enhances understanding of the importance of various data structures and algorithms.
    \n        Keep addressing such problems to continuously improve your Java programming skills.\n    <\/p>\n
    Further Reading<\/h2>\n