[JAVA] 65. Collections' Methods

1. 정렬 (Sorting)

• sort() : List 내에서 정렬을 수행
• Timsort 알고리즘 사용
• Merge Sort + Insertion Sort
• O(nlog(n)), 정렬이 어느 정도 되어 있다면 더욱 빠름

package ex18;

import java.util.ArrayList;
import java.util.*;

public class Sort {
    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 ex18;

import java.util.*;

// comparable : 비교하여 작으면 음수, 같으면 0, 크면 양수 반환
class Student implements Comparable<Student> {
    int number;
    String name;

    public Student(int number, String name) {
        this.number = number;
        this.name = name;
    }

    @Override
    public String toString() {
        return name;
    }

    public int compareTo(Student s) {
        return s.number - number;
    }
}

public class SortTest {
    public static void main(String[] args) {
        Student[] array = {
                new Student(2, "김철수"),
                new Student(3, "이철수"),
                new Student(1, "박철수"),
        };
        List<Student> list = Arrays.asList(array);
        Collections.sort(list);
        System.out.println(list);
    }
}

2. 섞기 (Shuffling)

• 정렬의 반대 동작

• 게임을 구현하는 데 유용
• 카드 게임에서 카드를 랜덤하게 섞는 데에 사용

package ex18;

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

        // 0 ~ 9까지 ArrayList에 추가
        for (int i = 0; i < 10; i++) {
            list.add(i);
        }

        // 무작위로 셔플 후 출력
        Collections.shuffle(list);
        System.out.println(list);
    }
}

3. 탐색 (Searching)

• 리스트 내에서 원하는 원소를 찾는 것
• 정렬되어 있지 않다면 모든 원소를 방문 (선형 탐색)
• 정렬되어 있다면 중간에 있는 원소와 비교 (이진 탐색)

• binarySearch() : 정렬된 리스트에서 지정된 원소를 이진 탐색
• 탐색이 성공하면 양수 값 반환, 실패하면 음수 값 반환
• 이 양수 값을 get()하면 객체를 얻을 수 있음
• 음수 값일 경우 (-pos -1)이 원소를 삽입 가능한 위치

package ex18;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Search {
    public static void main(String[] args) {
        int key = 50;
        List<Integer> list = new ArrayList<Integer>();

        // 0 ~ 99까지 원소 추가
        for (int i = 0; i < 100; i++) {
            list.add(i);
        }

        // 원소가 저장된 곳을 찾음 : 50이 저장되어 있는 곳을 index로 반환
        int index = Collections.binarySearch(list, key);
        System.out.println("탐색의 반환 값 : " + index);
    }
}

• index = 50 >> 51번째 자리에 50이 위치