자료구조 C++ (11) 썸네일형 리스트형 6. 정렬 (sorting) 1. 정렬의 소개 *리스트 연산 리스트에 원소를 추가 또는 제거하고 원하는 원소를 검색 제약점 -> 정렬된 리스트만을 요구함 정렬되지 않은 리스트라면? -> 정렬 * 정렬 (sorting) 데이터를 정해진 키에 따라서 크기 순으로 배열하는 것 오름차순 (ascending order) 내림차순 (descending order) *정렬 알고리즘의 성능 정렬할 데이터의 개수 : n O(f(n))으로 표시 O(n^2)정렬 알고리즘 - 버블정렬, 삽입 정렬, 선택 정렬, .... O(nlogn) 정렬 알고리즘 - 합병 정렬, 쾌속 정렬, .... 2. O(n^2) 정렬 - 정렬 알고리즘의 성능은 정렬하고자 하는 원소의 수 (n)의 제곱인 (n^2)에 비례함. 이동에 기반한 정렬 : 삽입 정렬 교환에 기반한 정렬 .. 4. 연결 리스트 (linked list) 1. 연결리스트 개념 원소들이 메모리에서 임의의 위치에 배치되어 있음 한 원소는 다음 원소를 가리키는 link를 가지고 있음 (포인터 기반) 2. 배열과 연결 리스트 비교 배열 : 원소들이 메모리에서 일정한 간격으로 나열되어 있음 연결 리스트 : 원소들이 메모리에 임의의 위치에 배치되어 있음 배열 연결 리스트 메모리 공간 연속된 메모리 주소 이산된 메모리 주소 공간 할당 정적 할당 / 동적 할당 동적 할당 접근 경로 첫 번째 원소의 주소 첫 번째 원소의 주소 접근 방법 인덱스 포인터 접근 방식 Random access Sequential access 3. 연결 리스트 정의 node = data + link node는 메모리의 임의의 위치에 배치됨 각 node는 다음 node를 가리키는 link를 포함하고.. 3. 배열 (Array) 1. 리스트와 배열 리스트 - 가장 기초적이고 오랫동안 사용된 자료구조 배열 - 리스트의 가장 널리 사용되는 구현 방법 2. 리스트의 개념 원소들을 한 줄로 나열한 구조 (특별한 순서를 따름) 리스트 ex) 전화번호부 , 앱 스토어 , 음악 플레이어 , 버스 도착 정보 , 포켓몬 고 3. 리스트의 정의 유한한 원소들의 나열 각 원소들은 인덱스에 대응됨 (index -> element) => 리스트의 가장 중요한 성질 4. 리스트의 구현 방법 배열(Array) : 인덱스에 기반한 구현 - 연속된 기억 공간에 원소를 저장 - 인접한 원소는 인접한 주소에 저장 연결 리스트(Linked list) : 포인터에 기반한 구현 - 메모리에 배열의 크기보다 더 큰 연속된 공간이 없을 때 사용 - 한 원소는 다음 원소를.. 이전 1 2 다음
