Python 선형검색, 이진검색, 순위, 버블정렬, 삽입정렬, 선택정렬

1. 선형검색

• 선형으로 나열되어 있는 데이터를 순차적으로 스캔하며 원하는 값을 찾는 방식

target = 3
numbers = [9, 12, 1, 6, 15, 7, 5, 3, 10]

for idx, num in enumerate(numbers):
  if num == target:
    print("Target found at index", idx)
    
# 출력 예시
# Target found at index 7 

2. 이진검색

• 정렬되어 있는 자료구조에서 중앙값과의 크고 작음을 이용하여 데이터를 효율적으로 검색하는 방식

target = 15
numbers = [1, 3, 5, 6, 7, 9, 10, 12, 15] # 정렬된 상태

min_idx = 0
max_idx = len(numbers) - 1
mid_idx = max_idx // 2
mid_val = numbers[mid_idx]

if target == mid_val:
  target_idx = mid_idx

elif target < mid_val:
  for idx in range(min_idx, mid_idx):
    if numbers[idx] == target:
      target_idx = idx

else:
  for idx in range(mid_idx, max_idx+1):
    if numbers[idx] == target:
      target_idx = idx

print("Target Index:", target_idx)
  
# 출력 예시
# Target Index: 8

3. 순위

• 수의 크고 작음을 활용하여 순서를 정하는 방식

scores = [98, 87, 85, 92, 93, 84]
ranks = [0 for score in range(len(scores))]
  
for idx, score1 in enumerate(scores):
  for score2 in scores:
    if score1 < score2:
      ranks[idx] += 1

ranks = [rank + 1 for rank in ranks]

for idx, score in enumerate(scores):
  print(f"Score: {score} -> Rank: {ranks[idx]}")
  
# 출력 예시
# Score: 98 -> Rank: 1
# Score: 87 -> Rank: 4
# Score: 85 -> Rank: 5
# Score: 92 -> Rank: 3
# Score: 93 -> Rank: 2
# Score: 84 -> Rank: 6 

4. 버블정렬

• 처음부터 끝까지 인접하는 두 인덱스를 비교함으로써 큰 숫자를 끝으로 옮겨 정렬하는 방식

scores = [98, 87, 85, 92, 93, 84]

print(f"Before: {scores}")

for i in range(len(scores)-1):
  for j in range(len(scores)-1-i): # 큰 수는 맨 뒤로 보내는 것이 목적
    if scores[j] > scores[j+1]:
      scores[j], scores[j+1] = scores[j+1], scores[j]

print(f"After: {scores}")

# 출력 예시
# Before: [98, 87, 85, 92, 93, 84]
# After: [84, 85, 87, 92, 93, 98]

5. 삽입정렬

• 정렬되어 있는 자료구조에 대하여 값에 대한 비교를 수행한 후, 적합한 위치를 찾아 삽입하여 정렬하는 방식

num_list = [5, 10, 2, 1, 0]

for i in range(1, len(num_list)):
  for j in range(i, 0, -1): # 매 회차마다 정렬된 자료구조 다음 인덱스부터 비교하는 것이 목적
    if num_list[j-1] > num_list[j]:
      num_list[j-1], num_list[j] = num_list[j], num_list[j-1]

print(num_list)

# 출력 예시
# [0, 1, 2, 5, 10]

6. 선택정렬

• 주어진 자료구조 내 최소값을 찾아, 그 값을 맨 앞의 값과 교체하며 정렬하는 방식

num_list = [4, 2, 5, 1, 3]

for i in range(len(num_list)-1):
  min_idx = i  # 작은 수는 맨 앞으로 보내는 것이 목적
  
  for j in range(i+1, len(num_list)):
    if num_list[min_idx] > num_list[j]:
      min_idx = j
      
  num_list[i], num_list[min_idx] = num_list[min_idx], num_list[i]

print(num_list)

# 출력 예시
# [1, 2, 3, 4, 5]

*이 글은 제로베이스 데이터 취업 스쿨의 강의 자료 일부를 발췌하여 작성되었습니다.