프로그래밍 면접 이렇게 준비한다 - 정렬

정렬 알고리즘

• 각각의 차이와 장단점에 대해 알아야 한다

안정적인 알고리즘

• 알파벳 순서로 정렬시 a1,b,a2 -> a1,a2,b 처럼 상대적인 위치가 그대로 유지되는 알고리즘을 말한다.

1. 선택 정렬

• 가장 단순한 정렬 알고리즘
• 배열의 첫번쨰 원소에서 시작하여 전체를 훑으면서 가장 작은 키를 갖는 원소와 맞바꾸며 진행한다
• (n-1)+(n-2)+…+1 번 수행하므로 n(n-1)/2회 수행되며 최선, 평균, 최악 모두 O(n^) 이다
• 불안정한 알고리즘

2. 삽입 정렬

• 한번에 한 원소씩 이미 정렬된 다른 원소들과 비교하여 새원소를 제 위치에 삽입하며 정렬된 배열을 만든다.
• 이미 정렬된 리스트에 새 원소를 추가할때 매우 효율
• 무작위로 정렬된 많은 데이터를 처리할땐 O(n^) 좋은 알고리즘x
• 안정적인 알고리즘
• 소량의 데이터 집합을 처리할때 강점 발휘

3. 퀵 정렬

• 집합 내에서 한 피벗 값 을 고른 다음 그것을 기준으로 두 부분집합으로 나눈다. 한쪽은 피벗보다 작은 값, 다른 한쪽은 피벗보다 큰 값을 넣는다. 더이상 쪼갤 부분집합니 없을 때 가지 반복한다.
• 최선,평균 O(n log(n)) / 최악 O(n^)
• 불안정한 알고리즘

4. 합병 정렬(merge sort)

• 데이터 집합을 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬하여 다음 부분집합들과 다시 정렬된 형태로 합치는 방식
• 장점
  1. 집합이 메모리에 한번에 올리기 클때 쓰기 좋다
  2. 최고,최저,평균 시간 O(n log(n)) 으로 정렬 시간의 상한을 철저하게 지켜야할때 좋다
• 단점
  1. 다른 알고리즘에 비해 O(n) 수준의 메모리가 추가로 필요

5. 버블 정렬

• 매번 연속된 두개 인덱스를 비교하여, 큰값을 뒤로 넘겨준다
• 1부터 비교하여 n-1, n-2개…1개씩 비교를 반복하므로 O(n^) 이다

정리

- 선택 정렬 : 가장단순 / O(n^) / 불안정
- 삽입 정렬 : 이미 정렬되어있으면 O(n) , 최악 O(n^) / 안정적
- 퀵정렬 : 가장 빠르다 / O(n log(n)) / O(n^) / 불안정
- 합병정렬 : merge sort : O(nlong(n)) / 메모리 O(n)추가 필요 / 집합크기가 클때 사용 / 안정적
- 버블정렬 : O(n^)

정렬문제

Q.상대적으로 빠른 정렬 A. 퀵정렬, 그다음이 합병정렬

Q.데이터가 클때 사용하는 정렬 A. 퀵정렬, 합병정렬

Q. 정렬시 가장 적합한 알고리즘은 무엇인가요?

A. 어떤 데이터인가요?
- 데이터가 이미 거의 정렬됬나요?
- 데이터 집합의 크기는 보통 어느 정도인가요?
- 중복된 키 값이 있나요?

B. 정렬 조건이 어떻게 되나요?
- 최선,최악,평균 중 어느 상황에 맞춰서 정렬해야하나요?
- 정렬 안정성을 만족시켜야 하나요?

C. 어떤 시스템인가요?
- 정렬하는 데이터가 사용 가능한 메모리 크기에 비해 큰가요?

---

Reference

• 프로그래밍 면접 이렇게 준비한다
• https://hsp1116.tistory.com/33