[중간고사] 3-(1). Sorting의 개념과 종류

Sorting

컴퓨터 과학 및 알고리즘 분야에서 중요한 개념으로, 주어진 데이터를 특정한 기준에 따라 순서대로 재배열하는 작업

 

Sorting의 응용

예상문제 1. sorting 기반과 divide-and-conquer 기반의 큰 맥락

		sorting	divide- and- conquer	시간복잡도			예시
				Best	Average	Worst
Search	Linear Search	O	X	O(1)	O(n)	O(n)	1D Closest Pair (1차원 가장 가까운 쌍)
							Element Uniqueness (요소 고유성)
							Median and Selection (중앙값과 선택)
							Mode (최빈값)
	Binary Search	O	O	O(1)	O(log n)	O(log n)	Convex hulls (볼록 껍질)

 

아래에 자세한 내용들을 정리해두었으니 참고해둘 것!

Linear Search

왼쪽부터 오른쪽으로 차례대로 탐색

https://hahasof.tistory.com/5
https://www.programiz.com/dsa/linear-search

 

Binary Search

이진 탐색이란 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘이다.
1. 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교한다.
2-(1) X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로,
2-(2) X가 중간값보다 크면 배열의 우측을 대상으로 다시 탐색한다.

3. 동일한 방법으로 다시 중간의 값을 임의로 선택하고 비교한다. 해당 값을 찾을 때까지 이 과정을 반복한다.

 

https://www.programiz.com/dsa/binary-search

---

1D Closest Pair (1차원 가장 가까운 쌍)

: 서로 가장 가까운 쌍을 찾는 문제

 

ex) {3,7,1,9,4,10}

 

1. 정렬

     {3,7,1,9,4,10} → {1,3,4,7,9,10}

2. 정렬된 리스트에서 각 숫자는 인접한 숫자와 비교 → 차이

     (1,3),(3,4),(4,7),(7,9),(9,10) → {2, 1, 3, 2, 1}

3. 결과 도출

     ∴ (1,3), (9,10) 

 

Element Uniqueness (요소 고유성)

: 주어진 배열이나 리스트에 중복된 요소가 있는지 확인하는 문제

 

ex 1) {1, 2, 3} →  중복되지 않으므로 True

ex 2)  {3,7,2,5,3,9,8} →  3이 중복되므로 False

 

Median and Selection (중앙값과 선택)

: k번째  항목을 찾는 문제

 

ex) 다음 {5,2,9,1,7,3} 배열의 3번째 항목은?

{5,2,9,1,7,3} → {1,2,3,5,7,9}  ∴ 3번째 항목 : 3

 

Mode (최빈값)

: 빈도가 높은 값

 

ex) {3,5,2,5,7,3,5,8,5,9} → {3:2,5:4,2:1,7:1,8:1,9:1} ∴ 숫자 5가 4번 등장하여 최빈값은 5임

---

Convex hulls (볼록 껍질)

: 2차원 평면상에 n개의 점이 주어졌을 때, 그들을 모두 포함하는 가장 작은 면적 다각형

 

x축 기준, 왼쪽부터 p, q, r이라 가정 → 직선 p-q가 점 r보다 왼쪽 → 직선 p-r

https://velog.io/@claude_ssim/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Convex-Hulls