정렬

정렬의 종류

• 크게 비교식과 분산식 정렬로 나눌 수 있다.
• 비교식 정렬의 종류로는 버블, 선택, 삽입 정렬이 있다.
• 분산식 정렬의 종류로는 합병, 퀵 정렬이 있다.

비교식 정렬

다른요소와 비교를 통해 정렬하는 방식

버블정렬

서로 인접한 두 요소를 검사하여 정렬하는 알고리즘으로 O(n^2)의 시간복잡도를 가진다.

선택정렬

선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘으로 O(n^2)의 시간복잡도를 가진다.

삽입정렬

선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘으로 O(n^2)의 시간복잡도를 가진다.

분산식 정렬

요소를 분산하여 정렬하는 방식으로 주요 개념으로는 분할 정복이 있다.
분할정복: 문제를 작은 2개의 문제로 분리하고, 더 이상 분리할 수 없을 때 처리한 후 합치는 전략으로 다양한 알고리즘에서 사용된다.

합병정렬

분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘으로 O(nlogn)의 시간복잡도를 가진다.

퀵 정렬

분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우 O(n^2)가 존재하는 불안정한 정렬이다. 일반적으로 O(nlogn)의 시간복잡도를 가지며 피벗을 기준으로 작은 값을 왼쪽, 큰 값을 오른쪽으로 배치하면서 정렬한다.