알고리즘 이론 깨부수기 Sort

Bubble Sort

n개의 원소를 가진 배열을 정렬할 때 In-place sort로 인접한 두개의 데이터를 비교해가면서 정렬을 진행하는 방식입니다.

가장 큰 값을 배열의 맨 끝에다 이동시키면서 정렬하고자 하는 원소의 개수 만큼을 두 번 반복하게 된다.

Selection Sort

n 개의 원소를 가진 배열을 정렬할 때, 계속해서 바꾸는 것이 아니라 비교하고 있는 값의 index 를 저장해둔다.

그리고 최종적으로 한 번만 바꿔준다. 하지만 여러 번 비교를 하는 것은 마찬가지이다.

Insertion Sort

n개의 원소를 가진 배열을 정렬할 때, i번째 배열을 정렬할 순서라고 가정하면 0부터 i-1까지의 원소들은 정렬되어 있다는 가정하에, i번째 원소와 i-1번째 원소부터 0번째 원소까지 비교하면서 i번째 원소가 비교하는 원소보다 클 경우 서로의 위치를 바꾸고, 작을 경우 위치를 바꾸지 않고 다음 순서의 원소와 비교하면서 정렬해줍니다. 이 과정을 정렬하려는 배열의 마지막 원소까지 반복해줍니다.

Merge Sort

Merge Sort는 더이상 나누어지지 않을 때 까지 반 씩(1/2) 분할하다가 더 이상 나누어지지 않은 경우 원소 하나를 반환합니다.

이 때 반환된 값끼리 비교하여 비교 결과를 기반으로 정렬되어 임시 배열에 저장된다. 그리고 이 임시 배열에 저장된 순서를 합쳐진 값으로 반환한다.

Heap Sort

binary heap 자료구조를 활용할 sorting방법에는 두 가지 방법이 존재합니다.

하나는 정렬의 대상인 데이터들을 힙에 넣었다가 꺼내는 원리로 Sorting 을 하게 되는 방법

기존의 배열을 heapify(heap 으로 만들어주는 과정)을 거쳐 꺼내는 원리로 정렬하는 방법

heap에 데이터를 저장하는 시간 복잡도는 O(log n)이고, 삭제 시간 복잡도 또한O(log n)이 됩니다.

힙 자료구조를 사용하여 Sorting 을 하는데 time complexity 는 O(log n)이 됩니다.

이 정렬을 하려는 대상이 n 개라면 time complexity 는 O(nlogn)이 됩니다.

Quick Sort

Divide 과정에서 pivot이라는 개념이 사용됩니다.

입력된 배열에 대해 오름차순으로 정렬한다고 하면 이 pivot 을 기준으로 좌측은 pivot 으로 설정된 값보다 작은 값이 위치하고, 우측은 큰 값이 위치하도록 partition됩니다.

이렇게 나뉜 좌, 우측 각각의 배열을 다시 재귀적으로 Quick Sort 를 시키면 또 partition 과정이 적용됩다.

이 때 한 가지 주의할 점은 partition 과정에서 pivot 으로 설정된 값은 다음 재귀과정에 포함시키지 않아야 합니다.

이미 partition 과정에서 정렬된 자신의 위치를 찾았기 때문입니다.

Quick Sort's worst case

정렬이되어있고 pivot값을 최소값 또는 최대값을 주었을 때 시간 복잡도 O(N^2)을 가지게 된다.

Balanced-partitioning

특정 위치의 원소를 pivot 으로 설정하지 않고 배열 내의 원소 중 임의의 원소를 pivot 으로 설정하면 입력에 관계없이 일정한 수준의 성능을 얻을 수 있다.