Overview
One of the common problems seen in coding tests is sorting a given number.
In this course, we will learn how to sort numbers using JavaScript.
The problem of sorting numbers is very useful for studying basic sorting algorithms.
We can sort numbers using various algorithms, each with different time and space complexities.
Problem Description
Problem
Write a function that takes an array of given numbers as input and returns a sorted array.
For example, if the input array is [3, 1, 2],
the output should be [1, 2, 3].
Input
- The first line contains an integer
N. (1 ≤ N ≤ 100,000) - The second line contains
NintegersA1, A2, ..., ANseparated by a single space.
(-1,000,000 ≤ Ai ≤ 1,000,000)
Output
You must print the sorted numbers in one line, separated by a single space.
Example
Input:
5
5 4 3 2 1
Output:
1 2 3 4 5
Problem Solving Process
Step 1: Requirements Analysis
To solve the given problem, the goal is to sort the input array and output it.
To do this, we can use classic sorting algorithms such as
Quick Sort and Merge Sort.
While we can use built-in JavaScript functions, it is important this time to implement the algorithms ourselves for understanding.
Step 2: Algorithm Selection
Among the sorting algorithms, Quick Sort and Merge Sort are generally widely used fast sorting algorithms.
Below, I will summarize the advantages and disadvantages of each algorithm.
Quick Sort
- Average time complexity:
O(N log N) - Worst-case time complexity:
O(N2)(with inefficient pivot selection) - Space complexity:
O(log N) - Advantages: Can perform in-place sorting with low memory usage.
- Disadvantages: It is not a stable sort.
Merge Sort
- Average and worst-case time complexity:
O(N log N) - Space complexity:
O(N) - Advantages: It is a stable sort.
- Disadvantages: Requires additional memory.
Step 3: Implementing Quick Sort
We will implement a function to sort an array of numbers using Quick Sort.
Below is the implementation code for Quick Sort written in JavaScript.
function quickSort(arr) {
if (arr.length <= 1) return arr;
const pivot = arr[arr.length - 1];
const left = [];
const right = [];
for (let i = 0; i < arr.length - 1; i++) {
if (arr[i] < pivot) {
left.push(arr[i]);
} else {
right.push(arr[i]);
}
}
return [...quickSort(left), pivot, ...quickSort(right)];
}
Step 4: Implementing Merge Sort
Next, let's implement the Merge Sort algorithm. Below is the implementation code for Merge Sort.
function mergeSort(arr) {
if (arr.length <= 1) return arr;
const mid = Math.floor(arr.length / 2);
const left = mergeSort(arr.slice(0, mid));
const right = mergeSort(arr.slice(mid));
return merge(left, right);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result.push(left[i]);
i++;
} else {
result.push(right[j]);
j++;
}
}
return result.concat(left.slice(i)).concat(right.slice(j));
}
Step 5: Handling Input and Output
Now that we have completed the sorting functions, we will implement the part that handles input and outputs the result. In JavaScript,
we can use prompt to receive input, and
the result can be printed using console.log.
const N = parseInt(prompt("Enter the number of integers:"));
const nums = prompt("Enter the integers:").split(" ").map(Number);
const sorted = quickSort(nums); // or mergeSort(nums);
console.log(sorted.join(" "));
Conclusion
In this course, we solved the problem of sorting a given array of numbers using JavaScript.
We learned not only the implementation of sorting algorithms but also the characteristics and performance of each algorithm.
By directly implementing Quick Sort and Merge Sort, we were able to deepen our understanding of sorting algorithms.
In coding tests, various problems are presented aside from sorting problems, so I recommend practicing these algorithms in various ways.
Problem Solving and Practice
Solve the following problems for more practice!
- Remove duplicate numbers from the given array and then sort it
- Interval sorting: sort only within a given interval
- Problem of merging two sorted arrays