병합 정렬

1. 분할!! 정렬이 안된 배열을 쪼갠다 [ 7, 5, 12, 18, 4, 9, 11] - 최소원소들이 될때까지 계속 병합정렬 호출

2. 병합!! 최소원소들을 합쳐가면서 병합시킨다.


퀵 정렬과 비교!

퀵 - 역순 , 적당히 정렬에서는 느리고 굉장히 어지러운 정렬에서는 효과를 발휘한다. 일반적으로 빠른 소트로 알려져있다.
     컴퓨터상에서는 평균보다 최악의 상황이 더 중요하다.

병합 - 실질적으로 빠른 정렬 ,  단점 : 메모리 사용량 ↑




count 정렬 

1

2

3

4

1

3

1

정렬전!


 

1

2

3

4

3개

1개

2개

1개

cnt =3

cnt =4

cnt =6

cnt =7

분석법을 이용해 표 작성

 

1

2

3

4

1

3

1

 

 

 

 

 

 

4

cnt--

1

2

3

4

1

3

1

 

 

 

 

 

3

4

cnt--
 

1

2

3

4

1

3

1

 

 

 

 

3

3

4

 cnt--

1

2

3

4

1

3

1

 

 

 

2

3

3

4

cnt--

1

2

3

4

1

3

1

 

 

1

2

3

3

4

cnt--

1

2

3

4

1

3

1

 

1

1

2

3

3

4

cnt--

1

2

3

4

1

3

1

1

1

1

2

3

3

4

cnt--

cnt==0 이 되고 정렬 끝  1 , 1, 1 ,2 ,3 ,3, 4




count
 카운트 소트를 이용한 radix sort(기수정렬)

121     121    121    121
753     753    753    275
275     473    473    473
473     275    275    753
      첫자리 두번째 세번째

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
연결리스트더미有  (0) 2009.12.16
퀵 정렬  (0) 2009.12.16
Posted by 아몰라

댓글을 달아 주세요

연결리스트


노드 - 데이터를 보관해준다!

head - 맨앞의 노드를 지칭
tail - 맨뒤의 노드를 지칭
head랑 tail은 위치정보만 가지고있다.(링크다!)

단일연결 - 어떠한 노드의 위치를 알수없다. (Stoker)
이중연결 - 어떠한 노드의 위치를 알수있다.


seek를 이용 seek<노드의값 이면 앞에 삽입하자!

Dummy 노드 있는게 더 좋다. 특정한 노드 사이에 저장이된다!


pushback - 맨 뒤에 보관한다.

1. in을 보관하는 노드 생성
2. tail 앞에 보관



Ehlist()                               //헤드랑 테일 초기화~
  {
   head = new EhNode();       //시작을 가르킬더미 생성
   tail = new EhNode();          //마지막을 가르킬 더미 생성
   head->af = tail;                
   tail->be = head;
   usage = 0;                      // 연결리스트의 개수를 알려준다
   
  }
  virtual ~Ehlist()
  {
   EhNode * ehnode = tail->be;  // 테일이 가르키는 노드의 옆에노드를 가르킨다.

   while(usage!=0)
   {
    tail->be = tail->be->be;       // 테일을 왼쪽왼쪽 가르키게 한다. 
    delete tail->be;                  // 테일 옆에 노드를 삭제
    usage--;
    
   }

   delete tail,head;
  }

  
  void push_back(T data)
  {
   EhNode * ehnode;
   ehnode = new EhNode(data);
   HangNode(ehnode, end().now); //노드를 넣을 데이터와 마지막 노드의 위치를 넘겨준다.
   usage++;

  }
  
  void insert(iterator at,T data)
  {
   EhNode * ehnode;
   ehnode = new EhNode(data);
   HangNode(ehnode, at.now);  //노드를 넣을 데이터와 선택위치를 넘겨준다.
   usage++;
  }

  
  void erase(iterator at)
  {
   EhNode * ehnode = at.now;
   ehnode->be->af = ehnode->af;
   ehnode->af->be = ehnode->be;
   usage--;
  }

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
연결리스트더미有  (0) 2009.12.16
퀵 정렬  (0) 2009.12.16
Posted by 아몰라

댓글을 달아 주세요


퀵 정렬

1. pivot을 선택한다.

2. pivot을 맨 앞(L)뒤(R)의 요소와 교환

3. pivot 보다 (L)에서 큰원소들을 찾는다.

4. pivot 보다 (R)에서 작은원소들을 찾는다.

5. 3~4에서 둘다 값을 찾으면 서로 값 교환한다.

6. L 과 R 이 만나게되면 pivot과 만나는 점을 교환하고 pivot을 확정한다.

7. pivot 왼쪽 quick sort - 원소 개수가 2개이상

   pivot 오른쪽 quick sort - 원소 개수가 2개이상

8. pivot이 다 확정되면 종료

'프로그래밍 기초 > 자료구조 & 알고리즘' 카테고리의 다른 글

지뢰찾기  (0) 2010.05.03
3n+1  (0) 2010.05.03
스케줄링 (라운드 로빈)  (0) 2009.12.17
병합정렬 & 퀵 정렬 비교 및 기수정렬  (0) 2009.12.17
연결리스트더미有  (0) 2009.12.16
퀵 정렬  (0) 2009.12.16
Posted by 아몰라

댓글을 달아 주세요