자료구조(11), Sorting and Searching Algorithm

Sorting and Searching Algorithm

---

- 배열에 저장된 값에는 관계 연산자가 정의된 유형의 키가 있다. 이를 오버로딩해서 사용한다.

- 오름차순 또는 내림차순으로 재배열을 한다.

---

1. Selection Sort(Straight)

- 1 iteration에서 두 개의 키 값을 찾아서 뒤집는데 최대 1개만 바꾸게 된다. 

- 정렬되지 않은 요소 중 가장 작은 요소를 작은 요소를 찾아 바꾼다. 정렬이 되지 않았기에 순차탐색을 사용해 정렬되지 않은 값 중 가장 작은 값을 찾아서 이를 정렬되지 않은 인덱스 중 가장 작은 인덱스의 값과 바꿔준다.

- 소트에서의 단위연산은 두 가지로 이뤄질 수 있다. 키 값의 비교가 몇 번 일어나는가. 이게 제일 중요해서 제일 많이 쓰이지만 스왑을 몇번 하는가?도 하는 경우가 많다.

- 최악의 경우와 최선의 경우의 비교횟수가 비슷하다.

- 0.5N^2 * 0.5N만큼의 시간복잡도를 가진다.

- 반복문이 두 개 발생한다. 

---

2. Bubble Sort

- 마지막 배열 요소부터 시작하여 인접 배열 요소 쌍을 비교하고 올바른 순서가 아닐 때마다 이웃을 교환한다.

- 물방울이 납작한 모양처럼되어서 버블을 만들어가며 값을 비교한다.

- 올바른 순서가 아닐 때 값을 바꾸어 버블업을 한다. (오름차순과 내림차순일 때 다르다.)

- 버블소트는 거의 모든 경우가 최악이다. 즉, input되는 n개에 대해 성능차이가 일관되게 나쁘다. 이는 교환 횟수가 너무 많기 때문이다. selection sort만 보더라도 selection sort는 한번만 스왑을 하겠지만 버블 소트는 굉장히 더 많이 교환한다.

- N^2의 알고리즘은 NlogN에 비해 구현하기 쉽다. 또한 N^2 알고리즘이 NlogN 정렬알고리즘보다 데이터유형에 따라 빨리 끝나는 것이 있다. 그러나 버블소트는 그러한 부분이 거의 없다.

 

구현파트

- other version에서 Flag가 생겼다. swap이 된다면 flag의 값이 증가한다. 만약 swap이 되지 않으면 flag의 값이 그대로 0이되니 이것을 탈출조건으로 활용해 성능을 조금 키우기 위해 사용한다.

---

3. Insertion Sort

- 정렬되지 않은 각 배열 요소는 하나씩 정렬되어 이미 정렬된 요소와 관련하여 적절한 위치에 삽입한다.

- 일반적으로 앞쪽에 값을 넣어주고, 각 패스에서 이미 정렬된 요소의 수가 1씩 증가한다.

- 앞에 정렬된 값들보다 더 작은 값이 이동한다면 정렬된 값 중 그보다 더 큰 값들은 뒤로 한칸씩 이동한다. 이는 버블정렬과 비슷하지만 내부 공간을 만들어주기 위해 옮겨주는 것이다. 따라서 임시변수를 만들어서 공간을 만들어줘야한다.

- 포인터배열을 사용하면 index만 이동시킬 수 있다. 그런식으로 구현하면 이동에 대한 비용을 줄일 수 있다.

 

cf) Sorting Algorithms and Average Case Number Of Comparisons

- SImple Sorts: N^2 시간복잡도

- More Complex Sorts: NlogN 시간복잡도

- N^2에 해당하는 알고리즘과 NlogN에 해당하는 알고리즘의 차이는 두 개의 키값에 존재하는 역을 한번에 몇개까지 제거할 수 있느냐에 달려있다. N^2은 최대 한번이지만 NlogN은 두 개 이상의 역을 제거할 수 있다.

 

---

4. Heap Sort

- 힙을 이용해서 정렬한다.

- BST는 아니다. 바이너리 트리는 맞다. complete binary tree이다.

- 가장 큰 값을 하나하나씩 뽑아서 이를 뒤에서부터 차곡차곡 저장한다.

- 리힙을 할 때는 2개의 하위 요소의 더 큰 요소와 교체된다. 리힙은 Complete binary tree이기에 logN만큼의 시간복잡도를 가진다.

- 힙소트는 힙을 유지하기 위해 연산을 더 해야하기에 NlogN보다 느린 편이긴하다.

- Min Heap에서 데이터를 뒤쪽에 저장한다면 내림차순으로 정렬된다. Max Heap을 사용하면 오름차순으로 정렬된다. 만약 어레이에 저장한다면 Min Heap이 오름차순으로 저장하기 더 편하다.

---

5. Quick Sort

- 최악의 경우에는 N^2의 시간복잡도를 가진다. 하지만 메모리의 로컬리티 때문에 다른 알고리즘과 동일한 시간복잡도를 가진다면 속도가 더 빠르다. 메모리 정책은 다양하게 있을 수 있고, 실패할 수도 있다. 따라서 cash hit 비율을 높이기 위해 메모리 정책을 놔두는데, sequential data(동적 할당도 포함)는 한번 쓰이면 다음 번에 더 쓰인다. 이는 locality 법칙이다. 그 주변에 있는 것도 가져와서 캐쉬에 저장한다. 즉, 동일한 배열을 사용하는 정렬알고리즘이더라도 스왑하며 진행하는 소트알고리즘은 지역성을 해치지 않으면 효율적이게 된다. 하지만 머지소트는 이를 쪼개고 합치는 경우가 있기에 머지소트와 퀵소트는 알고리즘 상 시간복잡도가 비슷하지만 퀵소트의 효율은 더 높다.

- SplitVal: 이를 어떻게 잡느냐에 따라 시간복잡도가 다르다. 따라서 3개 정도 값을 잡아서 최소값을 집어넣는 경우가 많다. 그 값을 기준으로 왼쪽에는 splitval보다 작은 값, 오른쪽은 큰 값을 배치한다. 이후 두 개의 내용이 결정된다. 자기 자신의 위치와 왼쪽에 배치된 데이터는 자기 자신보다 작고, 오른쪽에 배치된 데이터는 자기 자신보다 크게된다. 또한 작은 값과 큰 값들에 대해 위의 과정을 반복한다. 이는 재귀가 사용된다.

- 최악의 경우는 정렬되어있는 데이터가 입력된 경우가 된다. 이를테면 한쪽으로 데이터가 몰려있으면 split을 하기위해 n-1개의 그룹으로 쪼개지고, n-2개의 그룹으로 쪼개지는 등등의 과정을 거친다. 따라서 n^2의 시간복잡도를 가지게 된다. 최선의 경우에는 logN 분할만 일어난다.

 

---

6. Merge Sort

- 합치기 위해서 쪼개야한다. 이는 인덱스를 기준으로 쪼갠다. 이후 나눠진 것에 대해서 합친다. 각각의 첫번째 인덱스를 비교해가며 최소값을 모두 넣어주면 된다. 지역 배열을 많이 사용하기에 로컬리티가 줄어든다. 시간복잡도만 본다면 일반적으로 퀵소트보단 낫다.

- 분할할 때 얼마나 걸리는지가 중요하다. 

---

7. BinarySearch

- 중앙값을 기준으로 좌측과 우측을 탐색한다. 이를 위해서 기본적으로 정렬되어있어야한다. 어떤 데이터가 주어지고 특정값을 탐색하라고 했을 때 연산속도가 빠른 것을 도입시키기 위해선 추가적인 정보가 필요하다.

- 인명사전이 있다고 했을 때 최씨 성을 찾는다고 할 때는 굳이 binary search가 아닌 뒷쪽의 페이지부터 찾는다. 인명사전의 정보는 오름차순 정렬되어있고, 성씨의 분포가 고르지 않다는 것을 알 수 있다. 이에 따라 데이터의 비율을 반영해서 특정 위치를 계산해서 확인하는 것이 고간탐색이다. 따라서 추가적인 데이터 상황을 반영해서 찾는 경우 더 빠르게 탐색할 수 있다.

---

8. Hashing

- 키 값의 함수를 사용해서 목록에서 해당 위치를 식별함으로써 목록의 요소를 빠르게 정렬하고 접근하는데 사용되는 수단이다. 목표는 O(1)이다.

- 해쉬함수를 만들어서 그 결과값의 특정 인덱스에 해당 데이터를 보관하는 것을 해싱이라고 한다. 

- 해싱의 장점은 전체 데이터를 보지 않더라도 특정 키를 바로 확인할 수 있다. 따라서 원소들이 어떻게 저장되었는지 고려할 필요없이 데이터를 바로 확인할 수 있는 장점이 있다. 독자적인 자료구조가 필요하다.

- 정말 큰 데이터인 경우에는 해시함수를 사용하는게 상수에 해당하는 시간이기에 되게 빠르다. n에 상관없이 단위연산의 횟수가 동일하다.

- 일련번호가 있어서 해시함수를 통해 데이터의 일련번호를 구할 수 있다. 

- 예시) Hash(key) = partNum % 100, 이때 키 값이 주어졌을 때 확인해야하는 인덱스를 바로 얻을 수 있다. 하지만 충돌은 발생할 수 있다.

- 키가 중복되는 경우가 존재한다. 그 경우 해결하는 방법이 존재한다.

 

1) linear probing

- 현재 인덱스에서 순차적으로 숫자를 올려가며 비어있는 공간을 찾는다. 

- 이 경우에 찾을 때 값이 없다면 뒤에 있는 값들을 모두 찾아야한다. 이때 데이터를 삭제한다고 하면 그 뒤에 있는 원소를 굳이 찾지 않고 이를 뺀다. 따라서 삭제하는 경우에는 뒤에 있는 데이터를 가져오는 과정이 필요하다. 이는 close hashing이다. 이는 고정된 데이터를 사용하여 close hashing이다.

 

2) chaining

- open hashing: 링크드리스트로 되어있어서 어떤 인덱스에 대해 리스트를 쭉 따라가면 된다. 

- 하지만 입력되는 데이터의 hash 함수의 결과가 치우쳐져있는 경우에는 단점이 된다. 따라서 해쉬함수를 잘 구현해야한다. 

- 해쉬함수는 이상하게 구현하지 않는 이상 몰리지 않는다. 

 

---

9. 정렬 알고리즘의 연산속도

- std sort는 퀵소트 기반이다.

- stable sort는 머지 소트와 비슷하다.

- bogo sort는 인덱스 값을 랜덤으로 지정해줘서 언젠가 데이터가 정렬된다.

 

1) 랜덤값의 데이터가 입력됐을 때

퀵소트와 셀소트 > 머지소트 > 힙소트 > 삽입소트 > 선택정렬 > 칵테일 정렬 > 버블 정렬

 

2) Few unique

퀵소트 > 셀소트 > 머지소트 > 힙소트 > 삽입정렬 > 선택정렬 > 칵테일 정렬 > 버블 정렬

 

3) Inverse

퀵소트 > 셀소트 > 머지소트 > 힙소트 > 선택정렬 > 삽입정렬 > 버블정렬 > 칵테일 정렬

 

4) 거의 정렬되어있을 때 

- 삽입정렬 > 칵테일 정렬 > 퀵소트 > 머지소트 > 힙소트 > 버블소트 > 선택정렬

 

- 거의 정렬이 된 경우에는 삽입 정렬이 훨씬 빠르게 동작한다. 버블정렬은 어떻게 정렬이 되어있는지와는 상관없이 느리고, 힙정렬은 nlogn 시간복잡도를 가진 정렬알고리즘 중에서 조금 느린 편이다. 대체로 퀵소트가 빠른 것을 확인할 수 있다. inverse인 경우에는 선택정렬이 삽입정렬보다 빠르다.