Tag: sort

0

Merge sort algorithm

합병 정렬(merge sort)합병 정렬은 분할정복 알고리즘이며 길이가 N인 리스트를 길이가 1인 리스트로 쪼개고 다시 쪼개진 각각의 리스트를 정렬하며 합병해 최종적으로 정렬된 리스트를 가지게 된다. 함수의 구조를 보면 알겠지만, 중앙 위치를 찾고 중앙 위치를 기준으로 좌측, 우측을 나눠 재귀 호출된다. 재귀 종료 조건은 start < end의 조건에 맞지 않는다면 더 나뉠 수 없다고 판단하여 쪼개는 과정이 종료된다. 최종적으로 마지막 merge함수를 이용해 각 리스트를 합병한다. 중요한 점은 이때 임시버퍼를 사용해야 하는데, 만약 임시버퍼를 사용할 수 없는 조건이라면 합병 정렬은 사용할 수 없다.

0

Quick sort algorithm

퀵 정렬 알고리즘퀵 정렬은 피벗을 기준으로 좌/우에 자신보다 큰/작은 값을 몰고, 문제를 조금씩 나눠가며 정렬을 하게 된다. 최악의 경우(항상 피벗이 모든 값 중 가장 작은 경우) O(n^2)를 가지는 상황이 나올 수 있지만, 확률적으로 그럴 일은 적기에 평균적으로 O(NlogN)의 시간복잡도를 가진다.