Hello! In this post, we will discuss the “Sorting Numbers” algorithm problem that can help in preparing for coding tests in Java. The number sorting problem plays a very important role in understanding data structures and algorithms, as well as improving problem-solving skills. In this post, we will explain the problem definition, solution methods, and provide example code in detail.

Problem Definition

The task is to implement an algorithm that sorts a given integer array in ascending order. The length of the array ranges from 1 to 1,000,000, and each integer value ranges from -1,000,000,000 to 1,000,000,000. Through this problem, you can learn the concept of sorting algorithms and how to handle arrays in Java.

Problem Solving Strategy

To solve this problem, we can use various sorting algorithms. The most common sorting algorithms include bubble sort, selection sort, insertion sort, quick sort, and merge sort. However, considering the size of the given array and performance requirements, using quick sort or merge sort would be effective.

Quick Sort

Quick sort has an average time complexity of O(n log n) and is known for its fast performance. It works by choosing a pivot and recursively sorting the values based on whether they are smaller or larger than the pivot.

Merge Sort

Merge sort also has a time complexity of O(n log n) and is a stable sorting algorithm. It operates by dividing the array in half, sorting each half, and then merging them back together. Merge sort generally performs well when dealing with large amounts of data.

Example Input and Output

Now let’s take a look at an example.

Input

[5, 3, 8, 6, 2, 7, 4, 1]

Output

[1, 2, 3, 4, 5, 6, 7, 8]

Java Code Implementation

Now, let’s implement quick sort in Java.


import java.util.Arrays;

public class QuickSortExample {

    public static void main(String[] args) {
        int[] arr = {5, 3, 8, 6, 2, 7, 4, 1};
        quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    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;
    }
}

Code Execution Result

When you run the above code, the following result will be output:

[1, 2, 3, 4, 5, 6, 7, 8]

Explanation of the Process

Now, I will explain each part in detail.

1. Main Method

In the main method, we first define the array to be sorted and call the quickSort method. The quickSort method takes the array and the starting and ending indices of the array as arguments to begin sorting.

2. Quick Sort Method

The quickSort method is a recursive function that sorts the array within the given range. It only executes while low is less than high. During this time, the partition method is called to set the pivot, and the index of the pivot is received, allowing the array to be split into two for recursive sorting.

3. Partition Method

The partition method is responsible for dividing the array based on the pivot. It selects the last value of the array as the pivot and moves values smaller than the pivot to the left and larger values to the right. After partitioning, it returns the final position of the pivot.

4. Swap Method

The swap method exchanges the values at two indices i and j in the array. It is used to perform the necessary swap operations when sorting the array.

Conclusion

In this post, we implemented the quick sort algorithm through the "Sorting Numbers" problem. Such problems frequently appear in coding tests, so it is important to understand and be able to implement various sorting algorithms. Quick sort can have a time complexity of O(n^2) in the worst case, but it is an excellent algorithm that shows fast performance on average. In the next post, we will cover more diverse data structures and algorithms. Thank you!