파이썬 알고리즘 인터뷰 정렬 간단 정리

정렬

• 정렬 목록의 요소를 특정 순서대로 넣은 알고리즘 대게 숫자식 순서, 사전식 순서로 정렬 빅오, 분할 정복, 이진 트리, 시간과 공간의 트레이드오프 등 여러 가지 컴퓨터과학의 핵심 주제를 아우름
  • 버블 정렬 n 번의 라운드로 이뤄져 있으며 각 라운드마다 배열의 아이템을 한 번씩 쭉 모두 살펴본 후 연달아 있는 아이템 2개의 순서가 잘못되어 있는 것 발견 시 두 아이템 맞바꿈 배열 전체를 살펴보는 것을 n번 반복하기 때문에 시간 복잡도는 항상 O(n ^ 2) 가장 비효율적이며 구현 가능한 가장 느린 정렬 알고리즘
  • 병합 정렬 각 요소들을 더 이상 분할할 수 없을 때 까지 분할한 후 분할 끝났을 시 정렬하면서 정복 분할 정복을 이요한 알고리즘 최선과 최악 모두 O(n log n) 안정 정렬
  • 퀵 정렬 분할 정복 알고리즘 피봇이라는 개념을 이용해 피봇보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝 하며 분할한 뒤 각각 정렬하는 함수를 재귀 호출하여 정복한 뒤 결합함 불안정 정렬
  • 삽입 정렬 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘
  • 안정 정렬 vs 불안정 정렬 입력 값이 유지되는 안정 정렬이 불안정 정렬보다 훨씬 더 유용함 퀵 정렬이 최악의 알고리즘이 될 수 있음
    • 안정 정렬 중복된 값을 입력 순서와 동일하게 정렬
    • 불안정 정렬 기존의 정렬 순서는 무시된 채 섞이는 정렬
  • 내장 함수 Python 의 기본 정렬 알고리즘은 병합 정렬과 삽입 정렬을 휴리스틱하게 조합한 팀소트를 사용함
  • 콤마 연산자 중첩 리스트를 만들어주는 역할 함