[알고리즘] Sort - Java에서의 정렬 (Sort in java)

Sort - Java에서의 정렬 (Sort in java)

정렬 알고리즘에 대한 이야기가 아닌 실생활에서 쓰이는것에 대해 말해보자

실제로 정렬알고리즘은 기초적이고 매우 많이 사용 되기 때문에

직접 구현하지 않고 제공되는 경우가 많다.

따라서, 가장 많이 사용하는 Java를 예로 들어 정렬의 사용법에 대해 알아보자

int[] data = new int [capacity];
// data[0]에서 data[capacity-1]까지 데이터가 꽉
// 차있는 경우에는 다음과 같이 정렬한다.
Arrays.sort(data);
// 배열이 꽉 차있지 않고 data[0]에서 data[size-1] 까지                                                             
// size개의 이터만 있다면 당음과 같이 한다.
Arrays.sort(data,0,size);

자바는 위와 같이 원시(primitive) 데이터 타입에 대해 정렬을 지원한다.

Int 이외의 double, char에 대해서도 적용이 가능하다.

String [] fruits = new String [] {"pineapple", "Apple", "Orange", "Banana"}                                
 
Arrays. sort(fruits);
for(String name: fruits){
    System.out.println(name);
}
 

원시(primitive) 데이터 타입과 마찬가지로 String 클래스도

sort 메소드 사용이가능하다.

문자열은 사전식으로 정렬이 되어있기 때문이다.

List<String> fruits = new ArrayList<String>();                                                             
fits.add("Pineapple");
fits.add("Apple");
fits.add("Orange");
fits.add("Banana");
 
Collection.sort(fruits);
 
for(String name: fruits){
    System.out.println(name);
}
 

다음은 collection 오브젝트 하위의 구조들에 대한 정렬이다.

Arrays.sort를 사용하지 못하는대신

Collection에서 sort 메소드를 제공한다.

public class Fruit{
    public String name;
    public int quantity;
    public Fruit(String name, int quantity){                                                               
        this.name = name;
        this.quantity = quantity;
    }
}
 
// somewher in your program
Fruit [] fruits =  new Fruit[4];
fruits[0] = new Fruit("Pineapple", 70);
fruits[1] = new Fruit("Apple", 70);
fruits[2] = new Fruit("Orange", 70);
fruits[3] = new Fruit("Banana", 70);
 
Arrays.sort(fruits);

이제 사용자 정의 객체에 대해서 알아보자

위의 코드는 사용자 정의 객체 Fruit를 선언해서

객체를 하나하나 만들어 배열에 저장한 후 sort 메소드를 사용한 예제이다

그러나 sort메소드를 사용하면서 의문점이 발생한다.

무엇을 기준으로 정렬을 하는것인지 모호하기 때문이다.

이와 같은 상황에서는 올바르게 동작하지 않는다.

따라서 sort 메소드를 사용하기 위해서는 적절한 기준 데이터가 있어야한다.

public class Fruit implements Comparable<Fruit>{
    public String name;
    public int quantity;
    public Fruit(String name, int quantity){                                                                 
        this.name = name;
        this.quantity = quantity;
    }
    public int compareTo(Fruit other){
        return name.compareTo(other.name);
    }
}
 
// somewher in your program
Fruit [] fruits =  new Fruit[4];
fruits[0] = new Fruit("Pineapple", 70);
fruits[1] = new Fruit("Apple", 70);
fruits[2] = new Fruit("Orange", 70);
fruits[3] = new Fruit("Banana", 70);
 
Arrays.sort(fruits);

이와 같은 사용자 정의 객체를 하려면 

먼저 객체들 사이의 크기 관계를 어딘가에서 지정해주어야한다.

이를 위해서 2개의 방법이 있는데

첫번째로 Comparable interface를 사용하는 것이다.

Comparable interface에서 구현해야하는 메소드는 compareTo이다.

이 함수에서 비교할 기준값을 리턴해 주게 된다.

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

만약 재고 수량에 의한 비교를 하고싶다면 

위와 같은 코드를 작성해 주면 된다.

Comparator<Fruit> nameComparator = new Comparator<Fruit>(){
    public int compare(Fruit fruit1, Fruit fruit2){
        return fruit1.name.compareTo(fruit2.name);
    }
};
 
Comparator<Fruit> quantComparator = new Comparator<Fruit>(){                                               
    public int compare(Fruit fruit1, Fruit fruit2){
        return fruit1.quantity - fruit2.quantity;
    }
};
 
Arrays.sort(fruits, nameComparator);
Arrays.sort(fruits, quantComparator);

그렇다면 2개의 기준을 동시에 적용하고 싶다면 어떻게 해야할까

그때는 Comparator를 사용한다.

위와 같이 Comparator 인터페이스로 compare 메소드를 구현함으로써

각각의 조건에 맞는 case를 설정하고

경우에 따라 해당 객체의 compare 메소드를 사용하면된다.

public class Fruit implements Comparable<Fruit>{
    public String name;
    public int quantity;
    public Fruit(String name, int quantity){                       
        this.name = name;
        this.quantity = quantity;
    }
    public int compareTo(Fruit other){
        return name.compareTo(other.name);
    }
 
    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> quantComparator = new Comparator<Fruit>(){       
        public int compare(Fruit fruit1, Fruit fruit2){
            return fruit1.quantity - fruit2.quantity;
        }
    };
}
 

comparator의 위치를 보통 다음과 같이 작성한다.

타겟이 되는 객체 안에 public static으로 작성한다.

왜냐하면 각 객체마다 메모리의 낭비가 없이 

하나의 comparator 만 사용하면 되기 때문이다.

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘