์ ๋ ฌ
์ ๋ ฌ
2๊ฐ ์ด์์ ์๋ฃ๋ฅผ ํน์ ๊ธฐ์ค์ ์ํด ์์ ๊ฐ๋ถํฐ ํฐ ๊ฐ(์ค๋ฆ์ฐจ์ : ascending), ํน์ ๊ทธ ๋ฐ๋์ ์์๋๋ก(๋ด๋ฆผ์ฐจ์ : dexending) ์ฌ๋ฐฐ์ด ํ๋ ๊ฒ
ํค : ์๋ฃ๋ฅผ ์ ๋ ฌํ๋ ๊ธฐ์ค์ด ๋๋ ํน์ ๊ฐ
์ ๋ ฌ์ ์ข ๋ฅ
- ๋ฒ๋ธ ์ ๋ ฌ
- ์นด์ดํ ์ ๋ ฌ
- ์ ํ ์ ๋ ฌ
- ํต ์ ๋ ฌ
- ์ฝ์ ์ ๋ ฌ
- ๋ณํฉ ์ ๋ ฌ
๋ฒ๋ธ ์ ๋ ฌ(Bubble Sort)
์ธ์ ํ ๋ ๊ฐ์ ์์๋ฅผ ๋น๊ตํ๋ฉฐ ์๋ฆฌ๋ฅผ ๊ณ์ ๊ตํํ๋ ๋ฐฉ์
์ ๋ ฌ๊ณผ์
- ์ฒซ๋ฒ์งธ ์์๋ถํฐ ์ธ์ ํ ์์๋ผ๋ฆฌ ๊ณ์ ์๋ฆฌ๋ฅผ ๊ตํํ๋ฉด์ ๋งจ ๋ง์ง๋ง ์๋ฆฌ๊น์ง ์ด๋ํ๋ค.
- ํ ๋จ๊ณ๊ฐ ๋๋๋ฉด ๊ฐ์ฅ ํฐ ์์๊ฐ ๋ง์ง๋ง ์๋ฆฌ๋ก ์ ๋ ฌ๋๋ค.
- ๊ตํํ๋ฉฐ ์๋ฆฌ๋ฅผ ์ด๋ํ๋ ๋ชจ์ต์ด ๋ฌผ ์์ ์ฌ๋ผ์ค๋ ๊ฑฐํ ๋ชจ์๊ณผ ๊ฐ๋ค๊ณ ํ์ฌ ๋ฒ๋ธ ์ ๋ ฌ์ด๋ผ๊ณ ํ๋ค.
์๊ฐ๋ณต์ก๋
O(n²)
๋ฐฐ์ด์ ํ์ฉํ ๋ฒ๋ธ ์ ๋ ฌ
def BubbleSort(a, N): # ์ ๋ ฌํ List, N ์์ ์
for i in range(N-1, 0, -1): # ์ ์์ ๋ ์์น
for j in range(0, i):
if a[j] > a[j + 1]:
a[j], a[j + 1] = a[j + 1], a[j]
์นด์ดํ ์ ๋ ฌ(Counting Sort)
ํญ๋ชฉ๋ค์ ์์๋ฅผ ๊ฒฐ์ ํ๊ธฐ ์ํด ์งํฉ์ ๊ฐ ํญ๋ชฉ์ด ๋ช ๊ฐ์ฉ ์๋์ง ์ธ๋ ์์ ์ ํ์ฌ, ์ ํ ์๊ฐ์ ์ ๋ ฌํ๋ ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ
์ ๋ ฌ๊ณผ์
- Data์์ ๊ฐ ํญ๋ชฉ๋ค์ ๋ฐ์ ํ์๋ฅผ ์ธ๊ณ , ์ ์ ํญ๋ชฉ๋ค๋ก ์ง์ ์ธ๋ฑ์ค ๋๋ ์นด์ดํธ ๋ฐฐ์ด counts์ ์ ์ฅํ๋ค.
- ์ ๋ ฌ๋ ์งํฉ์์ ๊ฐ ํญ๋ชฉ์ ์์ ์์นํ ํญ๋ชฉ์ ๊ฐ์๋ฅผ ๋ฐ์ํ๊ธฐ ์ํด counts์ ์์๋ฅผ ์กฐ์ ํ๋ค.
- counts[a] ๊ฐ์, temp์ a ์ฝ์ , ๋ฐ๋ณต
์๊ฐ๋ณต์ก๋
O(n + k)
: n์ ๋ฆฌ์คํธ ๊ธธ์ด, k๋ ์ ์์ ์ต๋๊ฐ
์ ํ์ฌํญ
- ์ ์๋ ์ ์๋ก ํํํ ์ ์๋ ์๋ฃ์ ๋ํด์๋ง ์ ์ฉ ๊ฐ๋ฅ
- ๊ฐ ํญ๋ชฉ์ ๋ฐ์ ํ์๋ฅผ ๊ธฐ๋กํ๊ธฐ ์ํด, ์ ์ ํญ๋ชฉ์ผ๋ก ์ธ๋ฑ์ค ๋๋ ์นด์ดํธ๋ค์ ๋ฐฐ์ด์ ์ฌ์ฉํ๊ธฐ ๋๋ฌธ์ด๋ค.
- ์นด์ดํธ๋ค์ ์ํ ์ถฉ๋ถํ ๊ณต๊ฐ์ ํ ๋นํ๋ ค๋ฉด ์งํฉ ๋ด์ ๊ฐ์ฅ ํฐ ์ ์๋ฅผ ์์์ผํ๋ค.
์นด์ดํ ์ ๋ ฌ ๊ตฌํ
def Counting_Sort(A, B, k):
# A[] - ์
๋ ฅ ๋ฐฐ์ด (1 to k)
# B[] - ์ ๋ ฌ๋ ๋ฐฐ์ด
# C[] - ์นด์ดํธ ๋ฐฐ์ด
C = [0] * (k + 1)
for i in range(0, len(A)):
C[A[i]] += 1
for i in range(0, len(C)):
C[i] += C[i - 1]
for i in range(len(B) - 1, -1, -1):
C[A[i]] -= 1
B[C[A[i]]] = A[i]
์ ๋ ์ ์๊ณ ๋ฆฌ์ฆ(Selection Algorithm)
์ ์ฅ๋์ด ์๋ ์๋ฃ๋ก๋ถํฐ k๋ฒ์งธ๋ก ํฐ ํน์ ์์ ์์๋ฅผ ์ฐพ๋ ๋ฐฉ๋ฒ์ ์ ๋ ์ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ ํ๋ค.
์ต์๊ฐ, ์ต๋๊ฐ ํน์ ์ค๊ฐ๊ฐ์ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ์ ์๋ฏธํ๊ธฐ๋ ํ๋ค.
์ ํ๊ณผ์
์ ๋ ์ ์ ์๋์ ๊ฐ์ ๊ณผ์ ์ ํตํด ์ด๋ฃจ์ด์ง๋ค.
- ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ด์ฉํ์ฌ ์๋ฃ ์ ๋ ฌํ๊ธฐ
- ์ํ๋ ์์์ ์๋ ์์ ๊ฐ์ ธ์ค๊ธฐ
K๋ฒ์งธ๋ก ์์ ์์๋ฅผ ์ฐพ๋ ์๊ณ ๋ฆฌ์ฆ
1๋ฒ๋ถํฐ k๋ฒ์งธ๊น์ง ์์ ์์๋ค์ ์ฐพ์ ๋ฐฐ์ด์ ์์ชฝ์ผ๋ก ์ด๋์ํค๊ณ , ๋ฐฐ์ด์ k๋ฒ์งธ๋ฅผ ๋ฐํํ๋ค.
k๊ฐ ๋น๊ต์ ์์ ๋ ์ ์ฉํ๋ฉฐ O(kn)์ ์ํ์๊ฐ์ ํ์๋ก ํ๋ค.
def select(arr, k):
for i in range(0, k):
minIndex = i
for j in range(i+1, len(arr)):
if arr[minIndex] > arr[j]:
minIndex = j
arr[i], arr[minIndex] = arr[minIndex], arr[i]
return arr[k-1]
์๊ฐ๋ณต์ก๋
O(n²)
์ ํ์ ๋ ฌ
์ฃผ์ด์ง ์๋ฃ๋ค ์ค์์ ๊ฐ์ฅ ์์ ์์๋ถํฐ ์ฐจ๋ก๋๋ก ์ ํํ์ฌ ์์น๋ฅผ ๊ตํํ๋ ๋ฐฉ์
์์ ์ดํด๋ณธ ์ ๋ ์ ์๊ณ ๋ฆฌ์ฆ์ ์ ์ฒด ์๋ฃ์ ์ ์ฉํ ๊ฒ.
์ ๋ ฌ๊ณผ์
- ์ฃผ์ด์ง ๋ฆฌ์คํธ ์ค์์ ์ต์๊ฐ์ ์ฐพ๋๋ค.
- ๊ทธ ๊ฐ์ ๋ฆฌ์คํธ์ ๋งจ ์์ ์์นํ ๊ฐ๊ณผ ๊ตํํ๋ค.
- ๋งจ ์ฒ์ ์์น๋ฅผ ์ ์ธํ ๋๋จธ์ง ๋ฆฌ์คํธ๋ฅผ ๋์์ผ๋ก ์์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ค.
- ๋ฏธ์ ๋ ฌ ์์๊ฐ ํ๋ ๋จ์ ์ํฉ์์๋ ๋ง์ง๋ง ์์๊ฐ ๊ฐ์ฅ ํฐ ๊ฐ์ ๊ฐ๊ฒ ๋๋ฏ๋ก ์คํ์ ์ข ๋ฃํ๊ณ ์ ํ ์ ๋ ฌ์ด ์๋ฃ ๋๋ค.
์๊ฐ๋ณต์ก๋
O(n²)
๊ตฌํ
## ์๊ณ ๋ฆฌ์ฆ
def selectionSort(a[], N) :
for i from 0 to n-2
a[i], ... , a[n-1] ์์ ์ค ์ต์๊ฐ a[k] ์ฐพ์
a[i]์ a[k] ๊ตํ
## ์ ํ ์ ๋ ฌ
def selectionSort(a, N) :
for i in range(N-1) :
minIdx = i # ์ต์ ์ธ๋ฑ์ค๋ง ์ฐพ๊ธฐ! value๊น์ง ์ฐพ์ง x
for j in range(i+1, N):
if a[minIdx] > a[j] :
minIdx = j
a[i], a[minIdx] = a[minIdx], a[i] # ๊ฐ๋ค๋ฉด ๊ฑด๋๋ฐ๋ ์กฐ๊ฑด๋ฌธ ์ถ๊ฐ? < ์คํํ ๊ฑฐ๋ง ๋์ด๋จ ํ์์์
arr = [7, 2, 5, 3, 4, 3]
N = len(arr)
for i in range(N-1):
minIdx = i
for j in range(i+1, N):
if arr[minIdx] > arr[j]:
minIdx = j
arr[minIdx], arr[i] = arr[i], arr[minIdx] # if๋ฌธ ๋ฃ์ง ๋ง๊ธฐ ์๊ฐ๋ณด๋ค ์๊ทผ ์ก์๋จน์
'๐ถ Programming > Algorithm' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
5. Search ๊ฒ์ (0) | 2022.10.19 |
---|---|
4. Array Extra ๋ฐฐ์ด (0) | 2022.10.15 |
2. Array ๋ฐฐ์ด (2) | 2022.10.01 |
1. Algorithm ์๊ณ ๋ฆฌ์ฆ (4) | 2022.09.29 |