Problem Solving/Algorithm, DS
[알고리즘] 퀵정렬 Quick Sort (C++ 구현)
📌 퀵정렬 퀵정렬은 가장 널리 쓰이는 정렬 알고리즘으로 말 그대로 빠른 정렬이 가능하다. 퀵 정렬도 병합정렬과 마찬가지로 분할정복기법을 이용한 알고리즘이다. 퀵 정렬의 핵심 아이디어는 특정 원소를 기준으로 작은 데이터와 큰 데이터를 분류한다는 것이다. 이렇게 되면 특정 원소를 기준으로 순서가 결정되며 분류된 작은 데이터와 큰 데이터 안에서 각각 기준 원소를 다시 정해 재귀적으로 쪼개나가면서 정렬해나간다. 병합정렬과 마찬가지로 단위를 쪼개나가는 아이디어이므로 분할정복기법이라고 할 수 있다. 이때 생각해봐야 할 것은 기준이 되는 원소(pivot)를 어떻게 정하느냐 인데, 1) 첫번째 원소를 기준으로 하거나 2) 랜덤으로 원소를 선택한다 첫번째 원소를 기준으로 할 경우 이미 정렬된 리스트의 경우 피봇의 한쪽에..
