HLDEC.NET

[code cpp:nocontrols]
#define swap(x,y,t) {t=x; x=y; y=t;} // swap 매크로 함수
[/code]

[code cpp:nocontrols]
typedef struct _NODE {
 int begin, end;
 struct _NODE* link;
}NODE;
[/code]

[code cpp:nocontrols]
NODE* PushStack(NODE* ptr, int begin, int end)
{
 NODE* temp = (NODE*)malloc(sizeof(NODE));
 temp->begin = begin;
 temp->end   = end;
 temp->link = ptr;
 return temp;
}
[/code]

[code cpp:nocontrols]
NODE* PopStack(NODE* ptr)
{
 NODE* temp = (NODE*)malloc(sizeof(NODE));
 NODE* out = NULL;
 if (ptr) {
  temp = ptr;
  out = ptr->link;
  free(temp);
 } return out;
}
[/code]

[code cpp:nocontrols]
// 3-준위 퀵정렬 함수 (시스템 오버플로우를 방지하기위해 재귀호출을 피하고 리스트-스택 을 이용함)
// 3-준위 : 처음 중간 끝. 세 기준을 잡아 최저 최고값은 양 옆끝에 위치시키고 중간값을 피벗으로 검사
int Std3Quik(int data[], int begin, int end)
{
 int pLeft, pRight, pivot, nextPivot, temp; // 필요 변수 정의
 NODE *stack = NULL; // 리스트-스택 (이하, 스택) 정의
 stack=PushStack(stack, begin, end); // 스택에 정렬해야 할 부분 상위 노드로 넣기
 while(1) {
  if (!stack) break; // 스택 검사 (스택이 비어있으면 종료)
  begin = stack->begin; end = stack->end; // 시작점, 끝점 스택에서 꺼내어 정의
  stack=PopStack(stack); // 스택 상위노드 제거
  if ((end-begin)<100) {   // 정렬해야 할 부분 100개 미만일 경우
   DbSelect(data, begin, end); // 100개 미만일 경우 퀵정렬보다 선택 정렬이 더 효과적임
  } else {
   pivot = (begin+end)/2; // 중위 피벗 기준 설정
   // 각 기준 (begin, pivot, end) 정렬
   if (data[begin] > data[pivot])  swap(data[begin], data[pivot],  temp);
   if (data[begin] > data[end]) swap(data[begin], data[end], temp);
   if (data[pivot] > data[end]) swap(data[pivot], data[end], temp);
   swap(data[pivot], data[end-1], temp); // 정렬된 중위 피벗 end-1 위치로 이동
   pLeft = begin+1; pivot = end-1; pRight = nextPivot = end-2; // 각 포인팅 변수 초기화
   while(1) {
    // 조건(죄측은 피벗보다 작게, 우측인 피벗보다 크게) 에 맞으면 교환
    if (data[pivot] <= data[pLeft] && data[pivot] > data[pRight]) swap(data[pLeft], data[pRight], temp);
    // 조건(교환된, 혹은 교환되지 않은 우측이 피벗보다 크면)에 맞으면현재 위치를 다음 피벗의 위치로 설정
    if (data[pivot] <= data[pRight]) nextPivot = pRight;
    // 조건(두 포인팅이 더이상 움직일 필요가 없을경우)에 맞으면 교환 종료
    if (abs(pRight-pLeft)<2) break;
    // 각 조건에 맞으면 각 포인팅 이동
    if (data[pivot] > data[pLeft]) pLeft++;
    if (data[pivot] <= data[pRight]) pRight--;
   }
   // 단, 모든 교환이 끝났을때 좌측 포인팅이 피벗보다 더 클경우 다음 피벗 위치를 죄측 포인팅으로 설정
   if (data[pivot] <= data[pLeft]) nextPivot = pLeft;
   // 피벗과 다음 피벗의 값 교환 (이동된 해당 피벗은 영구 보존)
   swap(data[pivot], data[nextPivot], temp);
   // (3-준위 이기 때문에) 가까운 기준 끼리의 거리가 3 미만일 경우 재 교환 한다
   if ((end-nextPivot)<3 || (nextPivot-begin)<3) {
    stack=PushStack(stack, begin, end);
   } else { // 그렇지 않으면 새로운 기준으로 다시 교환한다.
    stack=PushStack(stack, nextPivot+1, end);
    stack=PushStack(stack, begin, nextPivot-1);
   }
  }
 }
 return 1;
}
[/code]

[code cpp:nocontrols]
#include <list>
using namespace std;
[/code]

[code cpp:nocontrols]
typedef struct tagEDGE{
 int  iNodeA;
 int  iNodeB;
 int  iWeight;
public:
 bool operator < (const struct tagEDGE &vector) {
  if (iWeight < vector.iWeight) return 1;
  else return 0;
 }
 void OutputScreen() {
  printf("( %d, %d : %d )\n", iNodeA, iNodeB, iWeight );
 }
}EDGE;
[/code]

[code cpp:nocontrols]
void ConvertData(const int iTree[SIZE][SIZE], std::list<EDGE> &listData)
{
 EDGE edge;
 
 for (int i=1; i<SIZE; i++) {
  for (int j=0; j<i; j++) {
   if (iTree[i][j]!=INFINITE) {
    edge.iNodeA = i;
    edge.iNodeB = j;
    edge.iWeight = iTree[i][j];
    listData.push_back(edge);
   }
  }
 }
 listData.sort();
}
[/code]

[code cpp:nocontrols]
void Prim(std::list<EDGE> &listData, std::list<EDGE> &listOutput)
{
 std::list<EDGE>::iterator it;
 EDGE edgeMin;
 int iMinWeight;
 bool *pBoundNode = new bool[SIZE];
 memset(pBoundNode, 0, sizeof(bool)*SIZE);
 it = listData.begin();
 listOutput.push_back(*it);
 pBoundNode[it->iNodeA] = TRUE;
 pBoundNode[it->iNodeB] = TRUE;
 while(listOutput.size() < SIZE-1) {
  iMinWeight = INFINITE;
  for (int i=0; i<SIZE; i++) {
   if (pBoundNode[i] == TRUE) {
    it = listData.begin();
    while(it != listData.end()) {
     if (it->iNodeA == i && pBoundNode[it->iNodeB] == FALSE ||
      it->iNodeB == i && pBoundNode[it->iNodeA] == FALSE ) {
      if (iMinWeight > it->iWeight) {
       iMinWeight = it->iWeight;
       edgeMin = *it;
      }
     }
     ++it;
    }
   }
  }
  if (iMinWeight != INFINITE) {
   pBoundNode[edgeMin.iNodeA] = TRUE;
   pBoundNode[edgeMin.iNodeB] = TRUE;
   listOutput.push_back(edgeMin);
  }
 }
 delete[] pBoundNode;
}
[/code]

[code cpp:nocontrols]
#include <list>
using namespace std;
[/code]

[code cpp:nocontrols]
typedef struct tagEDGE{
 int  iNodeA;
 int  iNodeB;
 int  iWeight;
 bool bVisited;
public:
 bool operator < (const struct tagEDGE &vector) {
  if (iWeight < vector.iWeight) return 1;
  else return 0;
 }
 void OutputScreen() {
  printf("( %d, %d : %d )\n", iNodeA, iNodeB, iWeight );
 }
}EDGE;
[/code]

[code cpp:nocontrols]
void ConvertData(const int iTree[SIZE][SIZE], std::list<EDGE> &listData)
{
 EDGE edge;
 
 for (int i=1; i<SIZE; i++) {
  for (int j=0; j<i; j++) {
   if (iTree[i][j]!=INFINITE) {
    edge.iNodeA = i;
    edge.iNodeB = j;
    edge.iWeight = iTree[i][j];
    edge.bVisited = FALSE;
    listData.push_back(edge);
   }
  }
 }
 listData.sort();
}
[/code]

[code cpp:nocontrols]
void Kruscal(std::list<EDGE> &listData, std::list<EDGE> &listOutput)
{
 std::list<EDGE>::iterator it, itClear, itNest;
 std::list<int> queueNode;
 std::list<int>::iterator itQueue;
 int iCount;
 it = listData.begin();
 while (it != listData.end() ) {
  listOutput.push_back(*it);
  // Looping check
  for (itClear = listOutput.begin(); itClear != listOutput.end(); ++itClear) itClear->bVisited = FALSE;
  itNest = --listOutput.end();
  queueNode.push_back(itNest->iNodeA);
  queueNode.push_back(itNest->iNodeB);
  itNest->bVisited = TRUE;
  itQueue = queueNode.begin();
  while(itQueue != queueNode.end()) {
   iCount = 0;
   itNest = listOutput.begin();
   while(itNest != listOutput.end()) {
    if (iCount < 2) {
     if (itNest->iNodeA == *itQueue) {
      if (itNest->bVisited == TRUE) {
       iCount++;
      } else {
       queueNode.push_back(itNest->iNodeB);
       itNest->bVisited = TRUE;
      }
     } else if (itNest->iNodeB == *itQueue) {
      if (itNest->bVisited == TRUE) {
       iCount++;
      } else {
       queueNode.push_back(itNest->iNodeA);
       itNest->bVisited = TRUE;
      }
     }
    }
    ++itNest;
   }
   if(iCount < 2)++itQueue;
   else {
    queueNode.erase(queueNode.begin(), queueNode.end());
    break;
   }
   queueNode.pop_front();
  }
  if (iCount >= 2) listOutput.pop_back();
  ++it;
 }
}
[/code]

[code cpp:nocontrols]
#define SWAP(x,y,t) {t=x;x=y;y=t;}
[/code]

[code cpp:nocontrols]
void MergeSort(int iArray[], int iTemp[], int iStart, int iEnd)
{
    if (iStart < iEnd) {
        int iMid = (iStart + iEnd)/2;
        MergeSort(iArray, iTemp, iStart, iMid);
        MergeSort(iArray, iTemp, iMid + 1, iEnd);
        Merge(iArray, iTemp, iStart, iMid, iEnd);
    }
}
void Merge(int iArray[], int iTemp[], int iLow, int iMid, int iHigh)
{
    int h = iLow, i = iLow, j = iMid+1, k;
    while ((h <= iMid) && (j <= iHigh)) {
        if (iArray[h] <= iArray[j]) { iTemp[i] = iArray[h]; h++; }
        else { iTemp[i] = iArray[j]; j++; } i++;
    }
    if (h > iMid) {
        for (k=j; k<=iHigh; k++) {
            iTemp[i] = iArray[k]; i++;
        }
    }
    else {
        for (k=h; k<=iMid; k++) {
            iTemp[i] = iArray[k]; i++;
        }
    }
    for (k=iLow; k<=iHigh; k++) iArray[k] = iTemp[k];
}
[/code]