C++ - 더블 링크드리스트로 구현한 삽입, 버블정렬

지난번처럼 설명을 자세하게 적고 싶었는데.. 하다보니 코드가 너무 길어졌네요 ;ㅁ;

리스트를 이용하여 구현한 삽입정렬, 버블정렬입니다.

배열로 구현한 삽입정렬(http://topnanis.tistory.com/12)과 버블정렬(http://topnanis.tistory.com/11)은  링크를 참조하세요.

싱글로 할 걸 굳이 더블 링크로 구현 한 이유는.. 퀵정렬을 구현하려다.. 그만 두었기 때문이죠.. 막판에 넣은 스왑 디파인아까워..ㅠ

퀵정렬시에는 재귀 함수에 인자값으로 배열의 크기(+피봇), 시작지점이 필요하므로 더블링크드가 더 적합하겠다 싶었습니다(배열쪽이 훨씬 편리한 것 같아요)

 

아래에 소스 첨부하였습니다.  

sort.cpp

#include <iostream>

#include <Windows.h>

#define SWAP(x,y,t) (t=x), (x=y), (y=t)                 //스왑을 정의(못써먹음,아까워;ㅁ;)

using namespace std;

class Node         //노드를 정의

{

public:

int val;

Node *head;

Node *tail;

};

class Link         //더블리스트클래스

{

private:

bool BubbleOrderAscending();         //버블(오름)

bool BubbleOrderDescending();         //버블(내림)

void InsertOrderAscending();         //삽입(오름)

void InsertOrderDescending();         //삽입(내림)

void Col(int color);

void ShowAll();         //링크출력

public:

Node *lHead;         //링크전체의 헤더

Node *tempPoint;         //생성시 동적할당을 위한 노드

Link()         //초기화

{

lHead = new Node();

lHead->head=NULL;         //초기화 하지 않으면 값 넣을때 에러발생

lHead->tail=NULL;         //초기화 하지 않으면 검색시 에러발생

}

void AddLilk(int val)             //노드추가

{

cout<<"add"<<endl;

tempPoint= new Node();         //노드 생성시 동적할당

lHead->head=tempPoint;         //링크 헤더연결

tempPoint->val=val;         //링크 값

tempPoint->tail=lHead;         //링크 테일연결

lHead=tempPoint;         //주소저장

ShowAll();

}

void revShowAll()         //링크 역출력

{

cout<<endl<<"Show Reverse"<<endl;

Node *schPoint= lHead;

while(schPoint->tail->val!=NULL) schPoint=schPoint->tail;

while(schPoint->head!=NULL)

{

if(schPoint->val>=100)Col(15);         //값 크기에 따라 색상(10:녹, 14:황, 15:백)

else if(schPoint->val>=10)Col(14); else Col(10);

cout<<schPoint->val<<"->";

schPoint=schPoint->head;

}

cout<<schPoint->val<<"->";

Col(15);

cout<<endl;

}

void InsertUp() //삽입정렬(오름)스위치

{

cout<<endl<<"Ascending(Insert)"<<endl;

InsertOrderAscending();

}

void InsertDown() //삽입정렬(내림)스위치

{

cout<<endl<<"Decending(Insert)"<<endl;

InsertOrderDescending();

}

void BubbleUp() //버블정렬(오름)스위치

{

cout<<endl<<"Ascending(bubble)"<<endl;

while(BubbleOrderAscending());

}

void BubbleDown() //버블정렬(내림)스위치

{

cout<<endl<<"Decending(bubble)"<<endl;

while(BubbleOrderDescending());

}

};

void Link::InsertOrderAscending()

{

tempPoint=lHead; //기준포인트

tempPoint=tempPoint->tail;         //삽입정렬 초기- 두 수를 비교하기 위해 기준블럭을 한 칸 이동 

while(tempPoint->tail!=NULL)

{

ShowAll();

//노드를 이용한 for문 참조_ serchP는 시작지점에서 기준블럭전 까지 비교하기 위한 포인터

for(Node *serchP = lHead; serchP->val!=tempPoint->val; serchP=serchP->tail)

{

if(serchP->val>tempPoint->val)

{

int tempVal = serchP->val;

serchP->val = tempPoint->val;

tempPoint->val = tempVal;

}

}

tempPoint=tempPoint->tail;

}

ShowAll();

}

void Link::InsertOrderDescending()

{

tempPoint=lHead;

tempPoint=tempPoint->tail;

while(tempPoint->tail!=NULL)

{

ShowAll();

for(Node *serchP = lHead; serchP->val!=tempPoint->val; serchP=serchP->tail)

{

if(serchP->val<tempPoint->val)

{

int tempVal = serchP->val;

serchP->val = tempPoint->val;

tempPoint->val = tempVal;

}

}

tempPoint=tempPoint->tail;

}

ShowAll();

}

bool Link::BubbleOrderAscending()

{

ShowAll();

bool isContinue=false;

tempPoint= lHead;

while(tempPoint->tail->tail!=NULL)

{

if(tempPoint->val>tempPoint->tail->val)

{

isContinue=true;

int temp=tempPoint->val;

tempPoint->val=tempPoint->tail->val;

tempPoint->tail->val=temp;

}

tempPoint=tempPoint->tail;

}

return isContinue;

}

bool Link::BubbleOrderDescending()

{

bool isContinue=false;

tempPoint= lHead;

while(tempPoint->tail!=NULL)

{

if(tempPoint->val<tempPoint->tail->val)

{

isContinue=true;

int temp=tempPoint->val;

tempPoint->val=tempPoint->tail->val;

tempPoint->tail->val=temp;

}

tempPoint=tempPoint->tail;

}

ShowAll();

return isContinue;

}

void Link::ShowAll()

{

Node *schPoint= lHead;

while(schPoint->tail!=NULL)

{

if(schPoint->val>=100)Col(15);else if(schPoint->val>=10)Col(14); else Col(10);

cout<<schPoint->val<<"->";

schPoint=schPoint->tail;

}

Col(15);

cout<<endl;

}

void Link::Col(int color) 

{

int bgcolor=NULL;

color &= 0xf;

bgcolor &= 0xf;

SetConsoleTextAttribute(GetStdHandle(STD_OUTPUT_HANDLE), (bgcolor << 4) | color);

}

int main() //메인

{

Link *link = new Link();

link->AddLilk(86);

link->AddLilk(1);

link->AddLilk(13);

link->AddLilk(4);

link->AddLilk(11);

link->AddLilk(226);

link->AddLilk(104);

link->BubbleUp();

link->BubbleDown();

link->revShowAll();

link->InsertUp();

link->InsertDown();

return 0;

}