Java와 자료구조 - 배열 / 정렬

 

 

 

배열

 

sort() : 배열을 오름차순으로 정렬할 때 사용한다.

binarySearch() : 배열에서 지정한 값이 저장된 위치를 찾을 때 사용한다. (중복되는 값이 있을 경우 무작위)

 

이진 검색은 배열의 검색범위를 절반씩 줄여가며 검색하기 때문에 빠른 속도로 검색할 수 있다.

 

 

정렬

 

 

배열을 정렬할 때 Arrays.sort()메서드를 자주 사용했는데, 사실 Character클래스의 Comparable의 구현에 의해 정렬되고 있었다.

 

정렬에 필요한 인터페이스로 Comparator와 Comparable이 있다. 

같은 타입의 인스턴스끼리 서로 비교할 수 있는 클래스들에 대해서 (Integer, String...) Comparable인터페이스가 정의돼있고, 기본적으로는 오름차순으로 정렬을 수행한다.

 

 

public interface Comparator{
  int compare(Object o1, Object o2);
  boolean equals(Object obj);
}

public interface Comparable{
  public int compareTo(Object o);
}

 

 

여기서 compare메서드와 compareTo메서드는 두 객체를 비교하는 역할을 한다.

compare와 compareTo는 비교하는 두 객체가 같으면 0, 비교하는 값보다 작으면 음수를, 크면 양수를 반환하도록 작성해야 한다.

 

Comparator인터페이스에는 equals메서드도 정의되어있는데, 특정 경우에는 오버라이딩이 필요할 수도 있다는 걸 암시하며, 일반적인 경우에는 compare메서드만 구현하면 된다.

 

위에서도 언급했듯, Comparable인터페이스는 기본적으로 오름차순으로 정렬을 수행한다. 내림차순이나 다른 기준으로 정렬하고 싶다면 Comparator를 구현해야 한다.

 

 

import java.util.*;
import java.io.*;

public class Main{
  public static void main(String[] args) throws IOException {    

      String[] arr = {"aaaa","bbbb","cccc","dddd"};
      
      Arrays.sort(arr, new Descending());

      for(int i=0; i<arr.length; i++){
        System.out.print(arr[i] + " ");
      }
  }
}

class Descending implements Comparator{
  public int compare(Object o1, Object o2){
    if(o1 instanceof Comparable && o2 instanceof Comparable){
      Comparable c1 = (Comparable)o1;
      Comparable c2 = (Comparable)o2;
      return c1.compareTo(c2) * -1;
    }
    return -1;
  }
}

 

dddd cccc bbbb aaaa로 출력된다. (-1을 곱해서 정렬 결과를 반대로 뒤집음)