자료구조

특정 순서에 따라 주어진 데이터를 나열하는 것크기 순으로 오름차순 or 내림차순 나열하는 것검색의 기본 요건이다레코드(n개의 필드), 필드, 키(식별자)로 구성되어 있다.구별할 수 있는 식별자 역할을 하는 학번이 키. 한 학생의 학번, 이름, 주소 정보가 필드.이러한

데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역으로 나누고 정렬되지 않은 영역의 값을 정렬된 영역의 적절한 위치로 놓으며 정렬최선의 경우 : O(n) - 이미 정렬최악의 경우 O(n^2) - 역순많은 이동이 필요하므로 레코드가 클 경우 불리대부분 정렬되어 있으

정렬된 왼쪽 부분과 정렬되지 않은 오른쪽 부분으로 나뉜다 초기에 왼쪽 부분은 비어있고, 오른쪽 부분은 가득 차 있다.오른쪽 부분에서 가장 작은 값을 구한 후 이를 왼쪽 부분으로 이동시킨다 왼쪽에는 데이터가 작은 수부터 하나씩 추가된다 오른쪽 부분에 데이터가 없을 때

인접한 두 개의 원소를 검사하여 정렬하는 방법으로 뒤에서부터 정렬인접한 2개의 레코드를 비교하여 순서대로 되어 있지 않으면 서로 교환(큰 수를 뒤로)가장 큰 수가 뒤로감이 과정을 리스트의 왼쪽 끝에서 오른쪽 끝까지 반복(스캔)1회 반복할 때마다 오른쪽에 정렬된 데이터가

삽입 정렬은 어느정도 정렬된 리스트에서 매우 빠르다. 이것에서 착안된 것이 쉘정렬이다.삽입 정렬은 요소들이 이웃 위치로만 이동하므로, 많은 이동이 필요하다.요소들이 멀리 떨어진 위치로 이동할 수 있다면 보다 적게 이동하여 제자리를 찾을 수 있다.전체 리스트를 일정 간격

Divide&Conquer리스트를 피벗을 중심으로 2개의 부분 리스트로 비균등 분할각각의 부분 리스트를 다시 퀵정렬(재귀호출)피벗은 보통 첫번째 데이터 이용하나 정해진건 아님평균적으로 가장 빠른 방법각 부분리스트에서 피벗을 선택최선 : 균등한 리스트로 분할되는 경우각

이진 힙을 사용하는 정렬이다.힙 : 각 묶음에서 큰 수가 위에 오는 형태상단의 힙에 변화가 생기면 하단의 힙에도 영향이 생긴다initial heap으로 만들고,가장 상위 수를 제거하고(가장 큰 수이므로),가장 끝 수를 가장 상위에 넣은 후, 힙을 재정렬한다.위의 경우

정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬리스트를 두 개의 균등한 크기로 분할하고 분할된 부분리스트를 정렬정렬된 두 개의 부분 리스트를 합하여 전체 리스트를 정렬Divide & Conquer단점 : 분할한 자료를 저장할 별도의 저장 공간 필요

기수 정렬레코드 비교하지 않고 정렬 수행비교에 의한 정렬의 하한인 𝑂(𝑛 log 𝑛) 보다 좋을 수 있다.기수 정렬은 O(d\*n) 의 시간 복잡도 (대부분 d<10 이하, d는 자릿수)정렬할 수 있는 레코드의 자료형이 한정적이다 (실수, 한글, 한자 등 불

꼭짓점(Vertex)와 간선(Edge)을 이용한 비선형 데이터 구조방향이 있는 간선을 포함하면 방향 그래프(Directed Graph) : <A, B>방향이 없는 간선을 포함하면 무방향 그래프(Undirected Graph) : (A, B)어떤 데이터는 흐름의 방

계층적 구조를 나타내는 자료구조트리는 데이터를 저장하고 탐색하기에 유용한 구조를 갖고 있다.트리는 나무 기둥에서 가지가 뻗어나가는 모습을 거꾸로 뒤집어 놓은 모양이다.노드 : 트리의 구성 요소부모, 자식, 형제(sibling) 노드루트(root) : 가장 상위의 노드,