JS 퀵정렬

퀵정렬: 가장 빠른 정렬 알고리즘중 하나이다. in place 방법과 아닌 방법이 있지만 실제로 in place 방법을 많이 사용한다.

 

Basic Quick Sort - Not in place 

-분할 정복을 사용한 알고리즘이다.

- 정렬하는데 가장 간단한 배열은 요소가 없거나 하나만 있는 배열이다. 모든 배열이 기본 배열이 될 때까지 큰배열을 나눠야 한다.

-퀵정렬에서는 요소 하나를 기준 원소인 pivot으로 설정한다. 기준 원소의 왼쪽에는 기준 원소보다 작은 값의 배열을 놓고 오른쪽에는 기준 원소보다 큰 값을 놓는다.

-pivot왼쪽에 놓여진 기준 원소보다 작은 배열에서 위와 같은 방법으로 다시 pivot을 설정하고 배열을 pivot을 기준으로 나눈다. 이것을 반복하면 원소가 하나만 있는 배열에 남는다.

 

51397 일때 pivot은 5

[13]   5(pivot)  [97]

1(pivot)3   9(pivot) 7

13579 

 

1.기준 원소를 고른다.(첫번째 요소를 기준 원소로 하였다).

2.배열을 기준 원소보다 작은 원소의 배열과 큰원소의 배열, 이렇게 2개의 하위 배열로 분할한다.

3.하위 배열에 대해 재귀적을 퀵정렬을 호출한다.

 

-in place 방법이 아니기 때문에 별도의 메모리 공간이 필요한다. 데이터의 양이 많으면 공간적인 낭비가 심해져 잘 쓰이지 않는다. 퀵 정렬을 할 경우에 중복되는 데이터는 순차적으로 pivot에 넣으면 되기 때문에 정렬전 중복 데이터의 순서가 바뀌지 않는 stable 한 정렬을 구현할 수 있다. 

원소의 0번째 요소를 pivot으로 잡는다.

left와 right배열을 새로 만든후 

0번째 요소 다음 요소부터 순회하면 pivot과 값을 비교하여

left 배열,right 배열에 데이터를 push 한후 

하위 배열에 대해 다시 재귀 호출을 하면서 3 배열을 합친다.

 

 

In place Quick Sort

-정렬되지 않은 데이터에서 가운데 원소를 pivot 으로 설정하고 가장 왼쪽 요소와 가장 오른쪽 요소가 시작점이다.

 

가장 왼쪽부터 값을 pivot값을 비교하여 pivot보다 큰 값이 나타날때까지 칸을 오른쪽으로 이동한다.

가장 오른쪽부터 값을 pivot값을 비교하여 pivot보다 작은 값이 나타날 때까지 칸을 왼쪽으로 이동한다.

pivot보다 큰 왼쪽 값과 pivot보다 작은 오른쪽 값을 서로 교환한다. 

 

왼쪽 인덱스가 오른쪽 인덱스보다 커지면 이동을 멈추고 그 자리에서 두 배열로 갈라서 각 배열에 위와 같은 방식으로 재귀 호출하여 정렬한다. 

 

메모리 공간이 절약 된다. 왼쪽과 오른쪽 값을 교환하는 과정에서 중복 값의 위치가 바뀔 수 있으므로 unstable한 정렬방법이다.

 

 

 

 

Big O

worst case: O(n^2)

best case: O(nlog2n)

퀵 정렬은 대개의 경우 매우 좋은 성능을 보여준다. 최선의 경우에는 스택의 크기가 O(log2n)이고 각 스택마다 요소의 개수만큼 검색하므로 총O(n)을 t순회하기 때문에 결과적으로 시간 복잡도는 O(nlog2n)이다.

최악의 경우에는 스택의 크기가 O(n)이 되고 O(n)번 순회하므로 O(n^2)이란 시간이 소요된다.

 

이미 정렬된 배열의 경우 7번의 재귀 호출을 한끝에 정렬이 완료되었으나

뒤섞여있던 배열은 5번의 재귀 호출을 한 끝에 정렬이 완료되었다.

일반적인 경우에는 최선의 경우와 같은 실행 속도를 가지며 평균적으로 O(nlog2n)실행 시간을 가지는 매우 빠른 정렬 방법이다.

 

https://im-developer.tistory.com/135?category=846746