<aside> ❓ 정렬(Sort)란 ‘데이터’를 ‘특정한 기준에 따라 순서대로 정렬’하는 알고리즘이다..

</aside>

→ 이때 **stability(안정성)**이란, 동일한 값을 가진 요소들의 순서가 정렬 전후로 변하지 않는다는 것을 의미한다. 즉, 정렬 알고리즘이 동일한 값의 순서를 보존한다는 것을 의미한다.

정렬 알고리즘의 종류

• 퀵 정렬(Quick Sort) : 분할 정복 방식을 이용하여 배열을 빠르게 정렬하는 알고리즘
  • Arrays.sort() : 퀵 정렬을 사용하여 배열(기본 타입, 객체 타입)을 정렬에 사용
  • Collections.sort() : 퀵 정렬을 사용하여 객체 배열(List, Set, Queue)을 정렬에 사용
• 버블 정렬(Bubble Sort) : 인접한 두 원소를 비교하여 큰 값을 오른쪽으로 이동 시키는 방식으로 정렬하는 알고리즘
• 선택 정렬(Selection Sort) : 주어진 배열에서 최소값을 찾아 맨 앞 원소와 교환하는 방식으로 정렬하는 알고리즘
• 삽입 정렬(Insertion Sort) : 정렬되어 있는 부분집합 내에서 자신이 들어갈 위치를 찾아 삽입하는 방식으로 정렬하는 알고리즘
• 병합 정렬(Merge Sort) : 분할 정복 방식을 이용하여 배열을 정렬하는 알고리즘
• 힙 정렬(Heap Sort) : 힙이라는 자료구조를 이용하여 정렬하는 알고리즘
• 기수 정렬(Radix Sort) : 각 자리의 숫자를 비교하여 정렬하는 알고리즘

💡각 알고리즘 별 동작 방식은 다음 사이트를 참고

https://adjh54.tistory.com/334

Arrays.sort()를 이용한 정렬 방법

• 기본 오름차순 정렬 : Arrays.sort(data)

  → 리턴 타입이 있지 않고, 메서드 내부에서 집합을 정렬하여 재배치함으로 변수 자체의 순서 변경

  int[] array = {5, 2, 8, 1, 9};
  Arrays.sort(array); // {1, 2, 5, 8, 9}
  

• 내림차순 정렬 : Arrays.sort(data, Collections.reverseOrder())

  → int와 같은 Primitive Type의 경우 사용이 안되므로 Integer와 같이 Wrapper Class 사용

  Integer[] array = {5, 2, 8, 1, 9};
  Arrays.sort(array, Collections.reverseOrder()); // {9, 8, 5, 2, 1}
  

<aside> ❗ 위의 방법으로 String과 같은 다른 데이터 타입의 경우에도 정렬 가능하다.

이는 클래스 내부에 Comparable을 구현하여 오버라이딩된 compareTo() 메서드에 의해서 정렬의 순서가 결정된다.

※ String의 경우에는 compareTo()가 문자열을 사전 식으로 정렬되도록 설정되어 있다.

</aside>

Collections.sort()를 이용한 정렬 방법

Arrays와 유사하게 Collections 클래스를 이용해 정렬을 수행할 수 있다. (List에 주로 사용)

• 기본 오름차순 정렬 : Collections.sort(data)

  int[] array = {5, 2, 8, 1, 9};
  List<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
  Collections.sort(array); // {1, 2, 5, 8, 9}
  

• 내림차순 정렬 : Collections.reverse(data)

  int[] array = {5, 2, 8, 1, 9};
  List<Integer> list = new ArrayList<Integer>(Arrays.asList(array));
  Collections.reverse(array); // {9, 8, 5, 2, 1}
  

Arrays.sort와 Collections.sort의 **시간 복잡도(Big-O)**는 다음과 같다.

• Arrays.sort() : 평균적으로는 O(nlog(n))의 시간 복잡도이지만, 드물게 O(n^2)의 최악의 경우가 발생할 수 있다.
• Collections.sort() : 시간 복잡도 O(n) ~ O(nlog(n))을 보장한다.

<aside> 💡 간단한 자료구조를 사용하는 경우에는 Arrays 클래스의 메서드를 이용하지만, 만약 시간 제한을 고려해야한다면 Collcetions 클래스의 메서드를 사용하자.

</aside>