▶ Collections 클래스
- Collections 클래스는 여러 유용한 알고리즘을 구현한 메소드들을 제공한다.
- 이 메소드들은 제네릭 기술을 사용하여 작성되었으며 정적 메소드의 형태로 되어있다.
- 자주 사용되는 알고리즘으로는 정렬(Sorting), 섞기(Shuffling), 탐색(Searching) 등이 있다.
언급한 세 메소드의 첫 번째 매개변수는 알고리즘이 적용되는 컬렉션이다.
▶ 정렬(Sorting)
- 데이터를 어떤 기준에 의하여 순서대로 나열하는 알고리즘이다.
- 퀵 정렬, 합병 정렬, 히프 정렬 등의 다양한 방법이 존재한다.
- Collections 클래스의 정렬은 속도가 비교적 빠르고 안전성이 보장되는 합병 정렬을 이용한다.
- 안전성이란 동일한 값을 가지는 원소를 다시 정렬하지 않는 것을 의미한다.
- 안전성은 같은 리스트를 반복하여 다른 기준에 따라 정렬할 때 중요하다.
예를 들어 상품 주문 리스트를 날짜를 기준으로 먼저 정렬하고 이후 주문처를 기준으로 정렬한다면 사용자는 같은 주문처가 보낸 주문은 날짜별로 정렬될 것이라고 가정한다. 이처럼 한번 정렬된 것이 유지되는 경우를 안정성 있는 정렬이라고 말한다.
- Collection 클래스의 sort() 메소드는 정적메소드로, List 인터페이스를 구현하는 컬렉션에 대하여 정렬을 수행한다.
List<String> list = new LinkedList<String>();
list.add(“김철수”);
list.add(“김영희”);
Collections.sort(list);
위의 경우는 원소가 String 타입이므로 알파벳 순서대로 정렬될 것이다. 원소가 Date 타입이라면 시간적인 순서로 정렬될 것이다. 그 이유는 String 클래스와 Date 클래스 모두 Comparable 인터페이스를 구현하기 때문이다.
- 정렬은 Comparable 인터페이스를 이용하여 이루어진다. List 인터페이스는 Comparable 인터페이스를 상속하므로
public interface Comparable<T> {
public int comparaTo(T o);
}
comparaTo() 메소드는 매개변수 객체를 현재의 객체와 비교하여 작으면 음수, 같으면 0, 크면 양수를 반환한다.
- 예제 1
import java.util.*;
public class SortTest1 {
public static void main(String[] args) {
String[] example = { "Nice", "to", "meet", "you" };
List<String> list = Arrays.asList(example); //배열을 리스트로 무조건 변환!
Collections.sort(list); //리스트 정렬
System.out.println(list);
}
}
[예제 1 출력 결과]
meet과 to의 위치가 바뀐 것을 볼 수 있다. 알파벳순이기 때문에 이러한 결과가 나온 것이다.
- 예제 2
import java.util.*;
class Student implements Comparable<Student> {
int number;
String name;
Student(int number, String name) {
this.number = number;
this.name = name;
}
public String toString() {
return name;
}
@Override
public int compareTo(Student s) {
return number - s.number; //학번순서로 정렬한다.
}
}
public class SortTest2 {
public static void main(String[] args) {
Student[] students = {
new Student(02, "선옥자"),
new Student(03, "한영희"),
new Student(01, "김철수")
};
List<Student> list = Arrays.asList(students);
Collections.sort(list);
System.out.println(list);
}
}
[예제 2 출력 결과]
- 예제 3 : 역순으로 정렬하기 - Collections.sort(list, Collections.reverseOrder());
import java.util.*;
public class SortTest {
public static void main(String[] args) {
String[] example = { "Nice", "to", "meet", "you" };
List<String> list = Arrays.asList(example); //배열을 리스트로 무조건 변환!
Collections.sort(list, Collections.reverseOrder()); //리스트 역순정렬
System.out.println(list);
}
}
[예제 3 출력 결과]
역순정렬로 인해 예제 1의 출력 결과와 반대되는 결과를 볼 수 있다.
▶ 섞기(Shuffling)
- 리스트에 존재하는 정렬을 파괴하여서 원소들의 순서를 랜덤하게 만든다.
- 정렬과는 반대 동작을 한다.
- 주로 게임을 구현할 때 유용하게 쓰인다. 예를 들어 카드 게임에서 카드를 섞을 때 사용할 수 있다.
- 예제
import java.util.*;
public class Shuffle {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
for(int i = 0; i <= 10; i++) {
list.add(i);
}
Collections.shuffle(list);
System.out.println(list);
}
}
[출력 결과 1]
[출력 결과 2]
메소드를 실행할 때마다 서로 다른 출력 결과를 보인다.
▶ 탐색(Searching)
- 리스트 안에서 원하는 원소를 찾는 알고리즘이다.
- 선형 탐색 : 처음부터 모든 원소를 방문하는 탐색 방법으로, 리스트가 정렬되어 있지 않은 경우 사용한다.
- 이진 탐색 : 리스트가 정렬되어 있는 경우 중간에 있는 원소(m)와 먼저 비교하여, 크면 그다음부(m+1)터 끝까지 비교하고, 작으면 처음부터 그 전(m-1)까지의 원소들과 비교하는 방식을 반복하여 하나의 리스트를 계속해서 두 개의 리스트로 분할한다. 이 방법은 리스트에 하나의 원소가 남을 때까지 반복된다. 이진 탐색은 문제의 크기를 반으로 줄일 수 있기 때문에 선형 탐색보다 효율적이다.
- Collections 클래스는 정렬된 리스트에서 지정된 원소를 이진 탐색한다.
- 이진 탐색 메소드인 binarySearch()는 만약 반환값이 양수이면 찾고자 하는 원소의 인덱스값이고, 음수이면 탐색이 실패한 것이다. 즉, 원소를 찾지 못했음을 의미한다.
int index = Collections.binarySearch(list, element);
// list는 리스트, element는 탐색할 원소이다.
단, binarySearch() 메소드는 실패하더라도 도움이 되는 정보를 반환한다. 즉, 반환값에는 현재의 데이터가 삽입될 수 있는 위치 정보가 있다. 반환값이 pos라고 한다면, (-pos-1)이 해당 데이터를 삽입할 수 있는 위치이다.
int pos = Collections.binarySearch(list, key);
if(pos < 0) list.add(-pos-1);
- binarySearch() 메소드는 위에도 언급했듯이 “정렬된 리스트”에 한해서 탐색을 진행한다는 점에 주의하여야 한다.
'Programming Language > JAVA' 카테고리의 다른 글
| 43. Thread - 스레드 (8) | 2017.07.24 |
|---|---|
| 41. Map, HashMap, TreeMap, LinkedHashMap (0) | 2017.07.24 |
| 40. Queue - 큐, FIFO, 우선순위 큐 (0) | 2017.07.24 |
| 39. Set, HashSet, TreeSet, LinkedHashSet - 집합 (0) | 2017.07.24 |
| 38. List interface, ArrayList, LinkedList, Vector - 리스트 인터페이스 (0) | 2017.07.23 |
