Java’s Sort
JAVA 를 통해 알고리즘 문제를 풀다보면, 배열을 정렬할 일이 있습니다.
이 때 보통 Arrays.sort() 혹은 Collections.sort() 메소드를 통해 배열 혹은 리스트에 대한 정렬을 합니다.
자바에서는 배열을 정렬할때, 사용하는 정렬 알고리즘을 메서드로 제공합니다.
배열 혹은 리스트로 구성된 원소들을 특정한 규칙에따라, 오름차순 혹은 내림차순으로 정렬을 할 수 있으며, 기본값으로 오름차순 정렬을 합니다.
Sorting Example Code
import java.util.Arrays;
import java.util.Collections;
public class Main{
public static void main(String[] args) {
int[] intArr = {8,7,6,5,4};
for(int i: intArr)
System.out.print(i + " ");
System.out.println();
//8 7 6 5 4
Arrays.sort(intArr);
for (int i : intArr)
System.out.print(i + " ");
System.out.println();
//4 5 6 7 8
// String
String[] strArr = {"d", "c", "b", "a"};
for(String s: strArr)
System.out.print(s + " ");
System.out.println();
// d c b a
Arrays.sort(strArr);
for (String s : strArr)
System.out.print(s + " ");
System.out.println();
// a b c d
Arrays.sort(strArr, Collections.reverseOrder());
for (String s : strArr)
System.out.print(s + " ");
// d c b a
}
}
Java
복사
Arrays.sort(배열);
•
오름차순으로 정렬하고 싶은 배열을 전달인자로 주면 전달인자로 받은 배열이 정렬됩니다.
•
문자열의 경우 아스키코드 순 (알파벳 순)으로 오름차순 정렬되며, 한글도 가나다 순으로 정렬됩니다.
내부 구조
Sort( Array )
•
java.util.Arrays 클래스에 static 메서드로 선언되어 있습니다.
•
int, long, short, double 등 JAVA의 Primitive (기본) 타입들에 대한 정렬을 지원합니다.
•
Reference (참조) 타입 의 배열의 정렬도 지원합니다.
Sort(Array, Comparator)
오름차순 정렬이 아닌, 임의의 정렬기준을 적용하려면 아래의 Comparator 를 구현한 클래스를 전달인자로 주어, 원하는 방식대로 정렬할 수 있습니다.
import java.util.Arrays;
import java.util.Collections;
public class Main{
public static void main(String[] args) {
int[] intArr = {8,7,6,5,4};
for(int i: intArr)
System.out.print(i + " ");
System.out.println();
//8 7 6 5 4
Arrays.sort(intArr); // 오름차순 정렬
for (int i : intArr)
System.out.print(i + " ");
System.out.println();
//4 5 6 7 8
Arrays.sort(intArr, Collections.reverseOrder()); // 내림차순 정렬
for (int i : intArr)
System.out.print(i + " ");
// 8 7 6 5 4
}
}
Java
복사
Arrays.sort(intArr, Collections.reverseOrder())
다음과 같이 sort 의 두번째 인자로 Comparator 의 구현체를 주면, 오름차순이 아니라 원하는 방식대로 정렬이 가능합니다.
위의 예제코드에서는 reverseOrder() 메서드를 통해 내림차순 정렬을 하였습니다.
Comparerator?
Sort의 두번째 인자로 준 Comparator 는 무엇일까요?
Comparator 는 정렬을 하기위한 여러가지 명세를 제공하는 인터페이스입니다.
1.
사용자는 이 인터페이스를 명세대로 직접 구현한 클래스를 만들 수 있습니다.
2.
이미 구현되어있는 구현체를 사용할 수 있습니다.
Arrays.sort(intArr, Collections.reverseOrder())
위의 내림차순으로 intArr 을 정렬하는 코드가 대표적인 2번의 예시입니다.
Collections.reverseOrder() 클래스의 리턴값을 전달인자로 주었습니다.
⇒ Collections 클래스의 reverseOrder() 메서드는 내부적으로 Comparator 인터페이스를 구현한 구현체를 리턴합니다.
//Collections.java
...
@SuppressWarnings("unchecked")
public static <T> Comparator<T> reverseOrder() {
return (Comparator<T>) ReverseComparator.REVERSE_ORDER;
}
Java
복사
⇒reverseOrder() 메소드는 내부적으로 Comparator 를 구현한 클래스를 리턴하며 ReverseComparator 라고 하는 Collections 의 내부 static 클래스로, 내림차순 정렬을 하도록 구현되어 있습니다.
Collections 클래스에 대한 자세한 내용은 아래 문서를 참고해주세요.
정리
1.
java 배열의 정렬은 Array.sort 를 통해 사용하며 java.util패키지에 있습니다.
2.
Sort ( 배열 ) 메서드를 를 통해, 기본값으로 오름차순 정렬을 할 수 있습니다.,
3.
Sort ( 배열 , Comparator ) 메서드를 를 통해서 원하는 방식대로 정렬을 할 수 있습니다.
Collections.sort
Collections.sort 는 2개의 메소드가 존재합니다.
T 타입의 List 객체를 전달인자로 받는 첫번째 sort는 T 타입의 클래스에서 Comparable 을 구현하고 있어야 사용이 가능합니다.
Comparable 은 Arrays.sort에서 Comparator 처럼 어떤 객체에대한 정렬하는 룰을 명시하는 인터페이스 로, compareTo(T o) 함수를 구현해야 합니다.
public interface Comparable<T> {
public int compareTo(T o);
}
Java
복사
Collections.sort Example
public class ArraysTest {
public static void main(String[] args) {
Integer[] intArr = {9,8,7,6,5};
//int 배열을 List 타입으로 변환
List<Integer> intList = Arrays.asList(intArr);
for(int i : intList)
System.out.print(i + " ");// 9 8 7 6 5
System.out.println();
Collections.sort(intList); // 5 6 7 8 9
for(int i : intList)
System.out.print(i + " ");
}
Java
복사
전체적인 구조는 위에서 살펴본 Arrays.sort() 와 비슷하며,
만약 List<MyClass> 와 같은 형태라면,
MyClass 안에서 Comparable 을 구현하거나,
//Collections.java
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
Java
복사
위 오버로딩된 sort 메소드의 두번째 전달인자로
Comparable 을 구현한 클래스를 전달하여 사용할 수 있습니다.
List<Integer> 는 Collections.sort(intList)
sort(리스트)를 받는 전달인자를 사용하며,
Integer class 는 Comparable 을 다음과 같이 구현하고 있습니다.
//Integer.java
public final class Integer extends Number implements Comparable<Integer> {
...
/**
* Compares two {@code Integer} objects numerically.
*
* @param anotherInteger the {@code Integer} to be compared.
* @return the value {@code 0} if this {@code Integer} is
* equal to the argument {@code Integer}; a value less than
* {@code 0} if this {@code Integer} is numerically less
* than the argument {@code Integer}; and a value greater
* than {@code 0} if this {@code Integer} is numerically
* greater than the argument {@code Integer} (signed
* comparison).
* @since 1.2
*/
public int compareTo(Integer anotherInteger) {
return compare(this.value, anotherInteger.value);
}
/**
* Compares two {@code int} values numerically.
* The value returned is identical to what would be returned by:
* <pre>
* Integer.valueOf(x).compareTo(Integer.valueOf(y))
* </pre>
*
* @param x the first {@code int} to compare
* @param y the second {@code int} to compare
* @return the value {@code 0} if {@code x == y};
* a value less than {@code 0} if {@code x < y}; and
* a value greater than {@code 0} if {@code x > y}
* @since 1.7
*/
public static int compare(int x, int y) {
return (x < y) ? -1 : ((x == y) ? 0 : 1);
}
....
}
Java
복사
그래서 Arrays.sort 와 Collections.sort
Collections.Sort() 는 결국 내부적으로 list.sort() 함수를 호출하고, list.sort 함수는 List.java sort(Comparator ) 메소드를 호출합니다.
// List.java
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
Java
복사
List.java 의 sort 메소드 안에서는 결국 Arrays,sort(a, Comparator) 함수를 호출하는것을 볼 수 있습니다.
Collections.sort() 는 List 객체를 Object 배열로 변환하여 Arrays.sort() 를 실행한다.
⇒ 따라서 근본적으로는 차이가 없습니다.
정리
•
JAVA 에서는 정렬을 수행할때 java.util 패키지의, Arrays.sort() 메소드를 사용한다
•
Primitive (기본형 int, double, short …) 타입 의 배열일 경우, Arrays.sort() 를 직접 사용
◦
DualPivotQuicksort
▪
최적 : O(NlogN)
▪
평균 : O(NlogN)
▪
최악 : O(N^2)
•
Reference (참조형)타입 의리스트일 경우 Collections, 를 통해 Arrays.sort()를 호출합니다.
◦
Timsort
▪
최적 : O(N)
▪
평균 : O(NlogN)
▪
최악 : O(NlogN)
다음번엔 primitive 타입 일때 사용하는 DualPivotQuickSort와
Reference 타입일때 사용 하는 Timsort 에 대해서 더 자세히 알아보고,
연결하여 완성하도록 하겠습니다.
