버블정렬(bubble sort), 퀵정렬(quick sort)

버블정렬(Bubble sort)

 

버블정렬은 다른말로 제자리정렬(in-place sort)라고도 하며 말 그대로 별도의 저장공간 필요없이 본 배열안에서 정렬이 이루어진다는 장점이 있다. 버블정렬의 정렬방법은 0번째 인덱스에 커서를 맞추는 것(커서의 인덱스좌표를 i로 선언)으로 시작하여 

 

1. i번째 인자와 인접한 인자(i+1)간의 값을 비교한다.

2. i번째가 더 크면 i+1번째 인자와 자리를 바꾼다.

3. i번째가 더 작거나 같으면 아무것도 하지 않는다.

4. 커서의 좌표, i를 1더해준다.

5. 해당 배열의 끝까지 1~3의 절차를 진행하는데 단 loop의 회차만큼 i는 배열 length에서 i를 뺀 만큼의 번째에 있는 값 까지만 비교한다.

6. 이 과정을 i가 length와 같게 될 때까지 진행한다. 같아지면 정렬된 배열이 완성되어 있다.

 

해당 정렬은 추가적인 저장공간이 필요가 없고 간단한 알고리즘으로 이루어지지만, 이 알고리즘의 시간복잡도 O(n)이 

 

O(n^2)으로 상당히 느려서 많은 양의 데이터를 정렬하는데 무리가 있다.

 

 

 

 

 

 

---

퀵정렬(Quick sort)

퀵정렬(quick sort)는 합병정렬과 비슷하나 대상 리스트를 무조건 반으로 쪼개는 대신 피봇(pivot)이라고 하는 기준값을 선택하고 기준값보다 작은 값만 들어 있는 리스트와 큰 값만 들어 있는 리스트로 나눈 수, 재귀 정렬한다. 합병정렬은 무조건 반으로 나누어 재귀 정렬하므로 추후에 합병 절차가 필요하지만, 퀵정렬은 피봇 값을 중심으로 작은 값과 큰 값을 따로 끼리끼리 나누는 수고를 미리 하고 재귀 정렬하므로 뒤에 합병할 필요가 없다.

 

알고리즘으로는 먼저 pivot을 정하는데 옆의 그림에서는 가장 앞의 숫자를 pivot으로 잡았다. 

1. pivot을 잡고 해당 pivot을 기준으로 작은 인자와 큰 인자를 따로 각각 두개의 배열에 저장한다.

2. 왼쪽과 오른쪽을 각각 quicksort로 재귀 호출하고 그 사이에 pivot을 넣어 quicksort(leftarr) + pivot + quicksort(rightarr)형식으로 반환한다.

 

버블정렬도 간단한 알고리즘이지만 해당 퀵정렬의 알고리즘도 매우 간단하다. 게다가 해당 알고리즘은 버블정렬보다 훨씬 빠르나,

최악의 경우(pivot이 최대값이거나 최솟값이라서 계속해서 한쪽의 배열에 모든 인자가 몰리는 경우)에는 O(n^2)의 시간이 걸린다.

하지만 보통이나 최적의 상황에서 각 두개의 배열에 인자값들이 고루들어가게 된다면 평균적으로 n*logn의 시간복잡도를 가지는데,

그렇다고 O(n)빅오표기법으로는 최악의 case에서의 시간복잡도를 가지므로,

퀵정렬는 O(n^2)이지만, Θ(nlogn)이라고 하는 것이 맞는 표현이다.