'자료구조'에 해당되는 글 4건

  1. 2010.05.14 큐 만들기
  2. 2010.05.13 스택만들기
  3. 2009.12.17 병합정렬 & 퀵 정렬 비교 및 기수정렬
  4. 2009.12.16 퀵 정렬

큐는 스택과는 다르게 FIFO 방식으로 먼저 들어온 녀석이 먼저나가는 방식이다.

그냥 일반큐를 만들어보았다.

구조체를 이용해 front, rear, count, q 를 하나로 통합시켰다.

typedef struct{
 int q[QueueSize+1];
 int front;
 int rear;
 int count;
}queue;


front에서는 Dequeue할 원소를 가르키고 있고 rear에서는 삽입할 자리를 가르키고있다. 또 count를
이용해 Deque나 Enqueue가 가능한지 확인하도록 사용하였다.

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

연결리스트를 이용한 이진트리의 순회방법  (0) 2010.05.14
트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
Posted by 아몰라

댓글을 달아 주세요

예전에 자료구조 배울때 못해보았던

스택만들기를 해보았다.

스택에 대한 간단한 이해만 있으면 어렵지 않게 만들 수 있는 것 같다.

현재 스택에 위치는 top 변수를 만들어서 사용했고

스택에 크기는 10으로 고정하였다.


맨 위에 3은 View가 3번이라서 그렇다. 스택이 아니다 -_-;;;

요 근래 계속 느끼는건데 c랑 c++에 대한 이해가 부족하다.
기본적인 배열이나 int 나 char나 뭔가가 부족하다. 확실하게 못짚겠다.
기초플러스 한번도 제대로 안봤는데 짬내서 봐야겄다.

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

트리의 배열표현 방법  (0) 2010.05.14
큐 만들기  (0) 2010.05.14
스택만들기  (0) 2010.05.13
LCD 디스플레이  (0) 2010.05.13
여행(The Trip)  (0) 2010.05.11
지뢰찾기  (0) 2010.05.03
Posted by 아몰라

댓글을 달아 주세요


병합 정렬

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 아몰라

댓글을 달아 주세요


퀵 정렬

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 아몰라

댓글을 달아 주세요

이전버튼 1 이전버튼