합병정렬(Merge Sort)합병정렬은 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음 두개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻고자 하는 것입니다.이처럼 합병정렬은 분할-정복(Divide and Conquer) 기법에 바탕을 두고 있습니다.- 얼핏보면 쉘 정렬과 비슷해보이지만 또 그렇지만은 않습니다. 1. 분할 : 입력 배열을 같은 크기의 2개의 부분 배열로 분할합니다.2. 정복 : 부분 배열을 정렬합니다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용해 다시 분할 정복 기법을 적용합니다.3. 결합 : 정렬된 부분 배열들을 하나의 배열에 통합합니다. 합병정렬의 특징삽입, 선택, 버블, 쉘 정렬 등의 이제까지 설명했던 정렬들 중 실행속도가 ..

쉘 정렬(Shell Sort)쉘 정렬은 Donald L. Shell 이라는 사람이 제안한 방법으로 삽입 정렬이 어느정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안한 방법입니다.쉘 정렬의 속도는 삽입정렬의 O(n^2)보다 빠릅니다. 쉘 정렬의 속도는 약 O(n^1.5) : 몇개로 그룹들을 나누느냐에 따라 실행속도가 달라집니다. 삽입정렬의 최대 문제점은 요소들이 삽입될 때 이웃한 위치로만 이동한다는 것입니다.만약, 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면 이미 정렬된 요소들이 많은 이동을 해야만이 제자리로 삽입될 수 있습니다.- 정렬 위치 이후의 모든 요소들이 한 칸씩 옆으로 이동해야 정렬이 됨쉘 정렬은 요소들이 멀리 떨어진 위치로 이동할 수 있습니다. 1. 정렬해야 할 리스트들을..

버블정렬 (Bubble Sort)버블정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행합니다. 이렇게 되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 되는데 이 과정을 스캔이라고 합니다. 이 스캔 과정을 반복하며 숫자가 정렬될 때까지 반복 수행합니다.레코드의 이동 과정이 마치 물 속에서 거품이 보글보글 떠오르는 것과 유사하다고 하여 버블정렬이라고 부릅니다. 1. 인접한 2개의 레코드 비교, 작은 숫자를 앞으로 교환2. 가장 큰 수가 오른쪽 끝으로 가게 됨3. 1의 과정을 다시 진행하여 모든 숫자가 정렬될 때 까지 반복 스캔 과정 버블정렬의 특징버블정렬은 안정성이 있고, 비효율적인 정렬입니다. 알고..

삽입정렬 (Insertion Sort) 삽입정렬은 손안의 카드를 정렬하는 방법과 유사합니다.즉, 새로운 카드를 기존의 정렬된 카드 사이의 올바른 자리를 찾아 삽입함으로써 정렬이 유지되게 합니다.- 새로 삽입될 카드의 수 만큼 반복하면 전체 카드가 정렬 1. 리스트의 처음부터 값을 비교하며 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판단2. 해당 위치에 이 숫자를 삽입하게 되면 정렬된 부분의 크기는 하나씩 커지며 자리이동3. 정렬되지 않은 부분은 크기가 하나 줄어듦의 순서를 반복합니다. 삽입정렬의 특징삽입정렬은 안정성이 있으며, 비효율적입니다. 처리속도는 선택정렬과 마찬가지로 O(n^2)입니다. 삽입정렬 코드 출처 : http://wonjayk.tistory.com/218

선택정렬 (Selection Sort) 선택정렬은 가장 이해하기 쉬운 정렬 방법입니다.리스트 중 가장 작은 숫자를 선택하여 왼쪽 부터 정렬시켜 나가는 작업을 반복하는 정렬입니다. 아래는 선택정렬의 순서입니다. 선택정렬의 특징 선택정렬은 안정성이 없고 비효율적이지만 구조가 단순하여 구현이 간단하다는 장점이 있습니다.레코드 갯수의 -1번 반복하여 정렬을 완료합니다.처리속도 O(n^2)- 안정성 : 입력 데이터에 동일한 키 값을 갖는 레코드가 여러개 존재할 경우 이들의 상대적인 위치가 정렬 후에도 그대로 바뀌지 않는 것을 안정성 있는 정렬 이라고 합니다. 선택정렬 구현 출처 : http://wonjayk.tistory.com/217

트리 (Tree) 지금까지는 리스트, 스택, 큐 등의 선형 자료 구조(Linear Data Structure)만을 공부했습니다. - 선형 자료 구조는 자료들이 직선과 같이 나열되어 있는 구조를 의미합니다. 만약 선형이 아니고 자료가 계층적인 구조를 가지고 있다면 어떻게 해야할까요? - 조상과 자손, 전체와 부분, 상사와 부하직원, 컴퓨터의 디렉토리 구조 등의 계층적 관계입니다. - 이런 계층적인 관계를 표현하기에는 선형 자료 구조로는 한계가 있습니다.트리는 이러한 계층적인 구조를 표현하는데 사용하는 자료구조입니다. - 인공지능 문제에서도 트리가 사용됩니다. 의사결정트리 등 트리의 용어들을 알아보겠습니다.노드 : 트리의 구성요소들루트노드 : 부모가 없는 노드, 트리는 하나의 루트노드만 가집니다.리프노드 :..