[게임 프로그래머 입문 올인원] STL Algorithms : 퀵정렬 (79강)

e. 퀵 정렬 (중요)

1) 퀵 정렬이란?

 

🌟 평균적으로 매우 빠른 속도를 보이는 정렬 알고리즘

 

• 분할 정복(divide and conquer) 기반
• 재귀적으로 배열을 분할하고 정렬하는 방식으로 동작

 

👉 분할 정복에 대한 내용은 d. 병합정렬에 작성되어있음

[게임 프로그래머 입문 올인원] STL Algorithms : 기본정렬 (78강)

 

💥 최악의 경우 시간 복잡도가 O(n^2)가 될 수있어 데이터 특성에 따라 잘 사용해야 함

 

2) 알고리즘

1. 분할(Divide): 배열에서 하나의 요소를 기준(pivot)으로 선택, 기준보다 작은 요소들은 왼쪽, 큰 요소들은 오른쪽
2. 정복(Conquer): 분할된 부분 배열에 대해 재귀적으로 퀵 정렬을 수행
3. 결합(Combine): 아무 작업도 수행할 필요가 없음. 부분 배열이 이미 정렬되어 있기 때문에 별도의 작업이 필요하지 않음

 

1) low는 오른쪽, high는 왼쪽으로 이동함, 피벗은 맨 왼쪽이나 오른쪽 둘 중 하나로 선택

 

2) 중간에 이렇게 멈췄다면 두개의 데이터를 교체함

여기도 바꿔줌

 

3) 여기까지가 한턴이 끝남, 여기서보면 5는 거의 중간값임

 

4) 같은 행위를 왼쪽, 오른쪽을 나눠서 실행하면 된다

 

3) 코드

 

시간복잡도 : 0(n)

 

시간복잡도 : 0(n log n)

 

사용한다면 이렇게

 

🧡 시간복잡도 복잡한 정도

가면갈수록 안좋다

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버 -

)