알고리즘/알고리즘
퀵정렬(Quick Sort)의 개념 및 구현
퀵정렬(Quick Sort)이란? 퀵정렬은 분할정복에 기반한 알고리즘이다. 분할정복이란 전체를 공략하는 대신 전체를 구성하는 구성 요소들을 나누어 잘게 쪼개진 적을 공략하는 개념이다. 퀵 정렬은 아래와 같은 과정으로 분할 정복을 이용해 정렬을 한다. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소들은 순서에 관계없이 무조건 기준 요소의 왼편에, 큰 값은 오른편에 위치시킨다. 1에서 나눈 데이터 집합들을 다시 1처럼 임의의 기준 요소를 선택하고 같은 방법으로 데이터 집합을 분할한다. 1,2 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻는다. 이를 토대로 예시를 들어보겠다. 요소 5를 기준으로, 5보다 작은 요소는 왼쪽, 5보다 큰 요소는 오..
