요즘 매일 코딩테스트 입문 문제를 쭈욱 풀어나가고 있는데, 풀면서 기초가 정말 중요하다고 느낀다.
머리로는 이거 이렇게 해야지~ 라고 생각이 드는데 막상 키보드 앞에 서면 '그거 어떻게 하더라..?' 한다.
블로그도 열심히 써보기로 했으니 블로그에 정리하면서 다시 한번 상기 시켜야겠다.
1. 💡 Arrays.sort()
자바에서는 배열을 정렬할 때 java.util.Arrays 클래스에 포함 된 정렬 알고리즘 sort()를 메서드로 제공 한다.
sort() 메서드를 사용하면 정렬을 간단하게 구현할 수 있다.
1-1. 기본형(Primitive Type) 배열 정렬
Arrays.sort() 는 기본 오름차순으로 정렬한다.
오름차순 정렬
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
int[] numbers = {5, 2, 9, 1, 5, 6};
Arrays.sort(numbers);
System.out.println(Arrays.toString(numbers)); // [1, 2, 5, 5, 6, 9]
}
}기본형 배열은 Arrays.sort()로 간단하게 오름차순 정렬할 수 있다.
Arrays.sort() 자체는 기본적으로 오름차순 정렬만 지원하지만, 내림차순 정렬도 구현할 수 있다.
내림차순 정렬
예) 기본형 int배열은 Arrays.sort()와 함께 Integer클래스를 활용하면 된다.
import java.util.Arrays;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Integer[] numbers = {5, 2, 9, 1, 5, 6}; // int[] 대신 Integer[]
Arrays.sort(numbers, Collections.reverseOrder());
System.out.println(Arrays.toString(numbers)); // [9, 6, 5, 5, 2, 1]
}
}기본형 배열은 Collections.reverseOrder()를 사용할 수 없기 때문에 Integer[]로 사용했다.
1-2. 객체(Reference Type) 배열 정렬
객체 배열은 참조형 데이터 타입인 객체의 주소를 저장하는 배열이다.
기본형 배열 정렬과 마찬가지로 Arrays.sort()를 사용하여 정렬할 수 있지만,
객체는 Comparable 인터페이스를 구현해야 한다.
Arrays.sort() 메서드를 사용해 객체 배열을 정렬하려면, 정렬의 기준을 Java가 알아야 한다.
이 기준을 제공하기 위해 객체 클래스에서 Comparable인터페이스를 구현해야 한다.
나이를 기준으로 오름차순 정렬 하기
import java.util.Arrays;
class Person implements Comparable<Person> {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public int compareTo(Person other) {
return this.age - other.age; // 나이 기준 오름차순
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
public class Main {
public static void main(String[] args) {
Person[] people = {
new Person("Alice", 30),
new Person("Bob", 25),
new Person("Charlie", 35)
};
Arrays.sort(people);
System.out.println(Arrays.toString(people)); // [Bob(25), Alice(30), Charlie(35)]
}
}자바의 Comparable 인터페이스는 compareTo() 메서드를 통해 객체 간의 순서를 비교할 수 있도록 해준다.
Person클래스에 나이를 기준으로 정렬한다고 했을 때,
this.age - other.age는 오름차순을 의미한다.
결과가 음수면 this가 other보다 앞에 온다는 의미이고,
결과가 양수이면 this가 other보다 뒤에 온다는 의미이다.
나이를 기준으로 내림차순 정렬하기
객체 배열 또한 내림차순으로 정렬이 가능한데,
객체 배열은 Comparator을 사용해서 내림차순으로 정렬할 수 있다.
Arrays.sort(배열, Comparator);두번 째 인자인 Comparator는 정렬 기준을 제공하는 함수이다.
import java.util.Arrays;
class Person {
String name;
int age;
public Person(String name, int age) {
this.name = name;
this.age = age;
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
public class Main {
public static void main(String[] args) {
Person[] people = {
new Person("Alice", 30),
new Person("Bob", 25),
new Person("Charlie", 35)
};
// 나이 기준 내림차순 정렬
Arrays.sort(people, (p1, p2) -> p2.age - p1.age);
System.out.println(Arrays.toString(people)); // [Charlie(35), Alice(30), Bob(25)]
}
}람다식을 사용해서 객체 배열을 내림차순 정렬 했다.
Comparator를 간단하게 람다식으로 표현한 것인데,
p1과 p2는 Person객체를 의미하고, p2.age - p1.age는 나이 기준 내림차순 정렬을 뜻한다.
Arrays.sort()는 람다식을 기준으로 people배열을 정렬한다.
p2.age - p1.age 덕분에 나이가 많은 순서로 정렬 된다.
💡 2. Stream API 정렬 구현
Stream API는 Java8에서 도입된 기능으로 Collection(List, Set)이나 배열 같은 데이터 소스를 처리하고 변환하는데 사용된다.
Stream API를 사용했을때 장점은 코드가 간결해지고, 데이터 변경 없이 새로운 결과를 사용할 수 있다.
2-1. 이름을 기준으로 오름차순 정렬
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
String[] names = {"Charlie", "Alice", "Bob"};
String[] sortedNames = Arrays.stream(names)
.sorted()
.toArray(String[]::new);
System.out.println(Arrays.toString(sortedNames)); // [Alice, Bob, Charlie]
}
}sorted()를 사용하면 오름차순으로 정렬한다.
2-2. 이름을 기준으로 내림차순 정렬
import java.util.Arrays;
import java.util.Comparator;
public class Main {
public static void main(String[] args) {
String[] names = {"Charlie", "Alice", "Bob"};
String[] sortedNames = Arrays.stream(names)
.sorted(Comparator.reverseOrder())
.toArray(String[]::new);
System.out.println(Arrays.toString(sortedNames)); // [Charlie, Bob, Alice]
}
}Comparator.reverseOrder()를 사용하여 내림차순 정렬도 가능하다.
하지만 Comparator.reverseOrder()는 객체 타입에서만 사용할 수 있기 때문에
기본형 배열에서는 사용할 수 없다.
💡 3. 정렬 알고리즘 직접 구현
사실 알고리즘 공부할 때는 직접 구현해보는 것이 제일 좋다고 생각한다.
1. 버블 정렬(Bubble Sort)
버블 정렬(Bubble Sort)은 인접한 두 요소를 비교해 교환하면서 정렬하는 단순한 정렬 알고리즘이다.
이름처럼 배열의 요소가 거품처럼 뽀글뽀글 위로 올라오듯이
가장 큰 값이 반복적으로 배열의 끝으로 이동하며 정렬 된다.
public class Main {
public static void main(String[] args) {
int[] numbers = {5, 2, 9, 1, 5, 6};
bubbleSort(numbers);
System.out.println(Arrays.toString(numbers)); // [1, 2, 5, 5, 6, 9]
}
public static void bubbleSort(int[] array) {
int n = array.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - 1 - i; j++) {
if (array[j] > array[j + 1]) {
// Swap
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
}버블정렬 동작 방식
- 배열의 처음부터 끝까지 인접한 두 요소를 비교한다.
- 만약 두 요소의 순서가 맞지 않으면 두 요소의 위치를 교환(swap) 한다.
- 위 과정을 배열 크기만큼 반복한다.
- 각 반복(iteration)마다 큰 값이 맨 뒤로 정렬되므로, 다음 반복에서는 마지막 요소를 제외하고 작업한다.
버블 정렬은 구현이 쉽지만 데이터가 클 경우 성능이 좋지 않기 때문에 실무에서는 퀵정렬(Quick Sort)나 병합 정렬(Merge Sort)같은 더 효율적인 알고리즘을 사용하는 것이 일반적이다.
