[Quick Sort] linked list를 퀵정렬로 정렬하기

보통 퀵정렬 예제들을 보면 배열로 구현이 되어있고 링크드 리스트로 구현된 코드를 찾아 보기힘들다..

왜 그런지는 직접 구현해보면 알수 있다.

힌트를 주자면 index와 관련있다. 퀵정렬에서는 index 관리를 많이 하지만 

모두가 알다시피 링크드 리스트로는 index관리가 힘들다.

어째튼 저도 링크드 리스트로 구현된 퀵정렬을 여기저기 찾다가 국내에서는 못찾고 외국에서 찾았지만 시원치가 못하다. 그래서 아래에 본인이 직접 구현한 알고리즘을 올립니다.

아래 코드에 추가 설명

int mode 는 오름차순과 내림차순 변수를 받는 값입니다. 1이면 오름차순 2이면 내림차순

처음 퀵정렬 함수를 부를때 파라메터로 HEAD와 TAIL을 주면 됩니다.

그리고 index과 동일한 열할을 하는 int형 변수 2개를 주어 이동하게 됩니다.

또 swap()함수는 두포인터의 data 값만 변경시키는 함수입니다.

data값이 아닌 포인터를 변경하게되면 swap 부분만 어마어마하게 커질지도 모릅니다.

그렇게되면 퀵소트가 아닌 슬로우소트가 되어버릴지도 모릅니다. 하....하....(필자 생각)

swap( * node1, * node2){

int tmp = node1->data;

node1->data = node2->data;

node2->data = tmp;

}

void sort_quick(int mode, struct D_NODE *Left, struct D_NODE *Right ) 

{

// key_node : pivot를 나타냄, Right값을 가짐.

// 링크드리스트이기때문에 배열과 같이 index를 나타내는 부분이 없음.

// -> 그래서 nLeft, nRight, nTotal 값으로 index를 check.

// 해당 index는 list_count() 함수로 구함.

struct D_NODE *Key_node, *left_node, *right_node;

int nLeft=1,nRight, nTotal;

nTotal = list_count(Right,Left,Right);

nRight = nTotal-1;

// 정렬 해야되는 노드 수가 1개일경우 재귀함수 종료

if(nRight <= 0) return;

Key_node =  Right;

left_node = Left;

right_node = Right->list.pre_node;

while(1)

{

//mode 1 : 오름차순 정렬

//mode 2 : 내림차순 정렬

if(mode ==1)

{

// key값을 기준으로 left 값과 right값 비교하면서 이동

while( left_node->number < Key_node->number)

{

left_node = left_node->list.next_node;

nLeft++;

}

while( right_node->number > Key_node->number)

{

if(nRight <=1 || right_node->list.pre_node ==NULL )

break;

right_node = right_node->list.pre_node;

nRight--;

}

}else if(mode== 2)

{

while( left_node->number > Key_node->number)

{

left_node = left_node->list.next_node;

nLeft++;

}

while( right_node->number < Key_node->number)

{

if(nRight <=1 || right_node->list.pre_node ==NULL )

break;

right_node = right_node->list.pre_node;

nRight--;

}

}

// while 종료 조건 

if(nLeft >= nRight)

break;

// 정렬

swap_node(left_node, right_node);

left_node = left_node->list.next_node;

nLeft++;

right_node = right_node->list.pre_node;

nRight--;

}

// 기준이 되는 key을 변경

swap_node(Key_node, left_node);

// key(pivot) 값을 기준으로 왼쪽 리스트 정렬시 재귀

if(left_node->list.pre_node != NULL && nLeft-1 > 0)

if(left_node->list.next_node != Left && Left->list.pre_node !=left_node)

sort_quick(mode, Left, left_node->list.pre_node);

// key(pivot) 값을 기준으로 오른쪽 리스트 정렬시 재귀

if(left_node->list.next_node != NULL && nLeft < nTotal )

if((left_node->list.pre_node != Right) &&  (Right->list.next_node != left_node))

sort_quick(mode, left_node->list.next_node, Right);

}

이번코드는 실제로 돌려본거라 에러부분은 없을겁니다.