'삽입정렬'에 해당되는 글 2건

  1. 2012.06.01 C++ - 더블 링크드리스트로 구현한 삽입, 버블정렬 (1)
  2. 2010.05.15 C - 알고리즘 - 삽입정렬 (3)


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


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


배열로 구현한 삽입정렬(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;

}




신고
Creative Commons License
Creative Commons License
Posted by 준환이형님

댓글을 달아 주세요

  1. c++ 삽입 2014.04.14 19:07 신고 Address Modify/Delete Reply

    c++ 삽입정렬

코드가 길어 행을 줄였습니다. 이렇게 하면.. 예쁘지는 않지만~ (사랑스러워~)
삽입정렬은.. 마치 [왕자와 거지]게임 같아서 한번 내동댕이 쳐진 숫자는 밑바닥에서부터 자리를 찾아 쏙 넣어진답니다..(-_-?)

리스트를 이용한 삽입정렬은 링크를 참조하세요(http://topnanis.tistory.com/176)

그림을 보면-


#include <stdio.h>

#include <string.h>                                            //memmove함수사용


int main(void)

int temp=NULL;

int data_set[]={8,6,7,9,4,3,5,2,1,10};

for(int i=0; i<9; i++)

if(data_set[i-1]>data_set[i]) temp=data_set[i];  //정렬되지 않은 수를 temp에 태워 처음으로 보냄

else continue;


for(int j=0; j<i; j++)

{  

if(temp<data_set[j]) //자리를 찾았다면

{                                                               // 이사  될 자리- 예전자리 범위를 전체 우로 일보.

memmove(&data_set[j+1], &data_set[j], sizeof(data_set[0])*(i-j)); 

data_set[j]=temp;

break;

}

for(int i=0; i<10; i++) printf("%d ",data_set[i]);

return 0;

}



 

사로자바님의 말에 따르면 리소스의 사용은 [크기비교]가 아닌 [교환]에서 일어나는 것이랍니다. 교환횟수를 비교해 보았을때 삽입정렬은 뽀글정렬과 비교가 안될정도로 우수한 성능을 자랑하는군요 :D




저작자 표시
신고
Creative Commons License
Creative Commons License
Posted by 준환이형님

댓글을 달아 주세요

  1. mindle 2014.04.15 22:16 신고 Address Modify/Delete Reply

    memmove함수 사용 없이 작성하려면 어떻게 해야되나요 ?

  2. mindle 2014.04.15 22:16 신고 Address Modify/Delete Reply

    memmove함수 사용 없이 작성하려면 어떻게 해야되나요 ?

  3. mindle 2014.04.15 22:16 신고 Address Modify/Delete Reply

    memmove함수 사용 없이 작성하려면 어떻게 해야되나요 ?

티스토리 툴바