[알고리즘] 정렬 알고리즘 선택

1. 버블 정렬 

 

첫 요소와 두번째 요소를 비교하고 작은 것을 앞으로, 그리고 두번째와 세번째를 비교해서 작은 것을 앞으로를 반복.

그러면 한번 실행했을 때 가장 큰 값이 뒤로 가기 때문에 그 다음 실행에선 마지막을 제외하고 같은 것을 반복.

그러면 비교 횟수가 처음엔 n-1번부터 시작해서 하나씩 줄어서 마지막에 1번을 한다.

1부터 n-1까지 더하면 식은 n(n-1)/2 다. (등차수열의합 공식)

 

첫 요소부터 비교하면서 마지막 요소까지 큰 값이 올라가는게 버블같다고 해서 버블 정렬.

정렬 중 무식하고 비효율적이다. 하지만 구현이 간단하다는 장점이 있다.

 

 

2. 삽입 정렬

 

버블 정렬이 뒤에서 부터 정렬한다면 삽입정렬은 앞에서부터 정렬한다. 처음에 맨 앞 두개를 비교해서 자기보다 작은 값  뒤에 삽입하고 범위를 세개, 네개로 늘려 반복한다. 버블 정렬이 정렬 대상을 늘릴 때 삽입 정렬은 정렬 대상을 줄인다.

비교 횟수는 1부터 n-1까지 더한 값으로 버블 정렬과 같다. 하지만 삽입 정렬은 정렬되어 있을 경우는 비교를 하지 않는다.

그래서 버블 정렬보다 낫다. 그래도 시간복잡도가 O(N^2)이기 때문에 여전히 느리다.

 

 

3.  퀵 정렬

 

퀵 정렬은 큰 문제를 잘게 나눠서 해결하는 분할 정복 원리를 이용한다. 특정 요소 기준 작은 것은 모두 왼쪽으로 큰 것은

모두 오른쪽으로 보내고 이것을 반복한다. 그래서 이것을 어떻게 구현할 것인가? 리스트에서는 기준 요소 앞 뒤로 보내는 것이 어려운 일이 아니지만 배열에서는 생각을 좀 해봐야 한다.

 

먼저 왼쪽->오른쪽으로 가면서 기준요소보다 큰 값을 찾고, 오른쪽->왼쪽으로 가면서 기준요소보다 작은 값을 찾은 후

둘을 바꾼다.  그것을 반복하고 둘이 만나면 기준요소를 왼쪽 데이터 집합의 마지막 요소와 교환한다. 분할정복은 재귀함수를 이용해서 구현할 수 있다.

 

퀵정렬의 속도는 이상적일 경우 한번에 데이터 집합이 두개씩 쪼개져서 8개로 나눌 때 3번의 재귀호출, 16번일 때 4번의 재귀호출해서 log2n로 빠르고 최악의 경우에도 버블, 삽입 정렬과 속도가 비슷하다. 평균 속도는 nlog2n이다.

 

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog