Java/자바[18일차] (2)-정렬 알고리즘, Comparator인터페이스

정렬 알고리즘

---

위의 배열을 오름 차순으로 하는 알고리즘을 짠다 했을 때

숫자는 38,20,40,18,30,21이 있습니다.

인덱스 0번과 오른쪽의 인덱스 값을 비교합니다.

위의 숫자로 비교하자면 38과 20을 비교하겠네요

오름 차순이면 가장 작은 숫자가 인덱스 0번에 위치해야 합니다.

따라서 인덱스 0번에는 가장 작은 값이 와야 하기에

인덱스 0번이 오른쪽 인덱스 값 보다 크면 오른쪽으로 이동시켜 주어야 합니다.

즉, int i=0이라고 했을 때

index [i]>index [i+1]이라는 비교 식이 성립을 사용할 수 있습니다.

따라서 위의 값을 비교해 봤을 때 38은 20보다 크기 때문에 값을 오른쪽 값과 교환해 주어야 합니다.

반복문을 돌려서 인덱스 0번부터 배열의 끝 값까지 비교했다면 최소 값은 이제 index [0]이 고정입니다.

---

이제 또 비교하는 인덱스 번호를 이동하여 인덱스 1번부터 앞의 값을 비교합니다.

이러한 방법으로 인덱스의 끝 값 -1까지 하면 정렬 알고리즘을 짤 수 있게 됩니다.

코드

public static void main(String[] args) {
		int arr[]= {38,20,40,18,30,21};
		
		for(int i=0;i<arr.length-1;i++) {
				for(int j=i+1;j<arr.length;j++) {
						if(arr[i]>arr[j]) {
							int tmp=arr[i]; 
							arr[i]=arr[j];
							arr[j]=tmp; 
						}
				}
			}
}

위의 코드를 보시면 알겠지만 만약 arr [i]>arr [j]보다 크다면

tmp라는 변수에 arr [i]의 값을 담아줬습니다.

만일 arr [i]의 값을 다른 변수에 담아주지 않고 arr [i] = arr [j]에 바로 담는다면

arr [i]의 값은 사라지게 됩니다.

arr[i]의 값은 arr [j]로 가야 하기 때문에 

tmp라는 변수에 담아주고 arr [j]에 원래 arr[i]의 값을 담은  tmp변수를

arr [j]에 대입해 주어야 합니다.

---

Comparator인터페이스 구현하여 객체 비교하기

위와 같은 정렬은 기본형 타입이기에 부등호를 갖고 쉽게 두 변수를 비교할 수 있다.

하지만 객체의 경우에는 어떠한 필드 값을 비교할지 기준이 없기에 객체를 비교할 수 있으려면

Comparator인터페이스를 구현하여 객체를 비교할 수 있게 된다.

---

Comparator 인터페이스 구현하기

Comparator<T> 변수명 = new Comparator<T>();

---

compare( ) 메서드 사용하기

compare 메서드는 Comparator 인터페이스에서 반드시 구현해야 하는 메서드입니다.

2개의 인자 값을 비교하여, 결과를 int형으로 반환해 줍니다.

compare메서드 오버라이드

@Override
		public int compare(Member o1, Member o2) {
			if(o1.getAge()>o2.getAge()) {
				return 1;
			}else if(o1.getAge()<o2.getAge()) { //Member객체의 나이 비교
				return -1;
			}else {
			return 0;	
			}

---

compare재정의 해서 객체 정렬하기

[오름 차순]

Comparator<Member> m= new Comparator<Member>() {

		@Override
		public int compare(Member o1, Member o2) {
			return o1.getAge()-o2.getAge();
			}
		
	};

compare메서드는 비교 대상 2개의 객체의 인자를 차례로 받습니다.

첫 번째 인자가 두 번째 인자보다 작다면 음수, 같다면 0 크다면 양수를 리턴합니다.

위와 같이 Comparator을 구현했다면 

sort( ) 함수에 인자로 넘겨줍니다.

compare 메서드로 정렬 기준 정의를 완료하면

Array.sort 또는 Colections.sort를 호출하여 실제 정렬 처리를 수행해 줍니다.

compare메서드의 return 값이 양수인 경우 , 두 값의 자리가 변경됩니다.

음수의 경우에는 두 값의 자리가 변경되지 않습니다.

---

compare( ) 메서드 오름차순

o1은 자기 자신 o2는 비교대상

리턴 값만 변경해 주면 된다.

return o1-o2;

ex) [5,3,1,2,4]의 수를 비교한다 했을 때

return 5-3은 2가 나온다 즉, 양수 값이 나오기 때문에 두 자리가 변경됩니다.

오름차순 정렬 : [5,4,3,2,1]

---

내림차순

return o2-o1;

위와 마찬가지로 [5,3,1,2,4]의 수를 비교한다 했을 때

오름차순과는 순서가 반대로 됐음으로

return 3-5는 양수이므로 값이 변경되지 않고

쭉 오른쪽으로 가서 2-4는 -2가 나오는 음수 값을 갖게 됨으로

값이 변경됩니다.

[1,2,3,4,5]

---

사용 예시

Comparator<Member> m= new Comparator<Member>() {
		@Override
		public int compare(Member o1, Member o2) {
			return o1.getAge()-o2.getAge();
			}
		
	};
		System.out.println("나이 정렬 후");
		member.sort(m);
		System.out.println(member.toString());

---

객체의 age 정렬 전 객체 출력

객체의 age정렬 후 객체 출력

---

compareTo( ) 메서드

compareTo 메서드는 두 개의 값을 비교하여 int 값으로 반환해 주는 함수입니다.

compareTo메서드는 문자열 비교와 숫자의 비교 두 방식이 존재합니다.

• 숫자의 비교 : 크면 1을 리턴, 같으면 0을 리턴, 작으면 -1을 리턴해줍니다.
• 문자열의 비교 : 문자열 2개를 각각 같은 위치 문자를 하나씩 아스키 코드 값으로 비교하여
  • 같으면 0, 그 외 양수/음수 값을 반환해줍니다.

---

compare( ) 메서드 리턴 값에 comapreTo( ) 메서드 사용해보기

Comparator<Member> ascName= new Comparator<Member>() {
			
			@Override
			public int compare(Member o1, Member o2) { //리스트에 인접한 2개의 o1,o2를 비교
				return o1.getName().compareTo(o2.getName()); //o1이 o2보다 작으면 : 오름 차순
			}
		};
		member.sort(ascName);

---