Computer Science

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

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

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

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

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

병합 정렬

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

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

퀵 정렬과 비교!

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

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




count 정렬 

분석법을 이용해 표 작성

 

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
      첫자리 두번째 세번째

퀵 정렬

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이 다 확정되면 종료