nomad-programmer

알고리즘 중에 분할 정복 알고리즘(Divide and Conquer Algorithm)이 있다. 어려운 문제를 작게 쪼개서(divide) 해결해 나가는(conquer) 것을 말한다. 대표적인 분할 정복 알고리즘인 퀵 정렬에 대해 알아보자. pivot은 정렬되지 않은 리스트에서 가운데 위치한 인덱스의 데이터를 말한다. 주의할 점은 인덱스가 아니라 데이터라는 것이다. start는 첫 번째 인덱스이고 end는 미자막 인덱스이다. left와 right는 각각 start와 end를 가리킨다. left 인덱스는 오른쪽으로 이동하고 right 인덱스는 왼쪽으로 이동한다. 목적은 pivot을 기준으로 왼쪽은 pivot보다 작은 데이터가 모이고, 오른쪽은 큰 데이터가 모이도록 만드는 것이다. 그렇게 하려면 left는 오..