Collections 클래스

Jan 04, 2024

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);
    }
}