[자료구조] Circulr Queue / Sort(bubble, selection)

환형버퍼(원형버퍼,원형큐)

 

 환영 버퍼란: 고정된 크기의 버퍼를 양 끝이 연결된 것처럼 사용할 수 있게 해주는 자료 구조이다. 환영 버퍼를 사용하   면 단순 배열을 거의 성능저하 없이 사용이 가능하다.

 

  원형큐는 선형큐에서 발전 된것인데

  선형 큐는  선입선출 을 기반으로 만든 것이다

  선형 큐는 n개의 메모리를 가지고 있는데 메모리가 꽉 차서 overflow가 될 때 데이터 를

  더 사용하게 되지 못하니 0으로 되돌아가서 다시 데이터 를 쓰게 만든것 이 원형 큐 이다.

 

환형버퍼의 동작                   

 

빈 원형 버퍼를 준비한다

 

빈 원형 버퍼에 1을 입력한다 (이때 시작의 위치는 중요하지 않다)

그리고 2와 3을 추가로 입력하면 다음과 같은 3개의 입력을 갖는다.

이중 2개의 입력된 값이 출력되면 1,2가 사라지고 3만 남게 된다 

이 버퍼의 크기는 7개이므로 7개가 입력되면 꽉차게 된다.

* 예시의 버퍼가 7개인 것이지 환영 버퍼의 제한이 7개는 아니다. 

 

SORT 정렬

버블정렬(BUBBLE SORT)

버블 정렬의 개념

서로 인접한 두 데이터를 검사하여 정렬 하는 알고리즘이다.

*두개의 데이터를 비교하여 크기가 순서대로 되어있지 않으면 교환한다

 

 

배열에 7,4,5,1,3 이 저장이 되어있다 가정해보자

1회차에서 7과4를 비교하고 7이 더크니 뒤로보낸뒤 7과 5를 비교하고

7이 더크니 뒤로 보낸다. 끝까지 가거나 더큰 숫자가 나오는 시점에서 종료

가장 큰 데이터가 끝으로 가게되니 맨 끝에 있는 데이터는 비교할 필요가없다.

2회차에서는 4와 5를 비교하여 교환하지 않고 5와1을 비교하여 5를 뒤로

보낸다 이를 반복하고 3,4,회차를 반복하면 숫자크기 대로 배열이 완성이 된다.

 

장점- 구현이 간단하다

 

단점- 구현이 간단하지만 비교하려는 데이터의 개수가 많아 질수록  연산의 횟수가 점점 늘어나기 때문에

        성능에 저하가 일어난다. 그래서 잘 사용되지 않고 데이터가 적은 경우에만 주로 사용한다.

 

 

선택 정렬 SELECTION SORT

선택 정렬의 개념

제자리 정렬- 입력 배열이외에 다른 추가 데이터를 요구하지 않는 정렬 방법이다.

해당 순서에 데이터를 넣을 위치는 이미 정해져 있고 어떤 데이터를 넣을지 선택하는 알고리즘이다.

 

배열에 9,6,7,3,5 가 저장 되있다고 가정해보자

오름차순으로 정렬시 1회차에 첫번째 데이터 9를 두번째 데이터 부터 마지막 데이터 까지 비교하여

가장 작은 값을 첫번째 위치에 옮겨 놓는다 이 과정에서 데이터가 5개니까 4번 비교를 한다.

2회차에서 두번째 데이터 6을 세번째 데이터부터 마지막 데이터 까지 비교하여

가장 작은 값을 2번째 위치에 옮겨 놓는다 4개의 데이터니까 3번 비교한다.

위 과정을 완료가 될때까지 반복한다.

 

장점- 자료 이동 횟수가 미리 결정 되있다.

 

단점-안정성이 떨어진다.

       즉 값이 같은 데이터가 있는 경우에 상대적인 위치가 변경될수가 있다.

        선택 정렬 또한 간단하지만 버블 정렬과 같이 비효율 적이다.