자바 정렬 알고리즘

[자바 정렬알고리즘]

객체들을 조작하기 위한 자료구조로 자바는 배열이나 Collection Framework 내의 여러클래스를 제공하고 있습니다.

Collection Framework는 크게 3가지 형태로 분류할 수 있는데 간단하게 살펴 보자면
- Map : key와 Value를 가지는 자료구조입니다. HashMap, Hashtable, TreeMap과 같은 클래스들을 자주 쓰죠.
- List : 순서가 있고 중복이 허용되는 자료구조입니다. ArrayList, LinkedList, Vector...
- Set : 중복을 허용하지 않습니다. HashSet, TreeSet...

이러한 자료구조 내에서 객체들을 컨트롤 할 때 정렬은 피할 수 없는 숙명이죠.

1. 정렬해야 하는데 정렬 알고리즘을 모르겠다. 누가 정렬 좀 안해주나?

버블소트는 간단하지만 퍼포먼스에 문제가 있고
일반적으로 가장 빠른 퀵소트는 구현하기가 까다롭습니다.
버블소트조차도 귀찮으신 분들을 위해 친절하게도 자바는 여러분에게 고성능(?)의 정렬기능을 제공하고 있습니다.
그러나 우리는 자바가 제공하는 정렬기능을 사용하기 위해서 한두가지는 해야 합니다. 공짜는 없는거죠.

먼저 정렬을 위한 두가지 인터페이스에 친숙해질 필요가 있습니다.

java.lang.Comparable
java.util.Comparator

두 인터페이스가 서로 다른 패키지에 속해 있다는 사실에 유의하시구요.

Comparable 인터페이스는 객체의 고유한 순서를 제공하기 위한 것이라고 보면 되는데요.
우리말로 '비교할 수 있는' 정도로 풀 수 있겠죠.
그 뜻대로 이 인터페이스를 구현한 클래스의 객체들은 배열이나 컬렉션 프레임웤에서
자신과 딴넘을 비교할 수 있기 때문에 정렬의 기본조건을 충족시키고 있습니다.
정렬의 기본조건(객체간의 대소비교, 선후비교)이 준비되어 있기 때문에 정렬은 java API에 맡기면 되는 겁니다.

아래의 소스에서 우리는 Customer 클래스를 만들고 Comparable 인터페이스를 구현했습니다.
Comparable 인터페이스를 구현했기 때문에 그 인터페이스에서 정의한 compareTo 메쏘드를 반드시 오버라이딩 해야하죠.
이 메쏘드가 바로 자신과 딴넘을 비교해서
자기자신이 딴넘보다 앞에 와야하면 -1을, 똑같으면 0을, 뒤에 와야하면 1을 리턴하게 됩니다.
Customer 클래스에서는 디폴트로 한글이름으로 정렬되도록 compareTo를 재정의 했습니다.

이렇게만 구현을 해 놓으면 Customer로 이루어진 배열이 있다면
Arrays.sort(arr);

Customer로 이루어진 리스트(컬렉션프레임웤)가 있다면
Collections.sort(list);

를 호출하기만 하면 군말 없이 정렬해 줍니다.

자바API에서도 여러 클래스들이 이 Comparable을 구현하고 있는데요.

API문서를 참고하면

BigDecimal, BigInteger, Byte, ByteBuffer, Character, CharBuffer, Charset, CollationKey, Date, Double, DoubleBuffer, File, Float, FloatBuffer, IntBuffer, Integer, Long, LongBuffer, ObjectStreamField, Short, ShortBuffer, String, URI

등의 클래스들이 있습니다.

이러한 클래스들의 자료를 다룰때는 위의 sort 메쏘드를 자연스럽게 불러주면 되겠죠?

자바가 내부적으로 어떻게 정렬을 수행하는지 궁금하지 않으십니까?
그러면 SDK 설치 디렉토리 밑에 src.zip파일을 찾아 java.util.Arrays와 java.util.Collections의소스를 뜯어보십시오.
Collections의 sort(List)는 아규먼트로 들어온 list를 배열로 변환해서 다시 Arrays.sort(array)를 호출하며 Arrays.sort(array)는 합병정렬을 하고 있습니다

아마 합병정렬은 정렬성능도 우수하지만 정렬시간이 거의 일정하기 때문에 사용하는 것 같습니다.

(퀵소트는 최악의 경우 O(n^2) 의 시간이 걸릴수도 있습니다.)
단 메모리를 자기자신만큼, 그리고 절반씩 쪼개지는 크기들 만큼씩 더 사용한다는게 단점이죠.

우리는 Customer 클래스들이 배열로 되어 있건 리스트에 들어있건 한글이름으로는 정렬할 수는 있는데 그렇다면 나이순이라든지 영문이름순으로, 즉 다른 기준으로 정렬하고 싶을 땐 어떻게 할까요?

이럴때를 위해서 만들어 놓은 인터페이스가 Comparator입니다.
우리말로 '비교기', '비교측정기' 정도로 번역할 수 있는데 두 객체의 대소와 선후를 구현의도의 기준에 따라 판별해 줍니다.
이 인터페이스를 구현하는 클래스도 마찬가지로 compare 메쏘드를 구현해야 하는데요.
아규먼트로 들어오는 두개의 Object를 비교해서 역시 compareTo 와 같은 방식으로 리턴합니다.

그리고 아래처럼 사용하면 배열이나 리스트를 Comparator의 기준에 따라 정렬을 수행하게 됩니다.
Arrays.sort(arr, new YoungOrderComparator());
Collections.sort(list, new EngNameComparator());

2. sort()를 부르기도 귀찮다. 그냥 알아서 줄 좀 서 봐라.

자바는 친절하게도 위의 요구까지 들어주고 있는데
TreeMap이나, TreeSet이 그 기대에 부응하는 클래스들입니다. (Tree~가 붙어 있죠? ^^)
TreeMap은 key로 정렬을 하게 되고 TreeSet은 그 원소들을 정렬합니다.
위의 컨테이너 객체에 원소들을 넣는 족족 알아서 정렬됩니다. 코딩할 일이 없습니다.

리스트 같은 객체들을 인자로 받아서 TreeSet을 만들면 알아서 기본순서로(compareTo에 정의된 대로) 정렬됩니다.
Set set = new TreeSet(list);

정렬기준을 바꾸고 싶다면 Comparator를 구현한 객체를 생성자로 만든후 리스트를 집어넣어 줍니다.
Set set2 = new TreeSet(new YoungOrderComparator());
set2.addAll(list);

아래의 소스에 위에 언급한 사항을 간단하게 구현해 보았습니다.

자바의 컬렉션 프레임웤, 정렬기능 등을 차근차근 살펴보면 Interface, 다형성 등의 묘미를 만끽할 수 있죠.
이러한 객체지향적 언어로서의 매력은 이곳외에도 자바API의 여러부분에서 표현되어져 있습니다.
JAVA는 정말 아름다운 언어임에는 틀림없습니다.

import java.util.*;

public class A {
public static void main(String args[]) {
// 다섯명의 고객에 대한 배열 생성
Customer[] arr = new Customer[] {
new Customer("헤더 로클리어",1961, "Heather Deen Locklear"),
new Customer("데미 무어", 1962, "Demetria Gene Guynes"),
new Customer("안젤라 바셋", 1958, "Angela Bassett"),
new Customer("신디 크로퍼드", 1966, "Cintia Ann Crawford"),
new Customer("캐서린 제타 존스", 1969, "Catherine Jones")
};

printArray(arr, "Before Array sort Using Default sort");
// 배열을 정렬 (클래스에 정의된 기본정렬)
Arrays.sort(arr);
printArray(arr, "\nAfter Array sort Using Default sort");

// 배열을 어린 나이부터 정렬
Arrays.sort(arr, new YoungOrderComparator());
printArray(arr, "\nAfter Array sort Using YoungOrderComparator");

List list = Arrays.asList(arr); // 배열을 리스트로
Collections.shuffle(list); // 리스트의 순서를 마구 섞어 주세요.
printList(list, "\nBefore List sort Using Default sort");

// 리스트를 정렬 (클래스에 정의된 기본정렬)
Collections.sort(list);
printList(list, "\nAfter List sort Using Default sort");

// 리스트를 영문이름으로 정렬
Collections.sort(list, new EngNameComparator());
printList(list, "\nAfter List sort Using EngNameComparator");

// 디폴트 정렬할 수 있는 TreeSet을 만든다
Set set = new TreeSet(list);
System.out.println("\nAfter Making Set Using Default sort\n" + set);

// 어린 나이부터 정렬할 수 있는 TreeSet을 만든다
Set set2 = new TreeSet(new YoungOrderComparator());
set2.addAll(list);
System.out.println("\nAfter Making Set Using YoungOrderComparator\n" + set2);
}

static void printArray(Customer[] a , String title) {
System.out.println(title);
for (int i=0; i<a.length; i++)
System.out.println(a[i]);
}

static void printList(List l, String title) {
System.out.println(title);
for (int i=0; i<l.size(); i++)
System.out.println(l.get(i));
}

}

// 디폴트 소팅을 위해서 Comparable 인터페이스를 구현한다.
class Customer implements Comparable {
String name;
int birthYear;
String engName;

// Constructor
public Customer(String name, int birthYear, String engName) {
this.name = name;
this.birthYear = birthYear;
this.engName = engName;
}

// Object의 toString 메소드 overriding.. 객체의 문자적 표현
public String toString() {
return name + "(" + engName + ") " + birthYear + "년생";
}

// Comparable 인터페이스를 구현한 클래스에서 반드시 overriding 해야만 하는 비교 메쏘드
public int compareTo(Object o) {
// String의 compareTo 메소드를 호출(사전순서적( lexicographically)으로 비교)
return name.compareTo(((Customer)o).name);
}
}

// 젊은 순서대로 정렬하기 위해 Comparator 인터페이스를 구현
class YoungOrderComparator implements Comparator {
public int compare(Object o1, Object o2) {
int by1 = ((Customer)o1).birthYear;
int by2 = ((Customer)o2).birthYear;
return by1 > by2 ? -1 : (by1 == by2 ? 0 : 1); // descending 정렬.....
}
}

// 영문이름으로 정렬하기 위해 Comparator 인터페이스를 구현
class EngNameComparator implements Comparator {
public int compare(Object o1, Object o2) {
String en1 = ((Customer)o1).engName;
String en2 = ((Customer)o2).engName;
return en1.compareTo(en2); // ascending 정렬
}
}

출처 : http://cafe.naver.com/crazyhackers.cafe?iframe_url=/ArticleRead.nhn%3Farticleid=4125&social=1