알고리즘 (12) 썸네일형 리스트형 Chap3-2 퀵정렬(QuickSort) 3.2 퀵정렬 퀵 정렬은 분할 정복 알고리즘으로 분류하지만 분할할 수 없을 때까지 분할 후 합병이 아닌 분할 정복, 분할 정보의 과정을 반복하는 알고리즘 2개의 부분 문제로 분할, 각 부분 문제의 크기가 일정하지 않음(비균등 분할) -a = 2이고 b의 값은 정해지지 않음 퀵정렬 알고리즘의 아이디어 순환의 방법으로 과정이 수행된다. 배열의 원소 중 하나를 “피봇”이라는 이름으로 선정 피봇이 위치한 곳을 기준으로 작은 것은 피봇의 왼편으로 큰 것을 피봇의 오른편으로 보낸다. 피봇을 제외한 왼쪽 부분에서 새로운 피봇을 정하여 이 과정을 반복 왼쪽 부분에서 더 이상 정렬할 것이 없다면 오른쪽 부분에서 새로운 피봇을 찾아 이 과정을 반복한다. 피봇 피봇을 기준으로 오른쪽 왼쪽이 다 정렬되면 피봇의 자리는 고정된.. Chap 3. 분할 정복 알고리즘 분할정복 알고리즘 : 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘 부분 해(분할)를 취합( =정복)하여 원래 문제의 해를 얻음 부분문제와 부분해 더 이상 분할할 수 없을 때까지 분할한다. → 분할한 문제들의 해를 취합 → 부분 취합을 다시 취합 (1) 분할 과정 [상황] 입력 = n 분할 = n을 3개로 분할 각각 분할된 부분 문제의 크기 = n/2 *질문 = 여기서 n을 3개로 분할한 것이므로 각각 분할된 부분 크기는 n/3이 아닌가? ⇒ n이라는 전체 크기를 3등분하여 반으로 나눈다는 의미 3등분을 전체에 대한 것이 아니라 전체의 반의 반이 하나의 등분으로 생각하면 된다. [ 이를 일반화 하면 ] 입력 = n 분할 = n을 b개로 분할 각각 분할된 부분 문제의 크기 = n/a.. 이전 1 2 다음
