기수정렬 (Radix Sort) 기수정렬은 낮은 자리수부터 비교하여 정렬해 간다는 것을 기본 개념으로 하는 정렬 알고리즘입니다. 기수정렬은 비교 연산을 하지 않으며 정렬 속도가 빠르지만 데이터 전체 크기에 기수 테이블의 크기만한 메모리가 더 필요합니다. ■ 정렬 방식 1. 0~9 까지의 Bucket(Queue 자료구조의)을 준비한다. 2. 모든 데이터에 대하여 가장 낮은 자리수에 해당하는 Bucket에 차례대로 데이터를 둔다. 3. 0부터 차례대로 버킷에서 데이터를 다시 가져온다. 4. 가장 높은 자리수를 기준으로 하여 자리수를 높여가며 2번 3번 과정을 반복한다. 아래의 8개 데이터에 대하여 기수 정렬을 시도해 보겠습니다. 위의 그림과 같이 각 숫자에 해당하는 Queue공간을 할당하고 진행합니다. 먼저..

병합 정렬 (Merge Sort) 전체 원소를 하나의 단위로 분할한 후에 분할한 원소를 다시 병합하며 정렬해 나가는 방식입니다. ■ 정렬 방식 1. 정렬하고자 하는 데이터 집합을 반으로 나눈다. 2. 반으로 나누어진 하위 데이터의 개수가 2이상이면 1의 과정을 반복한다. 3. 같은 집합에서 나온 하위 데이터 둘을 정렬을 시도하면서 다시 병합합니다. 4. 원래의 데이터 집합이 될때까지 3의 과정을 반복합니다. - 분할과정 전체 데이터 크기(n=8)에서 반으로(n=4) 나눕니다. 이 과정에 대해서 데이터 집합의 크기가 1이 될 때까지 반복합니다. -병합과정 같은 집합에서 나온 하위 데이터집합 두개를 정렬과 동시에 병합을 시도합니다. 주목해야 할 점은 병합이 이루어진 데이터 집합에 대해서는 정렬이 이루어졌습니..

퀵 정렬 (Quick Sort) 기준이 되는 원소를 기준으로 하여 기준 원소보다 작거나 같은 값을 지닌 자료는 앞으로 큰 값을 진ㄴ 자료는 뒤로 가도록 하여 기준 원소를 중심으로 분할해가며 정렬을 진행하는 방식입니다. ■ 정렬방식 1. 기준이 되는 원소를 정합니다. 배열의 시작 원소를 pivot으로 설정합니다. 2. 좌우 인덱스를 지정합니다. 해당 인덱스는 다음을 의미합니다. - left : pivot 보다 큰 값을 찾으러 다니는 index - right : pivot 보다 작은 값을 찾으러 다니는 index - left_hold : pivot을 제외하고 정렬 대상의 시작점 - right_hold : pivot을 제외하고 정렬 대상의 끝점 3. left를 pivot보다 큰 값을 찾을 때 까지 이동합니다...

버블정렬 (Bubble Sort) 두 인접한 배열요소를 차례대로 검사를 하여 정렬을 하는 방식 ■ 정렬 방식 1. 배열의 가장 앞에서 인접한 두 개의 요소에 대하여 비교를 한다. (배열의 첫 번째 요소와 두 번째 요소) 2. 배열의 다음 인접한 요소(두 번째와 세번째를 비교를 한다.) 3. 배열의 끝까지 반복을 한다. 한 사이클이 끝나면 배열의 맨 끝에는 정렬된 요소 하나가 정렬이 된 채 자리잡는다. 4. 정렬이 된 마지막 요소를 제외한 나머지에 대하여 1,2,3 번 과정을 반복한다. 정렬이 된 상태 비교 원소 5 4 3 2 1 최초 정렬이 이루어지지 않은 상태의 배열입니다. 5 4 3 2 1 첫 번째 요소와 두 번째 요소를 비교합니다. 4가 더 작으므로 둘의 위치를 교환합니다. 4 5 3 2 1 다음 ..

삽입 정렬 (Insetion Sort) 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 입니다. ■ 정렬 방식 1. 배열의 첫 번째 요소는 정렬 된 상태라고 가정한다. 2. 배열의 두 번째 요소부터 앞에 정렬된 배열을 차례대로 비교하며 교환한다. 3. 최종적으로 자신의 위치에 맞는 위치에 삽입된다. 4. 다음 배열 요소에 대해서 같은 작업을 반복한다. : 정렬이 완료 된 상태 : 비교되는 배열 요소들 5 4 3 2 1 첫 번째 배열요소는 정렬이 완료된 상태라고 가정을 합니다. 5 4 3 2 1 두 번째 요소부터 비교를 시작합니다. 앞에 정렬된 첫 번째 요소와 비교를 하고 4가 더 작으므로 둘의 위치를 바꿔줍니다. 4..

선택 정렬(Selection Sort) 기존 위치에 맞는 원소를 선택하여 교환하는 방식 ■ 정렬 방식 1. 아직 정렬이 안된 리스트 중에 가장 앞에 원소를 최소값으로 설정 2. 가장 앞에 원소를 제외한 나머지 원소를 차례로 비교하고 최소값을 찾아감 3. 리스트 끝까지 비교 후 찾은 최소값을 가장 앞에 원소와 교환 4. 정렬이 안된 원소들을 가지고 반복 ■ 특징 - 최소값을 찾기 위한 비교횟수는 많지만 교환 횟수는 적다. - 데이터의 개수가 적을 때 좋은 성능을 발휘한다. - 시간복잡도 : O(n＾2) ■ 소스코드 (Source Code) public int[] Selection_Sort(int[] data,int num) { int min,tmp; for(int i=0;i

옵저버 패턴 (Observer Pattern) 옵저버 패턴은 개개체의 상태 변화를 관찰하는 관찰자들, 즉 옵저버들의 목록을 객체에 등록하여 상태 변화가 있을 때마다 메서드를 통하여 관찰 대상자가 직접 옵저버들에게 통지하여 상태를 동기화 할 수 있도록 하는 디자인 패턴을 의미합니다. ■ 옵저버 패턴 예제 ▶옵저버 패턴이 적용된 예제를 구현 해보겠습니다. ● Generator : 관찰 대상자를 나타내며, 현재 관찰 대상자에 붙어있는 Observer들을 관리합니다. 뿐만 아니라 현재 관찰 대상자의 상태 정보를 얻기 위한 메서드를 제공하며, 상태 변화시 등록되어 있는 모든 관찰자들에게 상태 변화를 통지해주는 메서드를 제공합니다. ● StringGenerator : Generator를 상속받는 실제 상태 정보를 ..

메멘토 패턴 (Memento Pattern) 메멘토 패턴은 객체의 상태 정보를 저장하고 사용자의 필요에 의하여 원하는 시점의 데이터를 복원 할 수 있는 패턴을 의미합니다. ■메멘토 패턴 예제 구조 ▶ 실제로 메멘토 패턴을 사용하여 객체 정보를 저장하고 복원하는 예제를 살펴 보겠습니다. 예제는 간단히 String형 데이터 하나와 Int형 데이터 하나에 대한 정보로 가지는 Information 객체를 구현하였습니다. ● User : 메멘토 패턴이 적용 된 Information 객체를 실제로 사용하는 사용자입니다. ● Information : 상태를 저장하고 복원 할 데이터를 가지고 있는 클래스입니다. ● Memento : 특정 시점의 Information의 상태정보를 저장하는 클래스입니다. ● CareTak..

데코레이터 패턴 (Decorator Patter) 중심이 되는 객체에 부가적인 기능을 동적으로 추가하고자 할 때 사용하는 패턴입니다. ■ 데코레이턴 패턴 구조 (예제) 예제는 기본 빵 객체를 대상으로 여러가지 재료를 조합하여 동적으로 햄버거를 만드는 예제입니다. ● Hamburger : 장식할 대상이 가져야 할 공통 인터페이스를 정의합니다. ● Bread : 구체적인 장식 할 대상입니다. 다른 장식 대상을 장식 할 수는 없습니다. ● Ingredient : 장식 할 대상을 장식하는 클래스로 또한 Hamburger의 인터페이스를 가지기 때문에 장식 대상이 될 수도 있습니다. 장식 할 대상의 객체를 참조합니다. ●Shrimps_Patty 와 Bulgogi_Patty : Ingredient의 인터페이스를 구현..

방문자 패턴 (Visitor Pattern) 데이터 구조와 연산을 분리하여 데이터 구조의 원소들을 변경하지 않고 새로운 연산을 추가 할 수 있습니다. 새로운 연산을 추가하려면 새로운 방문자를 추가하기만 하면 됩니다. ■ 방문자 패턴 구조 (예제) 오른쪽에는 Composite 패턴으로 구현 된 File과 Directory로 이루어진 데이터 구조가 있습니다. 다만, 방문자를 수용하기 위해 Element 인터페이스를 상속받아서 accept() 메서드를 각각 구현하고 있으며 각 element의 경로를 구하는 연산 부분이 방문자에서 이루어집니다. 왼쪽에는 방문자로 데이터 구조를 방문하면서 필요한 연산을 수행합니다. 각 element에 접근하기 위한 visit메서드를 오버라이딩 및 오버로딩을 하고 있습니다. ■ 소..