[JAVA] List의 데이터 정렬과 검색

1. 기본 정렬: Collections.sort()

Collections.sort() 메서드는 List 데이터를 오름차순으로 정렬하는 간단한 방법을 제공합니다. 이 메서드는 내부적으로 Timsort 알고리즘을 사용하며, 정렬 대상 요소가 Comparable 인터페이스를 구현하고 있어야 합니다.

예제: 기본 정렬

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

public class Main {
    public static void main(String[] args) {
        ArrayList<String> fruits = new ArrayList<>();

        // 데이터 추가
        fruits.add("수박");
        fruits.add("사과");
        fruits.add("바나나");
        fruits.add("포도");

        // 정렬 전 출력
        System.out.println("정렬 전: " + fruits);

        // 기본 정렬
        Collections.sort(fruits);

        // 정렬 후 출력
        System.out.println("정렬 후: " + fruits);
    }
}

출력 결과

정렬 전: [수박, 사과, 바나나, 포도]
정렬 후: [바나나, 사과, 수박, 포도]

Tip: 기본 정렬은 문자열, 숫자 등 자연 순서를 따릅니다. 사용자 정의 정렬이 필요하면 Comparator나 Comparable을 사용합니다.

2. 사용자 정의 정렬: Comparator와 Comparable

Comparable 인터페이스

Comparable은 자연스러운 순서를 정의합니다. 해당 객체의 compareTo 메서드를 구현하여 정렬 방식을 설정할 수 있습니다.

예제: Comparable 구현

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

class Product implements Comparable<Product> {
    String name;
    int price;

    public Product(String name, int price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public int compareTo(Product other) {
        return this.price - other.price; // 가격 기준 오름차순 정렬
    }

    @Override
    public String toString() {
        return name + "(" + price + "원)";
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Product> products = new ArrayList<>();
        products.add(new Product("사과", 1000));
        products.add(new Product("바나나", 500));
        products.add(new Product("포도", 1500));

        System.out.println("정렬 전: " + products);

        Collections.sort(products);

        System.out.println("정렬 후: " + products);
    }
}

출력 결과

정렬 전: [사과(1000원), 바나나(500원), 포도(1500원)]
정렬 후: [바나나(500원), 사과(1000원), 포도(1500원)]

반응형

Comparator 인터페이스

Comparator는 별도의 클래스를 정의하여 정렬 로직을 분리합니다. 주로 여러 기준으로 정렬이 필요할 때 사용됩니다.

예제: Comparator 구현

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

class Product {
    String name;
    int price;

    public Product(String name, int price) {
        this.name = name;
        this.price = price;
    }

    @Override
    public String toString() {
        return name + "(" + price + "원)";
    }
}

class NameComparator implements Comparator<Product> {
    @Override
    public int compare(Product p1, Product p2) {
        return p1.name.compareTo(p2.name); // 이름 기준 정렬
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayList<Product> products = new ArrayList<>();
        products.add(new Product("사과", 1000));
        products.add(new Product("바나나", 500));
        products.add(new Product("포도", 1500));

        System.out.println("정렬 전: " + products);

        Collections.sort(products, new NameComparator());

        System.out.println("정렬 후(이름 기준): " + products);
    }
}

출력 결과

정렬 전: [사과(1000원), 바나나(500원), 포도(1500원)]
정렬 후(이름 기준): [바나나(500원), 사과(1000원), 포도(1500원)]

3. 이진 검색: Collections.binarySearch()

Collections.binarySearch() 메서드는 정렬된 리스트에서 효율적으로 요소를 검색합니다. 시간 복잡도는 **O(log n)**으로 매우 빠릅니다.

사용 조건

• 검색 전에 반드시 **Collections.sort()**를 호출해 정렬해야 합니다.
• 데이터가 정렬되지 않으면 결과가 올바르지 않을 수 있습니다.

예제: 이진 검색

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

public class Main {
    public static void main(String[] args) {
        ArrayList<String> fruits = new ArrayList<>();
        fruits.add("사과");
        fruits.add("바나나");
        fruits.add("포도");
        fruits.add("수박");

        // 정렬
        Collections.sort(fruits);

        // 이진 검색
        int index = Collections.binarySearch(fruits, "포도");

        if (index >= 0) {
            System.out.println("포도를 찾았습니다. 인덱스: " + index);
        } else {
            System.out.println("포도를 찾을 수 없습니다.");
        }
    }
}

출력 결과

 

포도를 찾았습니다. 인덱스: 2

Tip: 데이터가 많을수록 이진 검색의 장점이 더 두드러집니다.

참고 사이트

Java 공식 문서: https://docs.oracle.com/javase/8/docs/api/java/util/Collections.html