[면접용] 기본 정렬 알고리즘 정리

정렬 알고리즘은 단골 면접 질문이다. 최근에 본 면접에서도 특정 정렬 알고리즘에 대해 설명해 보라는 질문을 받았다. 학교 수업 때나 코테 준비를 하면서 여러 가지 알고리즘을 접해 보았고 전반적으로 이해는 하고 있지만 막상 면접 때 일목요연하게 답하려 하니 만만치 않았다. 그래서 이번에 한꺼번에 다시 정리를 하면서 면접 때 답변한 방식도 대강 정해 놓으려 한다.

 

1. 거품 정렬 Bubble Sort

시간복잡도: O(n^2)

 

서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘. 

각 리스트를 한 번씩 훑을 때마다 가장 끝 자리의 원소는 정렬에서 제외된다.

각 회전마다 가장 마지막 원소를 제외한다

각 회전마다 하나의 원소씩 제외하고, 각 원소의 길이 -1(두 개씩 비교하기 때문) 만큼 회전을 반복하기 때문에 시간 복잡도는 (n-1) + (n-2) + (n-3) + (n-4) +... + 3 + 2+ 1 = n(n-1)/2  => O(n^2) 이 된다. 

 

정렬이 되어 있건 안되어 있건 비교의 횟수는 동일하기 때문에 항상 시간복잡도가 O(n^2)로 일정하다는 특징이 있다.

 

또한 중복된 값의 위치가 초기 순서(입력 순서)와 동일한 안정 정렬에 해당한다. 이유는 간단하다. 비교할 두 값이 같으면 swap을 진행하지 않기 때문에 값은 값끼리 순서가 바뀔 일이 없다. 이를 안정성이 존재한다라고 말하기도 한다.

 

또한 주어진 배열 상에서 교환이 이루어 지므로 공간복잡도는 O(n)에 해당한다.

면접용: Bubble Sort에 대해 간단하게 설명해 보세요

Bubble Sort는 리스트의 한쪽 끝부터 시작하여 서로 인접한 두 원소를 비교해 나가며 진행하는 정렬 방식입니다.

본래 리스트의 정렬 상태와 관계없이 비교의 횟수가 동일하여 O(n^2)의 시간 복잡도를 가지는 특징이 있으며 이러한 특성으로 인해 정렬하려는 리스트의 상황에 따라 다른 정렬 알고리즘에 비해 굉장히 비효율적일 수도 있다는 단점이 있습니다.

 

장점으로는 구현이 매우 간단하고 직관적이며, 정렬을 진행하는데 다른 메모리 공간이 필요하지 않다는 점이 있습니다.

 

 

 

2. 선택 정렬 Selection Sort

시간복잡도: O(n^2)

 

해당 인덱스에 올 값을 찾아 선택하는 알고리즘.

리스트의 0번째 위치부터 시작하여 전체 리스트에서의 최솟값을 찾아 그 자리로 치환해주는 방식이며, 거품정렬과 마찬가지로 해당 리스트의 원소가 정해지면 다음 회전에서 제외한다,

값이 정해진 인덱스를 제외한 리스트에서의 최솟값을 찾아 치환해준다.

비교 횟수는 거품정렬과 같으므로 시간복잡도도 O(n^2) 으로 동일하다. 공간복잡도도 거품정렬과 동일하게 O(n)이다.

그렇다면 거품 정렬과는 무엇이 다를까? 결론적으로 말하면 선택 정렬은 불안정 정렬이다. 거품 정렬이 두 값을 비교해 가면서 계속 swap을 진행하는 것과 달리 선택정렬은 해당 리스트 범위 내에 최솟값을 찾아내어 현재 인덱스에 위치한 원소와 바꾸기 때문에 각 사이클마다 한 번의 swap이 일어난다. 이러한 경우 동일한 값이 있을 때 위치 순서가 뒤바뀔 수 있다. (값이 같은 원소끼리 비교 하는 경우가 없이 최솟값만 찾아서 이동시키기 때문에 앞에 있던 원소가 뒤쪽으로 점프해 위치하는 경우가 생긴다.) 설명이 어렵다면 실제 코드를 짠 후 진행과정을 살펴보자. 바로 이해가 갈 것이다. 

 

공간복잡도는 마찬가지로 O(n)이다. 

 

면접용: 선택정렬에 대해 간단하게 설명해 보세요

선택정렬은 말 그대로 그 자리에 위치할 원소를 선택하고 치환하며 이뤄지는 정렬 알고리즘 입니다. 오름차순을 기준으로 했을 때 리스트의 첫 번째 인덱스에는 해당 리스트에서의 최솟값을 찾아 치환하고 그 다음 인덱스에서는 첫번째 인덱스를 제외한 리스트에서의 최솟값을 찾아 치환하고를 반복해 나가는 방식입니다. 

 

버블소트와 마찬가지로 항상 일정하게 O(n^2)의 시간복잡도를 가지며 해당 리스트 내에서 정렬을 진행하기 때문에 O(n)의 공간복잡도를 가지는 것이 특징입니다. 또한 불안정 정렬의 특성을 가집니다.

 

면접용: Bubble Sort와 Selection Sort의 차이점을 설명해 보세요

정렬을 위한 비교 횟수가 같기 때문에 시간복잡도는 O(n^2)으로 동일하지만 실제 원소의 교환이 일어나는 횟수는 훨씬 적기 때문에 많은 교환이 일어나야 하는 상태의 자료에서는 더 효율적인 방식이라고 볼 수 있습니다.

 

또한 버블소트는 같은 값을 가진 원소의 순서가 서로 바뀌지 않는 안정 정렬인데 반해 선택정렬은 같은 값을 가진 원소의 순서가 정렬 후 바뀔 가능성이 존재하는 불안정 정렬이라는 차이점이 있습니다.

 

 

 

3. 삽입 정렬 Insertion Sort

시간복잡도: 최선 - O(n)

                    최악 - O(n^2)

 

 자신의 왼쪽에 위치한 원소들과 비교하여 삽입할 위치를 지정한 후, 원소들을 한칸씩 뒤로 옮기고 지정된 자리에 원소를 삽입하여 정렬하는 알고리즘. 최선의 경우 O(n)이라는 극강의 효율성을 보여 다른 정렬 알고리즘의 일부로 사용되는 경우도 있다.

자신의 왼쪽에 위치한 값들과 비교해 자신보다 크면 오른쪽으로 한칸씩 밀어놓는다

여기부터는 정렬할 리스트의 상태에 따라 시간복잡도가 현저히 달라지는 알고리즘이다. 최악의 경우는 역으로 정렬되어 있을 경우이며, 이 때는 선택정렬과 마찬가지로 O(n^2)의 시간복잡도를 가진다. 최선의 경우는 이미 정렬이 완료되어 있는 리스트일때이고 이 때는 그냥 각 원소별로 한번씩만 쭉 탐색하면 되므로 O(n)의 시간복잡도를 가지게 된다. 보통 이미 정렬된 리스트를 다시 정렬하려고 하지는 않으므로 O(n)의 시간복잡도는 나올 일이 적지만, 리스트의 정렬 정도에 따라 시간이 점점 빨라지기 때문에 거품정렬과 선택정렬보다 한 단계 나아간 정렬 방식이라고 볼 수 있다. 

 

삽입정렬을 설명할 때 선택정렬의 방식을 조금 더 개선한 정렬 방식이라고 소개하는 곳이 있어 선택정렬과 동일하게 불안정 정렬이라고 생각하기 쉬운데, 삽입정렬은 안정 정렬이다..! 간단하게 생각해 보면 삽입정렬은 정렬을 진행하면서 자신보다 큰 원소들을 오른쪽으로 밀어내기만 하지 선택정렬처럼 치환하지 않는다. 따라서 원래 위치에 있는 원소보다 작거나 같은 값이 갑자기 리스트의 뒤쪽으로 이동할 수 없는 형태이다. 이해가 안된다면 역시 코드를 짜보는게 제일이다. 

 

삽입정렬도 마찬가지로 리스트 내에서 정렬이 진행되므로 공간복잡도는 O(n)이다.

 

면접용: 삽입 정렬에 대해 설명해 보세요

손 안의 카드패를 정렬하는 방법과 유사하다고 볼 수 있습니다. 특정 인덱스의 원소를 뽑은 후 그 인덱스의 왼쪽에 위치한 값들을 보며 해당 원소들이 뽑아놓은 원소보다 더 크면 오른쪽으로 한 칸씩 밀어낸 후, 빈 자리에 뽑아 놓은 원소를 삽입하는 정렬 방식입니다. 

 

원래 리스트의 정렬된 정도에 따라 O(n)까지 정렬시간이 빨라질 수 있다는 장점이 있습니다. (또는 거품정렬이나 선택정렬보다 상대적으로 빠르다는 장점이 있습니다.) 또한 안정 정렬 방식에 해당돼 값이 같은 원소의 순서가 바뀌지 않는다는 특정이 있습니다.

 

 

 

4. 퀵 정렬 Quick Sort

시간복잡도: 평균 - O(n log n)

                    최악 - O(n^2)

 

리스트 중 한 요소를 선택하고 이를 피벗pivot 이라 부른다. 피벗을 기준으로 작은 요소들은 왼쪽, 큰 요소들은 오른쪽으로 옮긴다. 피벗을 기준으로 나눈 양 리스트를 각각 동일한 방법으로 반복한다. 

피벗을 기준으로 양 리스트 분할

분할 정복의 개념을 도입한 정렬 알고리즘. 퀵 소트에서 가장 중요한 부분은 피벗을 무엇으로 잡느냐이다. 피벗값을 기준으로 양 리스트가 나뉘기 때문에 나뉘는 리스트의 길이가 서로 균등할 수록 분할 정복의 횟수가 줄어든다고 볼 수 있다. (한쪽은 끝났는데 다른쪽이 아직 진행중이면 다른쪽이 끝날때 까지 기다려야 하고 이는 전체적인 소요 시간의 증가로 이어진다.) 따라서 최선의 경우에는 딱딱 반씩 리스트가 나뉠 때이고 시간복잡도는 O(n log n)에 해당한다. 반대로 최악의 경우에는 피벗이 리스트의 최대 or 최솟값일때이며 이 떄는 O(n^2)의 시간복잡도를 가진다. 

순환 호출의 깊이가 전체 시간을 좌우한다고 보면 된다

또 다른 특징으로 퀵 정렬은 불안정 정렬이다. 피벗으로 정한 값과 같은 값이 있다면 그 두 개의 값 중 어느 윈소를 피벗으로 두느냐에 따라 둘의 위치가 달라지기 때문에 같은 값의 순서를 보장할 수 없다.

 

퀵 정렬은 물어볼 포인트가 다양하기 때문에 분할 정복, 피벗, 시간복잡도, 불안정 정렬 등의 키워드를 머릿속에 담아 두고 정렬 과정을 찬찬히 살펴보면 좋을 것 같다.

 

 

 

5. 병합 정렬 Merge Sort

시간복잡도: O( n log n)

 

퀵 정렬과 마찬가지로 분할 정복 개념을 도입하였고, 요소들을 쪼갠 후 다시 합병시키면서 정렬해 나가는 방식이다.

합병을 진행할 때 합병의 대상이 되는 두 리스트가 각 영역에 대해서 이미 정렬이 되어 있기 때문에 단순히 두 리스트를 순차적으로 비교하며 정렬할 수 있다.

원소를 일일이 분할한 후 병합하며 정렬을 진행

퀵 정렬과 비교해서 물어볼 가능성이 많다. 같은 분할 정복 기법의 정렬방식이지만, 병합정렬은 안정 정렬에 해당한다.

또한 병합정렬은 정렬하려는 레코드가 배열의 형태인지 연결리스트의 형태인지에 따라 필요한 자원의 차이가 달라진다. 

배열의 형태일 때 병합정렬을 사용하려면 임시 배열이 필요하다(위 그림 참조) 또한 크기가 클 때에는 이동 횟수가 많으므로 매우 큰 시간적 낭비를 초래할 수 있다. 따라서 병합정렬은 연결리스트 형태 레코드의 정렬에 효과적이다.

 

면접용: 퀵 소트와 머지소트는 어떠한 차이점이 있나요?

퀵 소트와 머지소트는 둘 다 분할 정복 기법을 사용한 알고리즘이지만 퀵 소트는 임의 접근, 머지소트는 순차 접근의 성질을 가지고 있어 각각 배열 형태와 연결리스트 형태의 정렬에 효과적입니다. 임의 접근과 순차 접근의 성질에 의해 퀵 소트는 불안정 정렬, 머지소트는 안정 정렬의 특성을 지니고 있기도 합니다.

 

 

 

6. 힙 정렬 Heap Sort

시간복잡도: O(n log n)

 

완전 이진트리를 기본으로 하는 힙Heap 자료구조를 기반으로 한 정렬 방식이다. 오름차순 정렬에는 최소 힙, 내림차순 정렬에는 최대 힙 구조를 이용한다. 

우선순위 큐에 사용되는 알고리즘으로 전체 리스트가 있을 때 힙 정렬을 시행하는 것 보단 힙 구조로 존재하는 리스트에 새로운 원소를 추가하거나 임의의 원소를 삭제하였을 때 어떠한 과정으로 다시 정렬이 진행되는지를 숙지하고 있는 것이 좋다. 

새로운 원소를 추가할 때

퀵정렬과 병합정렬의 성능이 좋기 때문에 힙 정렬 자체의 사용빈도가 높지는 않지만 힙 형태의 자료구조가 많이 활용된다. 또한 동일한 값의 요소를 넣을 때 트리 구조의 상태에 따라 요소가 자리하는 위치가 달라지기 때문에 불안정 정렬에 해당한다.

 

 

이 외에도 기수정렬(Radix Sort)와 계수정렬(Count Sort) 등이 있지만 상대적으로 중요도가 낮은 정렬 방식이고, 계수 정렬은 따로 포스팅을 올린 적이 있어 생략하기로 했다. 이렇게 정리해놓고 면접 전에 마지막으로 한 번씩 훑고 가면 좋을듯..!

 

 

참조:

tech-interview-for-developer https://github.com/gyoogle/tech-interview-for-developer

어썸오 개발 블로그  https://wisdom-and-record.tistory.com/57

Heee's Development Blog https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html