프로그래밍 면접 이렇게 준비한다 - 정렬
정렬 알고리즘
- 각각의 차이와 장단점에 대해 알아야 한다
안정적인 알고리즘
- 알파벳 순서로 정렬시 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)
- 데이터 집합을 둘 이상의 부분집합으로 가르고, 각 부분집합을 정렬하여 다음 부분집합들과 다시 정렬된 형태로 합치는 방식
- 장점
- 집합이 메모리에 한번에 올리기 클때 쓰기 좋다
- 최고,최저,평균 시간 O(n log(n)) 으로 정렬 시간의 상한을 철저하게 지켜야할때 좋다
- 단점
- 다른 알고리즘에 비해 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