This lecture will cover the coding test preparation problem using Java, “Sorting Numbers 2”<\/strong>. This problem requires sorting the given numbers in ascending order. In particular, the goal of this course is to cultivate the ability to implement efficient sorting algorithms. Along with the process of solving the problem, I will explain the solution in detail using Java code.<\/p>\n The problem is stated as follows:<\/p>\n The output should print each integer in sorted order, one per line.<\/p>\n The given problem is a basic sorting problem that can be solved using various sorting algorithms. However, since the input size (N) can be up to 100,000 and each number can be up to 1,000,000, an efficient algorithm is essential. Among several sorting algorithms available in Java, algorithms with efficient O(N log N) time complexity such as Quick Sort<\/strong> or Merge Sort<\/strong> are suitable.<\/p>\n The goal of this lecture is to implement a sorting algorithm suitable for Java coding tests to solve the problem. In Java, the Arrays.sort() method can easily perform sorting, but it is important to learn about the internal workings of sorting algorithms. Therefore, we will implement a sorting algorithm ourselves.<\/p>\n Quick Sort is a divide and conquer algorithm with an average time complexity of O(N log N). First, a pivot is selected, and then values smaller than the pivot are placed on the left, and larger values on the right to partition the array. This process is repeated recursively to complete the sorting. The overall flow is as follows:<\/p>\n Below is the Java code that solves the problem using the Quick Sort algorithm:<\/p>\nProblem Definition<\/h2>\n
\nGiven N integers, write a program to sort them in ascending order.\nThe input will have the first line containing the integer N (1 \u2264 N \u2264 100,000),\nfollowed by N lines where each integer is a natural number not exceeding 1,000,000.\n<\/code><\/pre>\n
\n5
\n5
\n4
\n3
\n2
\n1\n<\/div>\n
\n1
\n2
\n3
\n4
\n5\n<\/div>\nProblem Analysis<\/h2>\n
Algorithm Selection<\/h2>\n
Quick Sort Algorithm<\/h3>\n
\n
Java Code Implementation<\/h2>\n
\nimport java.util.Scanner;\n\npublic class Main {\n public static void quickSort(int[] array, int low, int high) {\n if (low < high) {\n int pivotIndex = partition(array, low, high);\n quickSort(array, low, pivotIndex - 1);\n quickSort(array, pivotIndex + 1, high);\n }\n }\n\n public static int partition(int[] array, int low, int high) {\n int pivot = array[high];\n int i = low - 1;\n\n for (int j = low; j < high; j++) {\n if (array[j] <= pivot) {\n i++;\n swap(array, i, j);\n }\n }\n swap(array, i + 1, high);\n return i + 1;\n }\n\n public static void swap(int[] array, int i, int j) {\n int temp = array[i];\n array[i] = array[j];\n array[j] = temp;\n }\n\n public static void main(String[] args) {\n Scanner scanner = new Scanner(System.in);\n int N = scanner.nextInt();\n int[] numbers = new int[N];\n\n for (int i = 0; i < N; i++) {\n numbers[i] = scanner.nextInt();\n }\n\n quickSort(numbers, 0, N - 1);\n\n for (int number : numbers) {\n System.out.println(number);\n }\n\n scanner.close();\n }\n}\n<\/code><\/pre>\nCode Explanation<\/h3>\n