반응형
[DSA] Search & Sorting Algorithm Tutorial |
https://www.tutorialspoint.com/data_structures_algorithms/binary_search_algorithm.htm
-
Linear Search 는 O(n) 의 complexity 를 갖는다.
-
Binary Search 는 O(log n) 의 complexity 를 갖는다.
Divide and Conquer 방식이 기본이다.
Binary Search 가 작동하려면 sorting 이 되어 있어야 한다.
Mid position 에 있는 녀석이 찾으려는 녀석인지 확인한다.
찾으려는 녀석이 그 녀석보다 작으면 아래쪽을 다시 binary search 하고,
크면 위쪽을 다시 binary search 하는 방식이다.
-
Interpolation search 는 binary search 의 향상된 변형이다.
Binary Search 와 마찬가지로 sorting 이 되어 있어야 한다.
Search 의 시작점이 무조건 center 인 Binary 와는 달리 어떤 공식 (mid = Lo + ((Hi - Lo) / (A[Hi] - A[Lo])) * (X - A[Lo])) 을 통해 (probing) 시작점을 잡아서 divide and conquer 를 한다.
Time Complexity 는 O(log (log n)) 이다.
-
Sorting 은 in-place sorting 과 not-in-place-sorting 으로 구분된다.
sorting 을 하는 중 다른 memory space 를 사용하는 경우는(보통 element 갯수에 비례하여) not-in-place sorting 이고, 필요로 하지 않는 경우가 in-place sorting 이다.
in-place sorting 의 대표적인 녀석은 bubble sort 이고, not-in-place sorting 의 대표적인 녀석은 merge sort 이다.
-
Sorting 을 한 후 비슷한 content 의 순서가 바뀌지 않는다면 stable sorting 이다.
Sorting 을 한 후 비슷한 content 의 순서가 바뀔 수 있다면 unstable sorting 이다.
-
이미 Sorting 되어 있는 녀석을 sorting 할 때 이득이 있다면 adaptive 라고 부르며,
그렇지 않은 경우는 Non-adaptive 라고 부른다.
-
Bubble Sorting 은 바로 옆에 있는 녀석과 비교해나가면서 순서를 바꾼다.
옆에 있는 녀석과의 비교는 처음 index 0 부터 끝까지, 그 다음은 1 부터 끝까지.. 이런 식.
Complexity 가 O( n^2 ) 이기 때문에 large data set 에는 적합하지 않다.
-
Insertion Sorting 은 in-place sorting 이다.
index 0부터 한 개의 element 들을 검사하며 그 앞의 index 들과 비교하며 적합한 위치로 옮긴다. 이 때 shifting 이 많이 발생할 수 있다.
이 녀석도 Complexity 가 O( n^2 ) 이기 때문에 large data set 에 적합하지 않다.
-
Selection Sorting 은 정렬된 것이 왼쪽으로, 정렬되지 않은 것이 오른쪽으로 정렬되는 정렬법이다.
처음에는 정렬된 것은 없다.
In-place sorting 이다.
Unsorted array 쪽에서 가장 작은 녀석을 찾아 Unsorted array 의 첫번째 item 과 swap 한다.
그 다음 이 과정을 반복한다.
이 녀석도 Complexity 는 O( n^2 ) 이기 때문에 large data set 에 적합하지 않다.
-
Merge Sorting 은 Divide and conquer 방법의 정렬법이다.
반으로 나눌 수 있을 때까지 element 를 쭉 나눈 후, 정렬을 하면서 다시 합친다.
정렬할 때에는 sub-list 를 두고 그곳에 작은 녀석부터 insert 하는 방식을 사용한다.
O( n log n ) 의 복잡도를 갖는, 가장 잘 사용되는 방법 중 하나이다. 큰 사이즈의 Data 에 좋다.
-
Shell Sort 는 insertion sort 를 기반으로 한 아주 효율적인 정렬법이다.
insertion sort 에서 발생하는 large-shift 를 방지한다.
Knuth’s formula 를 이용하여 interval ( spacing ) 을 계산하고, interval 관계에 있는 녀석들에 대해 sorting 을 미리 하여, 전체적으로 더 적게 spread 된 녀석들을 insert sort 하는 방식이다. ( interval 이 1이 되면 insert sort )
중간 사이즈의 데이터에 대해 효율이 좋다.
O(n) 의 complexity 를 갖는다.
-
Quick Sort 는 작은 array 로 쪼개서 정렬( Divide and conquer )하는 아주 효율적인 정렬방식이다.
처음 시작은 가장 오른쪽 녀석이 pivot 이 된다.
pivot 을 기준으로 좌, 우 array 를 나눈다.
각각의 array 를 quick sort 한다.
pivot 을 제외하고 left, right 를 잡는다.
left 는 pivot 보다 작은 녀석들만 존재하도록 하기 위해, pivot 보다 큰 수를 찾아 오른쪽으로 이동한다.
right 는 pivot 보다 큰 녀석들만 존재하도록 하기 위해, pivot 보다 작은 수를 찾아 왼쪽으로 이동한다.
위의 조건이 만족되는 position 에 left 와 right 를 위치시켰다면 둘을 swap 시킨다.
이렇게 이동하다보면 left 와 right 가 만나는 지점이 있는데.. right 를 기존 pivot 과 swap 해주어 pivot 기준으로 좌우가 ordering 되도록 한다.
이 녀석은 큰 사이즈의 데이터에 적합하다.
O( n log n ) 의 complexity 를 갖는다. ( average )
반응형
'프로그래밍 놀이터 > Tips' 카테고리의 다른 글
| SIM Card 연락처 정보 (0) | 2019.01.16 |
|---|---|
| AVL Tree, Red Black Tree (0) | 2019.01.14 |
| [Data Structure] HashMap 보다 Tree 를 써야 하는 곳에 대해 알아보면서 알게 된 내용들 (0) | 2019.01.12 |
| [Kotlin] Coroutine 소개 (그렇지만 조금 깊을 수도 있음..) (1) | 2018.11.27 |
| [실용주의 프로그래머] 총 정리 (0) | 2018.11.19 |
댓글