패스트캠퍼스 챌린지 22일차

다양한 정렬 응용법

 정렬이란?

  - 오름차순이면 크기가 작은것부터 점점 큰 순으로 정렬

  - 내림차순이면 크기가 큰것부터 점점 작은 순으로 정렬

 

1. 정렬 조건이 필요

 - 오름차순 이라면 크기가 제일 작은것을 앞으로 이동 시켜야 한다

 

2. N개의 원소를 정렬하는 것은 O(N logN) 만큼의 시간 복잡도를 가짐

• JAVA의 Arrays.sort(arr) 

Privitive 원소 정렬 EX) int,double...	Object 원소 정렬
Dual-Pivot Quick Sort	Tim Sort
최선 시간 복잡도 : O(N)	최선 시간 복잡도 : O(N)
최악 시간 복잡도 : O(N^2)	최악 시간 복잡도 : O(NlogN)
평균 시간 복잡도 : O(N logN)	평균 시간 복잡도 : O(N logN)

 

3. In-place / Stable 여부를 알아야한다.

   1) 정렬 알고리즘이 In-place(제자리) 한가?

     => 정렬하는 과정에서 N에 비해 충분히 무시할 만한 개수의 메모리만큼만 추가적으로 사용하는가?

  

    2) 정렬 알고리즘이 Stable(안정) 한가?

      => 동등한 위상의 원소들의 순서 관계가 보존 되는가?

      EX) 동등한 관계에 있는 값을 들어온 순서에 따라 그대로 정렬하는가

 

 

정렬의 특성 

 -  같은 정보들은 인접해 있을것이다.

 - 각 원소마다 가장 가까운 원소는 자신의 양 옆중에 있다. 

  => 당연한것이지만 이해하고 문제를 해결하라

 

문제 풀이 시 정렬할 대상의 class를 정렬한 상태로 반환하기 위해 Comparable<T>를 구현하여 class를 생성

@Override

public int compareTo(T other){

   return 결과값 // 음수 : 내림차순, 0 : 동등, 1 : 오름차순

}

 

 

22일차 인증

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]