항해 99 4주차를 끝내며

항해 99

    알고리즘 4주 과정 중, 벌써 3주차가 끝이 났다. 이번 주차는 정렬과 함께한 주차였다. 버블 정렬, 선택 정렬, 삽입 정렬, 퀵 정렬, 병합 정렬, 그리고 힙 정렬까지 배웠다. 힙은 이번 주차 처음에 배웠던 힙 자료구조를 이용한 sort 방법이다. 각각의 정렬 방법들은 각기 다른 접근 방법을 통해 구현하였고, 이에 따라 서로 다른 시간 복잡도를 보인다. 여기서도 하나 개인적으로 특이하다고 느낀 점은, 같은 알고리즘으로 구현된 코드라고 할지라도, 최선의 경우와 최악의 경우에 따라서 그 시간 복잡도가 달라지는 것이었다. 

 

    버블 정렬의 경우, 모든 숫자 각각에 대하여, 그 외의 숫자들과 비교하여 제 자리를 찾아주는 식으로 접근하였다. 앞과 뒤를 비교하여 앞이 뒤보다 뒤에 있어야 하는 경우, 앞과 뒤의 위치를 바꿔주는 식으로 전체에 대하여 연산을 하여 가장 뒤에 존재할 원소를 찾아주고, 다시 그 바로 앞에 나올 원소를 찾으러 다시 한번 연산을 시작하는 식이다. 버블 정렬의 최악의 경우와 일반적인 경우 모두 n**2의 시간 복잡도를 가지고 있어 실질적으로 잘 이용되지 않는 알고리즘이다. 

 

    선택 정렬은 버블 정렬과 상당히 유사하다. 버블 정렬의 경우, 앞에서부터 비교를 시작하여 뒤에서부터 정렬을 완성시킨다면, 선택 정렬은 앞에서부터 비교를 시작하여 앞에서부터 정렬을 완성시킨다. 숫자를 오름차순으로 정리한다면, 각각의 자리에 대해서 아직 자리가 결정되지 않은 원소들의 최소값을 찾아서, 그 값을 채워주는 식이다. 선택 정렬 또한 버블 정렬과 마찬가지로 n**2의 시간 복잡도를 보이기 때문에, 실질적으로 거의 이용되지 않는 알고리즘이라고 할 수 있다.

 

    삽입 정렬은 최초에 하나의 원소를 정렬된 리스트라고 보고, 그 정렬된 리스트에 다른 원소들을 규칙에 맞게 하나씩 끼워넣는 방식으로 정렬을 진행하는 것이다. 삽입 정렬 또한 일반적인 경우와 최악의 경우 모두 n**2의 시간 복잡도를 가져 잘 이용되지 않는다.

 

    퀵 정렬은 정렬 대상 배열의 임의의 원소를 pivot으로 하여 그 기준점에 대하여 정렬을 하고, 다시 허술하게 정렬된 집단들 안에서 새로운 기준점을 잡아서 정렬을 진행하는 방식이다. 일반적으로 pivot은 가장 마지막 원소로 설정하는 듯 한데, 이 경우 오름차순 정렬을 한다고 했을 때 이미 정렬된 배열이 정렬 대상으로 들어오게 된다면, n**2의 시간복잡도를 보이는 단점을 가진다.

    여기서 한가지 더 적자면, 파이썬의 경우 내장 정렬 알고리즘은 tim sort라는 알고리즘으로 이루어져 있다. tim sort의 기본적인 아이디어는 우리가 실무에서 사용하는 배열은 무작위적인 것이 아니라, 실제로는 부분적으로 정렬되어 있는 데이터일 확률이 높다는 것이다. 이를 고려하여 퀵 정렬에 대해서 생각해본다면, 최악의 경우를 제외하면 n log n의 시간 복잡도를 보이는 퀵 정렬이지만, 그 약점은 생각보다 더 자주 노출될 수 있는 것이다.

 

    병합 정렬은 컴퓨터 공학의 천재로 이름 높은 폰 노이만이 고안한 알고리즘으로 잘 알려져 있다. 더 이상 쪼갤 수 없을 때 까지 배열을 쪼개면, 단일 원소로만 이루어진, 정렬된 배열이 만들어진다. 그 이후에 다이 정렬된 배열들을 병합하는 과정을 거쳐 하나의 정렬된 완전한 배열이 만들어진다는 것이 이 알고리즘의 핵심이다. 가장 주요하고 놀라운 아이디어는 단일 원소를 가진 배열은 이미 정렬된 것과 다름 없으므로, 배열을 쪼개고 또 쪼갠 후 다시 병합을 통해 정렬을 실시하면, 빠른 시간 안에 정렬을 완성할 수 있다는 것이다. 병합하는 과정에서는, 병합의 대상이 되는 각각의 배열이 모두 정렬된 상태이므로, n의 시간 안에 모든 병합을 마무리지을 수 있고, 배열을 2개씩 병합하면 log n 번 병합을 실시해야 하므로 (완전 이진 트리의 구조를 떠올리면 이해가 쉬울 것이다.), n log n 의 시간이 소요된다. 이는 최악의 경우와 최선의 경우, 일반적인 경우 모두에 대해서 그런 것으로, 이런 강점이 있어 병합 정렬은 실제로 자주 쓰이는 강력한 정렬 알고리즘으로 자리잡고 있다. 

 

    힙 정렬은 앞서 배운 힙 자료구조를 이용해 정렬을 실시하는 것이다. 힙 자료구조란, 느슨하게 정렬된 형태를 이루고 있는 일종의 트리 자료구조로, 최대 힙과 최소 힙으로 분류할 수 있다. 최대 힙과 최소 힙 모두 각 하나의 원칙을 만족하는 형태로 트리 자료구조를 이룬다. 최대 힙은 모든 node에 대해서 부모 노드의 값은 해당 노드의 자식 노드의 값보다 더 크다는 것이고, 최소 힙은 그 반대이다. 이런 식으로 노든 노드를 유지한다면, 최대값과 최소값을 최대 힙과 최소 힙에서 바로바로 뽑아낼 수 있고, 이 과정에서 망가진 힙 자료구조를 다시 되돌리는 데에 log n의 시간이 소요된다. 즉, 최소 힙이나 최대 힙에서 순차적으로 값을 뽑아내어 배열에 추가하면 저절로 정렬이 된 배열을 얻을 수 있는 것이다. 

 

 

각각의 정렬 알고리즘이 최선, 평균, 최악의 경우에 보이는 시간 복잡도와 메모리 소요.