정렬 (sort)
- 주로 이진탐색을 위해 수행한다
- 정렬 알고리즘
- 복잡도
오른쪽으로 갈수록 오래 걸림 (최악)
sort 메서드
static void sort(Object[] a):Object[] a를 오름차순 배열static void sort(Object[] a, int fromIndex, int toIndex):Object[] a의fromIndex부터toIndex-1까지 오름차순 배열
- 1부터 4까지라고 말할 때, 4는 포함되지 않음 (2 <= x < 4)
대부분의 코드가 '~에서 ~까지'라고 할 때, 끝은 포함되지 않음.
(그러므로 만약 배열의 끝까지 정렬하고 싶다면n부터 arr.length까지 정렬명령하면 됨)
예시 (기초형 + String 배열)
import java.util.Arrays;
class SortEx1 {
public static void main(String[] args) {
int[] arr = {2, 6, 7, 3, 9, 5};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
String[] strs = {"apple", "apply", "application", "adapter", "always"};
Arrays.sort(strs);
System.out.println(Arrays.toString(strs));
String[] strs2 = {"가가나", "가가", "가나나", "가가가", "가나다"};
Arrays.sort(strs2);
System.out.println(Arrays.toString(strs2));
}
}- 하지만 그외 참조형 변수는 ... ERROR!
import java.util.Arrays;
class Phone {
private String model;
private int price;
public Phone(String model, int price) {
setModel(model);
setPrice(price);
}
public String getModel() {
return model;
}
public int getPrice() {
return price;
}
public void setModel(String model) {
this.model = model;
}
public void setPrice(int price) {
this.price = price;
}
@Override
public String toString() {
return model + "(" + price + ")";
}
}
class SortEx2 {
public static void main(String[] args) {
Phone[] list = {
new Phone("갤럭시20plus", 900000),
new Phone("갤럭시22ultra", 1300000),
new Phone("아이폰14pro-max", 1800000),
new Phone("아이폰13plus", 1100000),
new Phone("갤럭시x플립4", 1350000)
};
Arrays.sort(list);
}
}
-
ClassCastException : 부모 클래스 객체를 자식 객체로 형변환하려고 할 때 뜨는 오류
-
객체를 정렬하려면 -> 객체끼리 먼저 비교 -> 하지만 비교의 기준은?
기준1 - interface Comparable<T>
java.lang 소속 (= 사용 빈도 높음 = 매우 중요함!!!)
- 객체간 비교하는 방법 정의 (정렬을 위해서)
- 비교해서 크면 positive integer, 같으면 0, 작으면 negative integer 반환
a.compareTo(b)
a > b : 양수
a < b : 음수
a == b : 0- 객체간 비교할 때 사용하는 멤버변수가 integer이면
return (price - other.getPrice()) * -1;- 객체간 비교할 때 사용하는 멤버변수가 String이면
return model.compareTo(other.getModel()) * -1;- interface Comparable를 implements하여 compareTo() 정의
-> natural ordering 형성
Natural ordering of Java objects is ordering
based on interface implementation (i.e. method ).ComparablecompareTo
- generics : 1.5~
타입을 미리 정하지 않고 동적으로 객체 생성시에 결정
1.7부터 생략 가능
한계: 클래스 정의할 때 T 멤버변수, T 패러미터를 활용할 수 없음 (무엇이 올지 알 수 없으니까)
그러니까 사용하려고 하지 말고 그냥 이해만 하자.
interface에서 사용할 경우 implements 될 때(override할 때) 결정된다.- generics이 생긴 이유
원래는 Object로 받음 -> 뭐든 넣을 수 있으니까 넣고 확인하고 형변환해야함 (+a 이유 있음 나중에 설명)
class Some<T> {
public T member;
public Some(T member) {
this.member = member;
}
}
interface ITodo<T> {
void printSome(T t);
}
class Other implements ITodo<String> {
public void printSome(String t){
}
}
class SortEx3 {
public static void main(String[] args) {
Some<String> s1 = new Some<String>("abc");
Some<Phone> s2 = new Some<Phone>(new Phone("갤럭시2", 50000));
}
}예제
/*
======================
Human
======================
- name : String
- age : int
- weight : double
======================
+ Human(name : String, age : int, weight : double)
+ getters / setters
+ toString() : String
1. 나이로 오름차순 정렬, 나이가 같으면 모무게로 내림차순
2. 이름으로 내림차순 정렬, 이름이 같으면 나이로 내림차순
3. 몸무게로 오름차순 정렬, 몸무게가 같으면 나이로 오름차순
*/
import java.util.Arrays;
class Human implements Comparable<Human> {
private String name;
private int age;
private double weight;
public Human(String name, int age, double weight) {
setName(name);
setAge(age);
setWeight(weight);
}
public String getName() {
return name;
}
public int getAge() {
return age;
}
public double getWeight() {
return weight;
}
public void setName(String name) {
this.name = name;
}
public void setAge(int age) {
this.age = age;
}
public void setWeight(double weight) {
this.weight = weight;
}
@Override
public String toString() {
return name + "(" + age + ") " + weight + "kg";
}
@Override
public int compareTo(Human other) {
/* (1)
int result = age - other.getAge();
if(result == 0) {
result = (int) (weight - other.getWeight()) * -1;
}
return result;
*/
/* (2)
int result = name.compareTo(other.getName()) * -1;
if(result == 0) {
result = (age - other.getAge()) * -1;
}
return result;
*/
// (3)
int result = (int) (weight - other.getWeight());
if(result == 0) {
result = (age - other.getAge());
}
return result;
}
}
class SortEx4 {
public static void main(String[] args) {
Human h1 = new Human("김갑을", 40, 65);
Human h2 = new Human("김갑수", 45, 70);
Human h3 = new Human("김갑을", 45, 65);
Human[] list = new Human[] {h1, h2, h3};
Arrays.sort(list);
System.out.println(Arrays.toString(list));
}
}기준2 - interface Comparator<T>
interface comparable<T>의 한계 :
하나의 정렬 기준을 클래스 안에 코드로 넣어야 함. 그러므로,
- 타인이 만든 코드(클래스)를 수정하기 어려울 때 X
- 여러 정렬 기준을 사용해야 할 때 (오름차순, 내림차순, 가격순, 무게순...) X
- 그래서 등장한 것이 comparator
Comparable과 Comparator
- 주 비교 기준인 comparable - 직접비교 (객체 간 직접 비교)
- 부 비교 기준인 comparator - 간접비교 (제3의 객체를 만들어 비교)
- 둘은 별개의 기능 수행, 경우에 따라 선택해서 사용
compare(T o1, T o2) 메서드
- 추상메서드 (오버라이드 필수)
- 첫번째 패러미터
T o1이 비교 기준 (<->compareTo(T o): this object가 기준)
equals(Object obj) 메서드
- 추상메서드 (사용할 경우에만 따로 오버라이드 - 안하면 Object에서 오버라이드함)
sort 메서드 (for comparator)
- 배열
T[] a를Comparator <? super T> c에 따라 정렬함
generic이 java api 문서에서 나타나는 형태 2가지
? super T: T의 상위 타입(T 포함) - 하향제한? extends T: T의 하위 타입(T 포함) - 상향제한?: Object (모든 객체)
- 어떻게 쓰여있든 대부분은 그냥 T를 의미함
double값을 int로 출력할 때는 반올림에 주의
public int compare(Object o1, Object o2) { return o1.weight - o2.weight; // 자동 반올림될 때 -0.5 < x < 0.5 구간이 0으로 처리되어 오류가 날 수 있음 // 확실하게 하기 위해 if문으로 정리 }
binarySearch(Object[] a, Object key) 메서드
- key에 해당하는 Object를 binary방식으로 검색함 (return: index 번호)
- 대상 범위(배열)가 이미 정렬되어 있어야 한다
- 정렬 기준에 해당하는 정보('key' 객체)로 검색이 가능하다.
(만약 기준이 여러개 있다면 검색용 생성자는 그것을 모두 포함해야 함)
- natural ordering을 이용하지 않으려는 경우는, Comparator를 따로 생성하여 사용할 수도 있다.
welcome