정렬이란?
대상이 되는 자료를 어떤 키 값에 따라 오름차순이나 내림차순으로 재배치하는 것!
🔰 순위
순위 알고리즘은 주어진 항목들을 정렬하거나 순서를 매기는 알고리즘을 의미한다.
<구현>
import random
scores = random.sample(range(50, 101), 10)
ranks = [0 for i in range(10)] # [0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
⭐ Rank 핵심
────────────────────────────────────
for idx, col in enumerate(scores):
for row in scores:
if col < row:
ranks[idx] += 1
────────────────────────────────────
print(scores)
print(ranks)
for i, s in enumerate(scores):
print(f'score:{s} \t rank:{ranks[i] + 1}')
# 실행결과
# [82, 76, 92, 86, 60, 84, 59, 68, 77, 50]
# [3, 5, 0, 1, 7, 2, 8, 6, 4, 9]
# score:82 rank:4
# score:76 rank:6
# score:92 rank:1
# score:86 rank:2
# score:60 rank:8
# score:84 rank:3
# score:59 rank:9
# score:68 rank:7
# score:77 rank:5
# score:50 rank:10
🔰 버블정렬
버블 정렬은 데이터 집합을 순회하면서 집합 내 이웃 요소들끼리의 교환을 통해 정렬을 수행하는 알고리즘이다.
- 처음부터 끝까지 인접하는 인덱스의 값을 순차적으로 비교하면서 오름차순일 경우 가장 큰 숫자를 제일 오른쪽 끝으로 옮기는 알고리즘이다.
<구현>
def bubbleSort(ns):
cns = copy.copy(ns)
⭐ Bubble Sort 핵심(오름차순)
──────────────────────────────────────────────
length = len(cns) - 1
for i in range(length):
for j in range(length - i):
if cns[j] > cns[j + 1]:
cns[j], cns[j+1] = cns[j+1], cns[j]
──────────────────────────────────────────────
return cns
> [i] for문을 돌 때마다 제일 큰 수가 오른쪽 끝으로 간다.
> [i] for문이 끝나고 오른쪽 끝으로 간 요소는 정렬이 완료된 것
> 그러므로 [j] for문은 0부터 (length - i)만큼 진행한다.🔰 삽입정렬
앞에서부터 차례대로 이미 정렬되어 있는 자료 배열과 비교해서, 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘이다.
<과정>
-
처음 Key 값은 두 번째 자료부터 시작한다.
-
첫 번째 데이터와 두 번째 데이터를 비교하여 정렬된 상태가 되도록 두 번째 데이터를 옮기면서 정렬이 시작된다.
-
이로 인해 첫 번째 데이터와 두 번째 데이터가 정렬이 완료된 영역을 형성하게 된다.
-
정렬이 완료된 영역 다음에 위치한 데이터가 그 다음 정렬대상이 된다.
-
이렇게 세 번째, 네 번째 데이터가 정렬이 완료된 영역으로 삽입되면서 정렬이 이어져 나간다.
-
즉, 정렬이 완료된 영역을 2개에서 시작해 하나씩 늘려나가는 방식으로 정렬 완료된 영역의 길이가 n이 될때까지 (n-1)회전을 하게된다.
<구현>
nums = [5, 10, 2, 1, 0]
⭐ Insertion Sort 핵심(오름차순)
────────────────────────────────────────────────────
for cur_idx in range(1, len(nums)): # 두 번째 키부터 시작
befor_idx = cur_idx - 1
cNum = nums[cur_idx]
while befor_idx >= 0 and nums[befor_idx] > cNum:
nums[befor_idx + 1] = nums[befor_idx]
befor_idx -= 1
nums[befor_idx+1] = cNum
────────────────────────────────────────────────────
print(f'nums: {nums}')
# 실행결과
# nums: [5, 10, 2, 1, 0]
# nums: [2, 5, 10, 1, 0]
# nums: [1, 2, 5, 10, 0]
# nums: [0, 1, 2, 5, 10]🔰 선택정렬
주어진 리스트 중에 최소값을 찾아, 그 값을 맨 앞에 위치한 값과 교체하는 방식으로 자료를 정렬하는 알고리즘이다.
< 과정 >
-
정렬 범위의 첫번째 키값(
i)을 선택한다. -
정렬 옵션에 따라 나머지(
j) 중 최소값 or 최대값을 탐색해 선택한다. -
키값(
i)이 최대 혹은 최소 값이라면 교환은 필요없다. -
키값(
i)과 나머지(j) 중 최대 혹은 최소 값을 교환한다.
<구현>
nums = [4, 2, 5, 1, 3]
print(f'initial nums: {nums}')
⭐ Selection Sort 핵심
────────────────────────────────────────────────────
for i in range(len(nums)-1): # i는 선택 값과 교환할 자리의 index
min_idx = i
#최소값 탐색
for j in range(i+1, len(nums)): # j는 선택 값으로 최솟값을 찾는다.
if nums[min_idx] > nums[j]:
min_idx = j
if min_idx == i: continue # 바꿀 자리의 값이 최솟값이라면 교환할 필요가 없다.
#값 교환
nums[i], nums[min_idx] = nums[min_idx], nums[i]
────────────────────────────────────────────────────
print(f'nums: {nums}')
print(f'final nums: {nums}')
# 실행결과
# initial nums: [4, 2, 5, 1, 3]
nums: [1, 2, 5, 4, 3]
nums: [1, 2, 3, 4, 5]
# final nums: [1, 2, 3, 4, 5]
ISTP(정신승리), To Be Data Scientist