[정렬] sort, Comparable, Comparator, generic

포키·2022년 11월 21일
0

국비과정

목록 보기
31/73

위키피디아 정렬 알고리즘


정렬 (sort)

  • 주로 이진탐색을 위해 수행한다
  • 정렬 알고리즘
    • 복잡도
      오른쪽으로 갈수록 오래 걸림 (최악)

sort 메서드

  • static void sort(Object[] a) : Object[] a를 오름차순 배열
  • static void sort(Object[] a, int fromIndex, int toIndex) : Object[] afromIndex부터 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>의 한계 :
    하나의 정렬 기준을 클래스 안에 코드로 넣어야 함. 그러므로,
  1. 타인이 만든 코드(클래스)를 수정하기 어려울 때 X
  2. 여러 정렬 기준을 사용해야 할 때 (오름차순, 내림차순, 가격순, 무게순...) 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[] aComparator <? 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 번호)
  1. 대상 범위(배열)가 이미 정렬되어 있어야 한다
  2. 정렬 기준에 해당하는 정보('key' 객체)로 검색이 가능하다.
    (만약 기준이 여러개 있다면 검색용 생성자는 그것을 모두 포함해야 함)

  • natural ordering을 이용하지 않으려는 경우는, Comparator를 따로 생성하여 사용할 수도 있다.
profile
welcome

0개의 댓글