티스토리 뷰

부경대 IT융합응용공학과 권오흠 교수님의 영리한 프로그래밍을 위한 알고리즘 강좌와 '쉽게 배우는 알고리즘: 관계중심의 사고법 - 문병로'등을 통한 알고리즘 학습 강좌 링크

3-9. Sorting in Java

  • 일반적으로 정렬은 가장 기본적인 알고리즘이기 때문에, 대부분의 프로그래밍 언어가 표준 라이브러리의 일부로 정렬을 제공한다.

  • 따라서, 일반적인 상황에서 개발자가 직접 알고리즘을 구현할 경우는 많지 않다고 볼 수 있다.

  • Java에서의 sorting을 알아본다.

기본 타입 데이터의 정렬

  • Arrays 클래스가 primitive 타입 데이터를 위한 정렬 메소드를 제공한다.


int[] data = new int[capacity];

//data[0]에서 data[capacity-1]까지 데이터가 꽉 차있는 경우에는 다음과 같이 정렬한다.
Arrays.sort(data);

//배열이 꽉 차있지 않고 size개의 데이터만 있다면 다음과 같이 정렬한다.
Arrays.sort(data, 0, size);
  • int이외의 다른 primitive 타입 데이터(double, char 등)에 대해서도 제공

객체의 정렬: 문자열

  • java.util.Arrays;


String[] fruits = new String[]{"pineapple", "apple", "orange", "banana"};

Arrays.sort(fruits);
for(String name : fruits)
 System.out.println(name);

ArrayList 정렬: 문자열

  • java.util.Collections;


List<String> fruits = new ArrayList<>();
fruits.add("pineapple");
fruits.add("apple");
fruits.add("orange");
fruits.add("banana");

Collections.sort(fruits);
fruits.forEach(System.out::println);

객체의 정렬: 사용자 정의 객체

  • 정렬의 대상인 데이터들에 대해 객체들간의 크기 관계 비교 대상을 정의해야 한다.


public class Fruit {
 private String name;
 private int quantity;
 public Fruit(String name, int quantity) {
   this.name = name;
   this.quantity = quantity;
}
}

Comparable Interface

  • Comparable 인터페이스를 implements하고, compareTo 메소드를 오버라이드한다.

  • 이름순으로 정렬


public class Fruit implements Comparable<Fruit> {
 public String name;
 public int quantity;

 public Fruit(String name, int quantity) {
   this.name = name;
   this.quantity = quantity;
}

 @Override
 public int compareTo(Fruit other) {
   return name.compareTo(other.name);
}

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


public static void main(String[] args) {
   Fruit[] fruits = new Fruit[4];
   fruits[0] = new Fruit("pineapple", 70);
   fruits[1] = new Fruit("apple", 100);
   fruits[2] = new Fruit("orange", 80);
   fruits[3] = new Fruit("banana", 90);

   Arrays.sort(fruits);
   for(Fruit fruit : fruits)
     System.out.println(fruit);
}


apple 100
banana 90
orange 80
pineapple 70

Process finished with exit code 0
  • 재고 수량으로 정렬


public class Fruit implements Comparable<Fruit> {
 public String name;
 public int quantity;

 public Fruit(String name, int quantity) {
   this.name = name;
   this.quantity = quantity;
}

 @Override
 public int compareTo(Fruit other) {
   return quantity - other.quantity
}

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

두가지 정렬을 동시에 제공하려면? Comparator

  • 이름 순과 재고수량 순으로 정렬하는 compareTo 메소드는 동시에 가지고 있을 수 없다.

  • 하나의 객체 타입에 대해서 2가지 이상의 기준으로 정렬을 지원하려면,

  • Comparator를 사용해야 한다.

  • Comparator 인터페이스의 익명구현객체를 만들면서 compare 메소드를 Overriding한다.

    • 인터페이스 자체는 new를 통한 인스턴스 생성이 불가하지만,

    • anonymous Class. 즉, 익명의 클래스를 먼저 만들어서 내부에 compare 메소드를 정의 한 뒤, 해당 익명클래스의 인스턴스를 만든 것이다.

    • 익명클래스에 이름을 붙여 생성하지 않은 이유는, 일회성으로 사용될 것이기 때문이다.

  • 비교할 때, comparator 인터페이스를 구현상속한 객체의 compare 메소드를 통해서 비교 후 정렬이 이루어진다.

  • Collection에 있는 객체를 정렬하려면 Arrays만 Collections로 바꿔주면 된다.


Comparator<Fruit> nameComparator = new Comparator<Fruit>() {
 public int compare(Fruit fruit1, Fruit fruit2) {
   return fruit1.name.compareTo(fruit2.name);
}
}

Comparator<Fruit> quantityComparator = new Comparator<Fruit>() {
 public int compare(Fruit fruit1, Fruit fruit2) {
   return fruit1.quantity - fruit2.quantity;
}
}

Arrays.sort(fruits, nameComparator);
또는
Arrays.sort(fruits, quantityComparator);
  • 일반적으로 Comparator객체는 데이터 객체의 static member로 둔다. 정렬할 때는 Arrays.sort(fruits, Fruit.nameComparator);와 같이 호출한다.


public class Fruit {
 private String name;
 private int quantity;
 public Fruit(String name, int quantity) {
   this.name = name;
   this.quantity = quantity;
}
 
 public static Comparator<Fruit> nameComparator = new Comparator<Fruit>() {
   public int compare(Fruit fruit1, Fruit fruit2) {
     return fruit1.name.compareTo(fruit2.name);
  }
}

 public static Comparator<Fruit> quantityComparator = new Comparator<Fruit>() {
   public int compare(Fruit fruit1, Fruit fruit2) {
     return fruit1.quantity - fruit2.quantity;
  }
}
}







댓글
댓글쓰기 폼