[알고리즘]퀵 정렬

아.. 간만에 쓴다.. 솔직히 버블이나 삽입같은거야 그냥 쉽게 쉽게 설명이 되는데 이분부터는 재귀씨가 들어가셔서 애로사항이 꽃필수도 있다.

우선 코드를 보면

void QuickSort(vector & iVec, int first, int last)
{
if(first >= last) // 값이 1개만 들어오거나 안들어왔을 경우를 위한

//문장
return;
if((last - first) <>

//를 사용
InsertSort(iVec, first, last);
SwapInt(iVec[first], iVec[last]); // 처음 인덱스의 값을 마지막으

//로 보냄
// 굳이 보낼 필요는 없지만, 보내고 싶어서 보냄
int pbot = iVec[last]; // 처음 값을 인덱스로 결정
--last;
int f = first; // 피봇보다 작은 값의 범위를 나타내줄 변수
int l = last; // " 큰 "
while(f <= l) { while(iVec[f] <>= pbot) // 피봇보다 작은 값이 나올때까지 이동
{
--l;
}
if(f <>= l이면 파티션이 제 자리를 찾았으므로 swap하지않

//는다.
SwapInt(iVec[f], iVec[l]);
}
SwapInt(iVec[++last], iVec[f]); // 피봇값을 제자리로 위치 시킴
QuickSort(iVec,first, f - 1); // 피봇보다 작은 쪽 파티션을 다시 재

//귀적으로 호출
QuickSort(iVec,f + 1, last); // " 큰 "
}

아.. 예전에 만든 코드를 가져다 붙였더니 엉망이다..

가장먼저 보이는 것은 vector로 배열을 사용하지 않고 벡터를 썼다. 배열을 써도 무관하다. 알고리즘과는 전혀 상관없다.

알고리즘을 설명하면 정렬하려는 범위내에서 피봇을 하나 선택한 후 그 피봇보다 작은 것은 앞쪽에 크거나 같은 것은 뒤쪽에 놓는다. 이 과정이 끝나면 피봇값은 정확한 위치에 놓이게된다.

그 다음 자신보다 작은부분과 큰부분에 다시 위의 것을 적용한다.

이것이 기본적인 컨셉이다.

이것을 구현하는 방식이 책이나 문서마다 조금씩 다른 경우가 있는데, 큰 차이는 없다. 위의 코드에서 사용한 방식을 보면

3 5 6 1 6 8 9 // 시작값

9 5 6 1 6 8 3 // 처음 값을 피봇으로 선택후 맨 뒤와 교체

f l p //p는 피봇값 f,l은 인덱스를 가리키는것으로 뒤에설명

9 5 6 1 6 8 3 // 앞쪽부터 피봇값보다 크거나 같은값이 올때까지 f를

f l p //이동

// 이동이 없다.

9 5 6 1 6 8 3 // 뒤쪽부터 피봇값보다 작은 값이 올 때까지 l을 이동

f l p// 1까지 이동

1 5 6 9 6 8 3 // f <>

f l p // 교체

// f > l이라면 끝낸다

1 5 6 9 6 8 3 // 다시 f를 이동

f l p // 5까지 이동

1 5 6 9 6 8 3 // l을 이동

l f // 1까지 이동

// f > l 이므로 현재 단계를 끝낸다.

1 3 6 9 6 8 5 // 피봇값과 f를 교체

l p f // 교체

// 피봇값의 앞 뒤로 다시 알고리즘을 실행한다.

// 앞쪽은 1 하나로 종료

// 위에 설명했으므로 바뀌는 순서만 표시

6 9 6 8 5

5 9 6 8 6

5 6 6 8 9 // 피봇값은 두번째

// 앞쪽은 5 하나로 종료

6 8 9

9 8 6

6 8 9 // 피봇값은 첫번째

8 9

8 9

// 결과

1 3 5 6 6 8 9

알고리즘은 이런 식 이지만, 자료가 일정 수 이하일 경우

퀵정렬이 삽입정렬보다 정렬 시간이 더 걸리게 되므로

현재 정렬해야하는 원소의 수를 세어서 위의 코드의 경우 10개 미만이라면 삽입 정렬을 사용한다.

위의 예에서는 단지 퀵정렬이 이루어지는 방식을 보여주는 것으로

저정도 숫자라면 삽입 정렬을 사용한다