Java Coding Test Course, Sort Array 2

This lecture will cover the coding test preparation problem using Java, “Sorting Numbers 2”. 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.

Problem Definition

The problem is stated as follows:

Given N integers, write a program to sort them in ascending order.
The input will have the first line containing the integer N (1 ≤ N ≤ 100,000),
followed by N lines where each integer is a natural number not exceeding 1,000,000.

The output should print each integer in sorted order, one per line.

Problem Analysis

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 or Merge Sort are suitable.

Algorithm Selection

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.

Quick Sort Algorithm

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:

1. Select a pivot from the array.
2. Rearrange the array based on the pivot.
3. Recursively perform quick sort on the left and right subarrays based on the rearranged array.

Java Code Implementation

Below is the Java code that solves the problem using the Quick Sort algorithm:

import java.util.Scanner;

public class Main {
    public static void quickSort(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            quickSort(array, low, pivotIndex - 1);
            quickSort(array, pivotIndex + 1, high);
        }
    }

    public static int partition(int[] array, int low, int high) {
        int pivot = array[high];
        int i = low - 1;

        for (int j = low; j < high; j++) {
            if (array[j] <= pivot) {
                i++;
                swap(array, i, j);
            }
        }
        swap(array, i + 1, high);
        return i + 1;
    }

    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt();
        int[] numbers = new int[N];

        for (int i = 0; i < N; i++) {
            numbers[i] = scanner.nextInt();
        }

        quickSort(numbers, 0, N - 1);

        for (int number : numbers) {
            System.out.println(number);
        }

        scanner.close();
    }
}

Code Explanation

Looking at the code, it first receives the integer N through input and stores those integers in an array through subsequent inputs. Then it calls the quickSort method to perform the sorting. The partition method selects the pivot, partitions the array, and returns the final position of the pivot, while the swap method exchanges the positions of two elements in the array.

Conclusion

Through this lecture, we learned how to solve algorithm problems using Java. The "Sorting Numbers 2" problem was solvable using a basic sorting algorithm. By actually implementing Quick Sort to perform sorting, we were able to enhance our understanding of the internal workings of algorithms. I hope that such problems will help improve your skills in Java coding tests.