Search
Duplicate

[JAVA] Sort 사용 (Arrays, Collections)

간단소개
Java 의 자료구조에서 사용하는 Sort 의 구조에 대해 알아봅시다
팔만코딩경 컨트리뷰터
ContributorNotionAccount
주제 / 분류
Java
Algorithm
태그
Java
algorithm
Scrap
8 more properties

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 에 대해서 더 자세히 알아보고,
연결하여 완성하도록 하겠습니다.