Contents
1. 정렬(Sorting) : 가장 중요한 컴퓨터 알고리즘여러 유용한 알고리즘을 구현한 메서드 들을 제공해줌
Collections 클래스가 제공해주는 메서드 : 제네릭 사용
정적 메소드
첫 번째 매개 변수 : 알고리즘이 적용되는 컬렉션이 됨
중요한 알고리즘
1. 정렬(Sorting) : 가장 중요한 컴퓨터 알고리즘
데이터를 어떤 기준에 의하여 순서대로 나열하는 것
종류 : 퀵 정렬, 합병 정렬, 히프 정렬 등
합병 정렬 : Collections 클래스의 정렬에서 사용됨
속도가 비교적 빠르고 안정성이 보장됨
시간 복잡도가 O(nlog(n))
거의 정렬된 리스트에 대해서는 상당히 빠름
sort() : List 인터페이스를 구현하는 컬렉션에 대한 정렬을 수행
List<String> list = new LinkedList<String>();
list.add("김철수");
list.add("김영희");
Collections.sort(list); // 리스트 안의 문자열 정렬String 타입 > 알파벳 순서
Date 타입 > 시간 순서
가능한 이유 : Comparable 인터페이스 사용
문자열 정렬하기
package ex13;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public class SortTest {
public static void main(String[] args) {
String[] sample = {"i", "walk", "the", "line"};
List<String> list = Arrays.asList(sample);
Collections.sort(list);
System.out.println(list);
}
}
사용자 클래스의 객체 정렬하기
package ex13;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
class Student implements Comparable<Student> {
int number;
String name;
public Student(int number, String name) {
this.number = number;
this.name = name;
}
public String toString() {
return name;
}
public int compareTo(Student s) {
return s.number - number;
}
}
public class SortTest1 {
public static void main(String[] args) {
Student array[] = {
new Student(2, "김철수"),
new Student(3, "이철수"),
new Student(4, "박철수"),
};
List<Student> list = Arrays.asList(array);
Collections.sort(list); // 순서대로
System.out.println(list);
Collections.sort(list, Collections.reverseOrder()); // 역순으로
System.out.println(list);
}
}
CompareTo() : 매개 변수 객체를 현재의 객체와 비교
> 작으면 음수 반환
> 같으면 0 반환
> 크면 양수 반환
2. 섞기(Shuffling) : 정렬의 반대 동작을 함
리스트에 존재하는 정렬을 파괴하여서 원소들의 순서를 랜덤하게 만듦
게임을 구현할 때, 테스트할 때 용이 함
package ex13;
import java.util.AbstractList;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Shuffle {
public static void main(String[] args) {
List<Integer> list = new ArrayList<Integer>();
for (int i = 1; i <= 10; i++) {
list.add(i);
}
Collections.shuffle(list);
System.out.println(list);
}
}
3. 탐색(Searching)
리스트 안에서 원하는 원소를 찾는 것
선형 탐색 : 정렬되어있지 않아 모든 원소를 다 탐색
이진 탐색 : 정렬되어있어 중간에 있는 원소와 먼저 비교해서 탐색
binarySearch 알고리즘 : 정렬된 리스트에서 지정된 원소를 이진탐색한 것
index = Collections.binarySearch (collec. element);
반환값이 양수 > 탐색이 성공한 객체 위치
음수 > 탐색 실패, 도움이 되는 정보가 반환
숫자들의 리스트 탐색하기
package ex13;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class Search1 {
public static void main(String[] args) {
int key = 50;
List<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < 100; i++) {
list.add(i);
}
int index = Collections.binarySearch(list, key);
System.out.println("탐색의 반환값 =" + index);
}
}
Share article
