[정렬] 정렬의 종류와 외워둘 사항들, 예상 면접 질문

정렬 알고리즘의 종류

삽입, 선택, 버블, 합병, 기수, 퀵, 쉘, 힙 정렬

 

정렬 알고리즘의 시간 복잡도

https://search.pstatic.net/common/?src=http%3A%2F%2Fblogfiles.naver.net%2FMjAxOTAzMjhfMjkg%2FMDAxNTUzNzY3NzU1OTUy.odfu07SVD2bCAbVbLj8mgjPEuSpJgCtky5TXmr4RBowg.kzPrRLctiDpuDlFX1gGeFYjswgNyeQ3wmI4mPUAJVm8g.PNG.idc1204%2Fimage.png&type=sc960_832

Big-O 시간복잡도

O(1) > O(log n) > O(n) > O(n log n) > O(n2) > O(2n) > O(n!)

 

💡 시간 복잡도는 최악의 경우를 두고 생각한다

​

퀵정렬의 경우 예외적인 상황(이미 정렬이 돼있는 경우)을 제외하곤 평균적으로 빠른 속도를 보여주지만

데이터의 크기가 커지거나 규모가 큰 프로젝트에서는 이러한 예외 상황을 그냥 지나치기 어렵기 때문에

정렬 알고리즘을 사용할 때는 항상 최악의 시간복잡도를 고려해서 사용하는 것이

예외를 두지 않는 좋은 방법이라고 생각한다.

​

다만, 정렬되는 데이터의 크기가 항상 동일하거나 로직이 복잡하지 않은 소규모의 프로젝트에서 사용할 경우에는 본인에게 맞는 정렬 알고리즘을 사용하는 것이 좋다. 시간복잡도가 성능을 보장해주는 것이 아니며,

기수 정렬과 같은 알고리즘은 시간 복잡도가 가장 낮지만 특수한 상황에서만 사용 가능하다.

 

 

 

예상 면접 질문

• 퀵 정렬의 특징과 시간복잡도에 대해 설명해주세요. 
  
  • 빠른 정렬 속도를 가진 분할/정복 알고리즘
  • 하나를 피봇으로 설정하고 피봇보다 큰 값과 작은 값으로 분할해서 정렬
  • 병합정렬과 다르게 리스트를 비균등하게 분할
  • 장점 : 추가적인 메모리를 필요로 하지 않음
  • 단점: O(nlogn)이지만 worst case 경우 O(n^2)까지 나빠짐
• 퀵 소트 성능 개선 기법으로는 어떤게 있나요?
  • 1. 피벗을 맨 처음 값을 정하면 최악의 경우 O(N^2)을 가지므로 랜덤하게 피벗을 설정하기
  • 2. 맨 앞과 중간, 맨 뒤 값을 우선적으로 정렬하고 중앙 값을 피벗으로 삼는 방법
  • 하지만 이렇게 해도 O(nlogn)이 되진 않음
• 퀵 소트를 여러 언어의 정렬 내부 구현으로 사용하는 이유가 뭘까요?
  • 피벗을 적절하게 선택하도록 구현해 성능 개선할 수 있음
  • 한번 위치가 정해진 원소는 정렬을 위해 확인할 대상에서 제외된다는 특성이 있어서
  • 평균적으로 병합 정렬보다 빠르다
• 버블 정렬에 대해 설명해주세요.
  • 서로 인접한 두 원소를 비교해서 정렬하는 알고리즘
  • 0번 인덱스부터 n-1번 인덱스까지 모두 비교
  • O(n^2)
• 선택 정렬에 대해 설명해주세요.
  • 첫번째 값을 두번째~마지막 값이랑 비교해서 최솟값을 찾아 바꿈
  • 두번째 값을 세번째~마지막 값이랑 비교해서 최솟값을 찾아 바꿈
  • 이것을 0번 인덱스부터 n-2번 인덱스까지 반복
  • O(n^2)
• 삽입 정렬에 대해 설명해주세요.
  • 두번째 값부터 시작해서 그 앞에 있는 원소들과 비교해서 삽입할 위치를 삽고, 삽입하는 정렬 알고리즘
  • O(n^2)이고, 선택이나 버블과 다르게 이미 정렬이 되어있을 때인 best case의 경우 O(n)까지 높아질 수 있다 
• 힙 정렬에 대해 설명해주세요.
  • 주어진 데이터를 완전 이진 트리를 기반으로 한 힙트리로 만들어서 최댓값 또는 최솟 값부터 하나씩 꺼내서 정렬하는 알고리즘 
  • 힙 정렬은 전체 정렬보다는 가장 큰거나 작은 몇 개의 값만을 필요할 때 좋다
  • O(nlogn)
• 병합 정렬의 특징과 시간복잡도에 대해 설명해주세요.
  • 주어진 배열을 크기가 1인 배열로 분할하고 합병하면서 정렬하는 대표적인 분할/정복 알고리즘
  • O(nlogn)
• Big-O 표기법의 시간 복잡도 크기 순서를 말해주세요. 
  • O(1) > O(log n) > O(n) > O(n log n) > O(n2) > O(2n) > O(n!)
• 정렬의 최악의 경우는 O(n^2)인데, 이문제를 해결하는 방법이 있나요?
• 정렬에는 다양한 방법이 있는데, 알고 있는 방법에는 무엇이 있나요?
• 왜 정렬 알고리즘은 많을까요?
  • 하나가 무조건 우수한게 아니고, 주어진 상황에 따라 얻는 것이 있으면 잃는 것이 있다는 "trade off"가 있기 때문
• 구체적인 Trade-Off의 예시가 있을까요?
  • 퀵소트는 평균 경우 O(nlogn)을 갖지만 정렬된 경우 O(n^2)을 가짐
  • 삽입정렬은 평균 O(n^2)을 갖지만 정렬된 경우 O(N)을 가짐
• 이미 정렬된 데이터에 대해 가장 좋은 성능을 보이는 정렬 알고리즘은 무엇인가요?
  • 삽입 정렬
  • 자기 앞에 있는 원소에 대해서만 비교를 수행하므로 O(N)
• 버블 정렬 같은 알고리즘은 왜 사용할까요? 
  • 구현이 쉬움
  • 다른 메모리 공간이 필요 없음
  • 안정 정렬이다
  • 데이터 크기가 크지만 않으면 성능 저하가 크지 않음
• 안정 정렬은 무엇이고, 종류는 뭐가 있나요?
  • 정렬된 후에도 동일한 값을 가진 요소들의 상대적인 순서가 정렬 이전과 같은 상태로 유지되는 정렬 알고리즘
  • 데이터에 동일한 값이 여러 개 존재한다면, 안정 정렬 알고리즘은 이 값들이 원래의 순서대로 배치되도록 보장
  • 삽입, 버블, 병합, 계수 정렬
• 왜 삽입 정렬이 평균 O(N^2) 시간 복잡도를 갖는 알고리즘 중 가장 빠를까요?
  • 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해서 자신의 위치를 찾음
  • 따라서 삽입할 위치까지만 탐색하면 되니까 선택/버블에 비해 빠르다
• 본인이 사용하는 언의 정렬 알고리즘이 무엇인지 알고 있나요?
  
  • Arrays.sort(), Collections.sort()
  • 공통적으로 Timsort를 사용
  • 합병 정렬(Merge Sort)과 삽입 정렬(Insertion Sort)을 결합한 하이브리드 정렬 알고리즘으로, 안정적인 정렬을 보장

---

출처

알고리즘 면접 대비 질문 리스트업 : 네이버 카페 (naver.com)

알고리즘 면접 대비 질문 리스트업

신입 개발자 기술면접 질문 정리 - 알고리즘 (tistory.com)

신입 개발자 기술면접 질문 정리 - 알고리즘