분할정복법(divide & conqver )
- 여러 알고리즘의 기본이 되는 해결방법으로, 기본적으로는 엄청나게 크고 방대한 문제를 조금씩 나눠가면서 용이하게 풀 수 있는 문제 단위로 나눈 다음 그것들을 다시 합쳐서 해결하자는 개념에서 출발했다.
-> 퀵 정렬, 병합정렬
- 퀵 정렬
-
평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 방법
-
전체리스트를 2개의 부분 리스트로 분할하고, 각가의 부분 리스트를 다시 퀵정렬하는 전형적인 분할정복법을 사용
- 퀵 정렬 소스코드
#include <stdio.h>
#define swap(x,y,t) ((t)=(x), (x)=(y), (y)=(t))
int partition(int list[], int left,int right)
{
int pivot,temp,low,high;
low = left;
high= right+1;
pivot=list[left];
do
{
do
{
low++;
}while(list[low]<pivot && low<=right);
do
{
high--;
}while(list[high]>pivot);
if(low<high)
{
swap(list[low],list[high],temp);
}
}while(low<high);
swap(list[left],list[high],temp);
return high;
}
void quicksort(int list[], int left,int right)
{
if(left<right)
{
int q=partition(list, left, right);
quicksort(list,left,q-1);
quicksort(list,q+1,right);
}
}
int main()
{
int list[6]={10,2,20,7,50,1};
quicksort(list,0,5);
for(int i=0; i<6; i++)
{
printf("%d ",list[i]);
}
return 0;
}1. swap(x, y, t) 매크로 정의
#define swap(x, y, t) ((t) = (x), (x) = (y), (y) = (t))이 매크로는 x와 y의 값을 교환하는 역할을 한다.
t는 임시 변수로, x의 값을 잠시 저장하고 나중에 y로 바꿔주는 역할을 한다.
2. partition 함수
int partition(int list[], int left,int right)
{
int pivot,temp,low,high;
low = left;
high= right+1;
pivot=list[left];
do
{
do
{
low++;
}while(list[low]<pivot && low<=right);
do
{
high--;
}while(list[high]>pivot);
if(low<high)
{
swap(list[low],list[high],temp);
}
}while(low<high);
swap(list[left],list[high],temp);
return high;
}배열을 분할하여 피벗(pivot)을 기준으로 두 개의 부분 배열로 나누는 역할을 한다. 피벗 값보다 작은 값들은 왼쪽에, 큰 값들은 오른쪽에 배치된다.
매개변수:
list[]: 정렬하려는 배열.
left: 배열의 왼쪽 끝 인덱스.
right: 배열의 오른쪽 끝 인덱스.
동작 과정
pivot = list[left]: 피벗 값으로 배열의 첫 번째 요소를 선택한다.
↓
low는 피벗 바로 오른쪽에서 시작하고, high는 배열의 끝에서 시작한다.
↓
low는 피벗보다 큰 값을 찾고, high는 피벗보다 작은 값을 찾습니다. 이 값들을 찾으면 두 값을 서로 교환한다.
↓
low와 high가 교차하지 않을 때까지 이 과정을 반복한다.
마지막으로 피벗과 high 위치의 값을 교환한다.
↓
high를 반환하여 피벗의 최종 위치를 반환한다. 이 위치를 기준으로 배열을 다시 분할할 수 있다.
3. quicksort 함수
void quicksort(int list[], int left,int right)
{
if(left<right)
{
int q=partition(list, left, right);
quicksort(list,left,q-1);
quicksort(list,q+1,right);
}
}퀵 정렬을 재귀적으로 구현
매개변수:
list[]: 정렬할 배열.
left: 배열의 시작 인덱스.
right: 배열의 끝 인덱스.
동작 과정
partition 함수를 호출하여 피벗을 기준으로 배열을 분할한다.
↓
분할된 배열의 왼쪽 부분(left부터 pivot-1)과 오른쪽 부분(pivot+1부터 right)을 각각 다시 퀵 정렬한다.
↓
재귀적으로 계속해서 배열을 나누고 정렬하는 과정이 반복된다.
4. main 함수
int main()
{
int list[6] = {10, 2, 20, 7, 50, 1};
quicksort(list, 0, 5);
for(int i = 0; i < 6; i++)
{
printf("%d ", list[i]);
}
return 0;
}list 배열을 선언하고 초기화
↓
quicksort 함수로 배열을 정렬
↓
정렬이 완료된 후, 배열의 각 요소를 출력
전체 동작 요약
배열 [10, 2, 20, 7, 50, 1]을 퀵 정렬로 정렬하고
↓
정렬 과정에서 피벗을 기준으로 배열을 두 개의 부분 배열로 나누고,
↓
재귀적으로 각 부분 배열을 정렬한다.
최종 출력되는 배열은 [1, 2, 7, 10, 20, 50] 이다.