정렬

정렬

Arrays.sort()

• int, char와 같은 primitive type 배열 정렬 지원 (예외로 String도 지원)

• 해당 함수는 dual pivot quicksort 정렬 알고리즘을 활용. (primitive type일때)

• 일반 quickSort는 O(n^2) 복잡도를 지님
  → 이러한 퀵소트 속도를 보안하여 만든 것이 dual pivot quicksort.

• dual pivot quick sort = 삽입 정렬 + 퀵 정렬

• 사용법

**오름차순**
import java.util.Arrays;

public class Sort {
	public static void main(String[] args)  {	
		int[] array = {58, 32, 64, 12, 15, 99};
		
		Arrays.sort(array);
	}
}

**일부 오름차순**
import java.util.Arrays;

public class Sort {
	public static void main(String[] args)  {	
		Integer[] array = {58, 32, 64, 12, 15, 99};
		
		Arrays.sort(array, 1, 4);
	}
}

내림차순 정렬

• 내림차순 정렬은 Collections 내에 있는 reverseOrder()을 활용
• primitive type 배열: wrapper 클래스로 변경해서 사용
• primitive type boxing 하는법

int[] arr = {4, 3, 6, 1, 2};
Integer[] arr2 = Arrays.stream(arr).boxed().toArray(Integer[]::new); //방법1
Arrays.sort(arr2, Collections.reverseOrder());

arr = Arrays.stream(arr).boxed().sorted(Collections.reverseOrder()).mapToInt(Integer::intValue).toArray(); //방법2

• object type 배열: sort 내에 Collections.reverseOrder()을 바로 사용
• 사용법

**내림차순**
import java.util.Arrays;
import java.util.Collections;

public class Sort {
	public static void main(String[] args)  {	
		Integer[] array = {58, 32, 64, 12, 15, 99};
		
		Arrays.sort(array, Collections.reverseOrder());
	}
}

**일부 내림차순**
import java.util.Arrays;
import java.util.Collections;

public class Sort {
	public static void main(String[] args)  {	
		Intege array = {58, 32, 64, 12, 15, 99};
		
		Arrays.sort(array, 1, 4, Collections.reverseOrder());
	}
}

Object 배열 & N차원 배열 정렬

• object 정렬 → timSort
• tim sort = 삽입정렬 + merge sort
• Comparator 인터페이스로 int compare(T t1, T t2)를 구현

  List<Student> sList = new ArrayList<>();
  
  Comparator<Student> cp = new Comparator<>() {
  	@Override
  	public int compare(Student s1, Student s2) {
  		return s2.age - s1.age;
  	}
  };
  
  Collections.sort(sList, cp);

  • t1, t2 순서로 정렬 ⇒ return 음수
  • t1 == t2 ⇒ return 0
  • t2, t1 순서로 정렬 ⇒ return 양수

Lambda를 활용한 정렬

• comparator 객체는 method 1개인 함수형 인터페이스를 구현 ⇒ lambda 함수로 대체 가능
• 간결한 코드
• 예시: 문자열 length 길이에 따른 정렬

Arrays.sort(months,
            (String a, String b) -> a.length() - b.length());

→ 아래 코드: 더 깔끔한 방식

Arrays.sort(months, Comparator.comparingInt(String::length));

Stream으로 정렬

• Stream 클래스의 sorted() method도 Comparator 객체를 인자로 받아 정렬함
• 기존 객체의 순서를 변경하지 않고, 새롭게 정렬된 객체를 생성할 때 사용

List<Player> sortedPlayers = players.stream()
        .sorted((a, b) -> b.getScore() - a.getScore())
        .collect(Collectors.toList());