정렬 알고리즘은 단골 면접 질문이다. 최근에 본 면접에서도 특정 정렬 알고리즘에 대해 설명해 보라는 질문을 받았다. 학교 수업 때나 코테 준비를 하면서 여러 가지 알고리즘을 접해 보았고 전반적으로 이해는 하고 있지만 막상 면접 때 일목요연하게 답하려 하니 만만치 않았다. 그래서 이번에 한꺼번에 다시 정리를 하면서 면접 때 답변한 방식도 대강 정해 놓으려 한다. 1. 거품 정렬 Bubble Sort 시간복잡도: O(n^2) 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 각 리스트를 한 번씩 훑을 때마다 가장 끝 자리의 원소는 정렬에서 제외된다. 각 회전마다 하나의 원소씩 제외하고, 각 원소의 길이 -1(두 개씩 비교하기 때문) 만큼 회전을 반복하기 때문에 ..