6. 정렬알고리즘 정리, 딕셔너리

이전에 공부한 정렬 알고리즘을 정리한 사진

정렬의 안정성

동일한 키를 가진 경우 (k, e1),(k, e2)의 순서대로 들어왔을 경우

e1이 앞에서 정렬되었을 경우 안정적인 정렬이라 한다.

선택정렬, 삽입정렬등은 안정적이다. 그러나

힙정렬, 퀵정렬의 경우 안정적이지 못하다.

🔍사전(ADT)

(키, 원소)쌍의 항목들의 모음을 모델링한 자료구조

작업: 탐색, 삽입,삭제 알고리즘

무순사전: 키의 순서에 상관없음.

순서사전: 키의 순서대로 정렬되어있는 사

메쏘드

일반 메소드

int size(): 사전의 항목 수를 반환

boolean isEmpty(): 사전이 비어있는지에 대한 여부를 반환

접근메소드

element findElement(k): 키를 가진 항목이 존재하면 반환, 아니면 NoSuchKey반환

갱신메소드

insertItem(k,e): 사전에 (k,e)항목을 삽입

element removeElement(k): 사전에 키 k를 가진 항목이 존재하면 삭제 후 반환, 아니면 NoSuchKey반환

사전의 응용

직접적 응용

• 연락처 목록
• 신용카드 사용 승인
  • 온라인 결제 시 카드 번호, 정보등을 조회
• 인터넷 주소 매핑
  • 호스트명(www.naver.com)을 인터넷 주소(xxx.xxx.xxx.xxx)로 매핑

탐색

키와 연관된 데이터원소를 반환

• 유일키: 한개의 키에 대해 하나의 데이터 항목이 존재
• 중복키: 한개의 키에 대해 여러개의 데이터 항목이 존재

기록 파일 구현: 무순리스트를 이용해 구현된 사전

사전 항목들을 임의의 순서로 리스트에 저장

성능

• insertItem: 새로운 항목을 기존 리스트의 맨 앞 또는 맨 뒤에 삽입하면 되므로 O(1)의 시간 소요
• findElement 및 removeElement: 키를 찾기 위해 리스트 전체를 순회해야 하므로 O(n)의 시간 소요

사용처

• 소규모 사전, 삽입이 빈번하나 탐색,삭제가 드문 사전(로그인기록등)

FindElement(k)

while문을 통해 전체 원소를 훑은 후 k에 해당하는 원소를 찾으면 반환

일람표 구현: 순서리스트를 이용해 구현된 사전

사전 항목들을 배열에 기초한 리스트에 키로 정렬된 순서로 저장

성능

• findElement: 이진탐색을 사용하면 O(log n)의 시간 소요
• insertItem: 새로운 항목을 삽입하기 위해 공간확보를위해 n개의 기존 항목을 이동해야해 O(n)의 시간이 소요
• removeItem: 마찬가지로O(n)의 시간이 걸림

사용처

• 소규모 사전, 탐색은 빈번하지만 삽입, 삭제는드문 사전

실패가 예정된 경우

정렬이 되어있으므로 찾다가 키보다 정렬된 순서값이 더 커져버리면 break해줄 수 있다.

이진 탐색

재귀를 이용해 findElement작업을 수행한다.

배열의 가운데 지점을 확인 후 해당 지점보다 크면 오른쪽 작으면 왼쪽을 탐색한다.

해당 지점이 찾은 요소일 경우 반환

따라서, 재귀가 반복될 때마다 후보 항목의 수가 절반으로 줄어든다

이진 탐색 트리

(키, 원소)쌍을 저장하며

부모키, 왼쪽자식키,오른쪽 자식키 일때

왼쪽자식키 < 부모키 ≤ 오른쪽 자식키의 조건이 만족해야하는 트리

탐색

찾을 노드가 해당 키보다 작을 경우 왼쪽 클경우 오른쪽으로 이동,

이를 반복하여 탐색하는방식

그러나 해당 이진탐색 트리의 방법의 경우

삽입과정에서 좌우 불균형이 심해질 가능성이 존재함.

따라서 AVL트리를 작성하기도 한다.