퀵 정렬(Quick Sort)

퀵 정렬 알고리즘 개념

---

과정 설명

• 배열의 한 원소를 피벗으로 선택
• 피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를 오른쪽에는 피벗보다 큰 원소를 배치
• 피벗을 제외한 양쪽의 두 배열을 각각 정렬
• 배열이 더 이상 나누어지지 않을 때까지 실행

과정 상세 설명

피벗을 제외한 배열의 왼쪽과 오른쪽을 같이 검사한다.

배열의 왼쪽에는 피벗보다 작은 수가 있어야 하므로 왼쪽에서 검사할 때는 피벗보다 큰 수를 찾으면 멈추고

배열의 오른쪽에는 피벗보다 큰 수가 있어야 하므로 오른쪽에서 검사할 때는 피벗보다 작은 수를 찾으면 멈춘다.

양쪽의 검사가 멈추게 되면 그 두 수의 위치를 바꾼다.

 

4

3

7

1

5

6

2

4를 피벗으로 설정한다.

 

 

4

3

7

1

5

6

2

3과 2를 검사한다.

3<4이므로 왼쪽 검사는 멈추지 않고 2 <4이므로 오른쪽 검사는 멈추게 된다.

 

 

4

3

7

1

5

6

2

4

3

2

1

5

6

7

7을 검사한다.

이번에는 7>4이므로 왼쪽 검사도 멈추게 된다.

양쪽의 검사가 멈추게 되면 두 수의 위치를 바꾼다.

 

 

4

3

2

1

5

6

7

1<4이고 6>4이므로 지나간다.

 

 

4

3

2

1

5

6

7

5에서 4<5이므로 왼쪽 검사는 멈추고 오른쪽 검사는 계속 진행된다.

 

 

4

3

2

1

5

6

7

왼쪽 검사가 오른쪽 검사를 지나치게 되면 검사는 중지된다.

 

 

4

3

2

1

5

6

7

1

3

2

4

5

6

7

마지막으로 오른쪽 검사 부분과 피벗의 위치를 바꾼다.

이렇게 피벗의 왼쪽과 오른쪽을 정렬했다.

다음에는 왼쪽 배열과 오른쪽 배열을 같은 방법으로 정렬한다.

 

퀵 정렬 알고리즘 시간복잡도

---

Best: nlogn

Avg: nlogn

Worst: n^2(원소들이 역순으로 정렬되어 있을 때)

 

개선방법

---

원소들이 역순으로 정렬되어 있을 때는 알고리즘이 효율을 내기 힘들다.

그러므로 처음에 첫 번째 원소와 중간 원소의 값을 교환한 다음 첫 번째 원소를 피벗으로 지정하게 되면 만약의 경우를 대비할 수 있다.

+ 첫 번째 원소, 중간 원소, 마지막 원소의 값을 비교해서 중간 값을 피벗으로 사용하는 방법을 많이 쓰고 있다고 한다.

 

References

---

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

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

https://mygumi.tistory.com/308

퀵소트 알고리즘 :: 마이구미