[알고리즘] 정렬 알고리즘 판단

정렬 알고리즘의 좋고 나쁨의 판단 기준

1. 복잡도

2. 추가적으로 필요한 메모리 (in-Place성)

3. 안정적 정렬 여부 (안정성)

1. 복잡도

시간복잡도와 공간복잡도

---

2. In-Place성

정렬하는 과정에서 추가적으로 필요한 메모리의 양을 의미한다

• 예를 들면, 버블정렬과 선택정렬, 삽입정렬은 모두 새로운 메모리 공간이 따로 필요하지 않고, 기존의 배열내에서 swap이나 대입으로 정렬을 진행한다 -> In_place 정렬
  
  
• 하지만, 계수정렬과 같은 경우에는, 해당 배열내의 최대값을 기준으로 새 배열을 할당하기 때문에 추가적인 메모리가 든다 -> In_place정렬이 아니다
  -> 계수정렬은 배열내의 크기가 작고, 값이 적은 경우에 효과적이다

---

3. 안정성

동일한 요소(값)에 대해 정렬할 때, 어떻게 처리하는 가를 다루는 것

• 안정적 알고리즘 : 동일한 값의 순서가 바뀌지 않음 (기존의 순서를 지킴)
  -> 버블정렬, 삽입정렬, 병합정렬 등
• 불안정 알고리즘 : 동일한 값의 순서가 바뀜
  -> 선택정렬, 퀵정렬 등

안정적 알고리즘

• 예시로 4 2 2 3 4 가 들어있는 배열을 버블정렬로 정렬해보겠다

• 버블정렬은 인접한 요소끼리 비교한 뒤 값을 교환하는 정렬 방식이다

• 해당 배열안에 동일한 값의 연두색2와 노란색2가 있다
  -> 정렬을 다 수행한 뒤에도 서로의 2가 기존의 위치인 앞:연두색, 뒤:노란색으로 기존의 위치가 유지되었다

불안정적 알고리즘

• 예시로 4A 3 2 4B 1 이 들어있는 배열을 선택정렬로 정렬해보겠다

• 선택정렬은 배열의 원소 값들 중 최소값을 찾고 맨 앞의 원소와 교환하면서 정렬하는 방식이다

• 해당 배열 안에 같은 값 4A와 4B가 있다 (같은값이지만 기존배열 내 앞에 있는 값 4A가 더 작은 값으로 간주된다)
  

• 최소값이 1이 맨 앞의 원소인 4A와 swap되면서 기존의 4A 4B 순서가 4B 4A가 되었다
  -> 선택정렬을 다 한 뒤 결과값이 기존의 순서와 달라진다
  -> 이 경우에 운이 좋다면 4A가 4B와 교환되어 기존의 결과와 같아질 수 있을 가능성이 있지만, 선택정렬은 같은 값일 경우 기존의 결과와 달라질 수도 있기 때문에 불안정적 정렬방식이다