Python 실습(선형 검색, 이진 검색, 순위 정렬, 버블 정렬, 삽입 정렬, 선택 정렬, 병합 정렬)

1. 선형 검색 프로그램

• 1 부터 20까지의 정수 중 난수를 10개 추출하여 숫자 7에 대해 선형 검색을 수행하는 프로그램을 만드시오. (단, 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없는 경우 -1을 출력하시오.)

import random

target_number = 7
num_list = random.sample(range(1,21), 10)
print(f"탐색 대상: {num_list}")

def linear_search(num_list):
  flag = False
  loc_idx = 0
  
  for i, num in enumerate(num_list):
    if num == target_number:
      flag = True
      loc_idx = i

    else:
      pass

  return loc_idx if flag else -1

print(f"탐색 결과: {linear_search(num_list)}")
  
# 출력 예시
# 탐색 대상: [11, 10, 8, 16, 14, 13, 19, 7, 12, 9]
# 탐색 결과: 7
# 탐색 대상: [16, 19, 9, 5, 11, 12, 14, 4, 15, 18]
# 탐색 결과: -1 

2. 이진 검색 프로그램

• 1 부터 20까지의 정수 중 난수를 20개 추출 및 정렬하여 숫자 7에 대해 이진 검색을 수행하는 프로그램을 만드시오. (단, 검색에 성공하면 해당 정수의 인덱스를 출력하고, 검색 결과가 없는 경우 -1을 출력하시오.)

import random

target_num = 7
num_list = sorted(random.sample(range(1, 21), 10)) # 정렬 필수
print(f"탐색 대상: {num_list}")

def binary_search(num_list):

  flag = False
  loc_idx = 0
  max_idx = len(num_list)-1
  min_idx = 0
  tmp_idx = -1

  while target_num >= num_list[0] and target_num <= num_list[len(num_list)-1]:

    mid_idx = (min_idx + max_idx) // 2
    mid_num = num_list[mid_idx]

    # 계속되는 나눗셈으로 인한 무한루프 방지
    if tmp_idx == mid_idx:
      break

    # 직전 idx와 변동이 없는지 검사하는 용도
    tmp_idx = mid_idx

    if target_num == mid_num:
      flag = True
      loc_idx = mid_idx
      break

    elif target_num < mid_num:
      max_idx = mid_idx

    else: # target_num > mid_num
      min_idx = mid_idx

  return loc_idx if flag else -1

print(f"탐색 결과: {binary_search(num_list)}")

# 출력 예시
# 탐색 대상: [1, 3, 5, 8, 9, 10, 11, 14, 19, 20]
# 탐색 결과: -1
# 탐색 대상: [1, 2, 4, 7, 9, 10, 12, 13, 14, 16]
# 탐색 결과: 3

3. 순위 정렬 프로그램

• 50 부터 100까지의 정수 중 난수를 20개 추출하여 큰 숫자부터 작은 숫자 순으로 순위에 따라 정렬하는 프로그램을 만드시오.

import random

num_list = random.sample(range(50, 101), 20)
print(f"정렬 대상: {num_list}")

def rank_search(num_list):
  rank_list = [0 for num in range(len(num_list))]

  for self_idx, self_num in enumerate(num_list):
    for other_num in num_list:
      if self_num < other_num:
        rank_list[self_idx] += 1

  print(f"순위 정보: {[rank+1 for rank in rank_list]}")
  
  sorted_list = [0 for num in range(len(num_list))]

  for idx, rank in enumerate(rank_list):
  	sorted_list[rank] = num_list[idx]
        
  return sorted_list

print(f"정렬 결과: {rank_search(num_list)}")

# 출력 예시
# 정렬 대상: [81, 90, 58, 84, 74, 100, 61, 85, 76, 53, 79, 69, 54, 62, 89, 63, 88, 92, 78, 83]
# 순위 정보: [9, 3, 18, 7, 13, 1, 17, 6, 12, 20, 10, 14, 19, 16, 4, 15, 5, 2, 11, 8]
# 정렬 결과: [100, 92, 90, 89, 88, 85, 84, 83, 81, 79, 78, 76, 74, 69, 63, 62, 61, 58, 54, 53]

4. 버블 정렬 프로그램

• 1 부터 20까지의 정수 중 난수를 20개 추출한 뒤 버블 정렬 알고리즘에 기반하여 오름차순 또는 내림차순으로 정렬하는 프로그램을 만드시오.

import random

num_list = random.sample(range(1, 21), 10)
print(f"정렬 대상: {num_list}")

def bubble_sort(num_list, desc=False):

        for i in range(len(num_list)-1, 0, -1):
            for j in range(i):
                
                if desc == True:
                    if num_list[j] < num_list[j+1]:
                        num_list[j], num_list[j+1] = num_list[j+1], num_list[j]   
                        
                elif desc == False:
                    if num_list[j] > num_list[j+1]:
                        num_list[j], num_list[j+1] = num_list[j+1], num_list[j]
                        
        return num_list

print(f"정렬 결과 (오름차순): {bubble_sort(num_list)}")
print(f"정렬 결과 (내림차순): {bubble_sort(num_list, desc=True)}")

# 출력 예시
# 정렬 대상: [6, 7, 3, 15, 19, 20, 11, 10, 13, 9]
# 정렬 결과 (오름차순): [3, 6, 7, 9, 10, 11, 13, 15, 19, 20]
# 정렬 결과 (내림차순): [20, 19, 15, 13, 11, 10, 9, 7, 6, 3]

5. 삽입 정렬 프로그램

• 1 부터 20까지의 정수 중 난수를 20개 추출한 뒤 삽입 정렬 알고리즘에 기반하여 오름차순과 내림차순으로 정렬하는 프로그램을 만드시오.

import random

num_list = random.sample(range(1, 21), 10)
print(f"정렬 대상: {num_list}")


def insertion_sort(num_list, desc=False):

    for i in range(1, len(num_list)):
        for j in range(i, 0, -1):
            
            if desc == True:
                if num_list[j] > num_list[j-1]:
                    num_list[j], num_list[j-1] = num_list[j-1], num_list[j]

            elif desc == False:
                if num_list[j] < num_list[j-1]:
                    num_list[j], num_list[j-1] = num_list[j-1], num_list[j]

    return num_list


print(f"정렬 결과 (오름차순): {insertion_sort(num_list)}")
print(f"정렬 결과 (내림차순): {insertion_sort(num_list, desc=True)}")

# 출력 예시
# 정렬 대상: [17, 19, 12, 2, 5, 9, 1, 11, 4, 13]
# 정렬 결과 (오름차순): [1, 2, 4, 5, 9, 11, 12, 13, 17, 19]
# 정렬 결과 (내림차순): [19, 17, 13, 12, 11, 9, 5, 4, 2, 1]

6. 선택 정렬 프로그램

• 1 부터 20까지의 정수 중 난수를 20개 추출한 뒤 선택 정렬 알고리즘에 기반하여 오름차순과 내림차순으로 정렬하는 프로그램을 만드시오.

import random

num_list = random.sample(range(1, 21), 10)
print(f"정렬 대상: {num_list}")


def selection_sort(num_list, desc=False):

    for i in range(0, len(num_list)-1):
        target_idx = i

        for j in range(i + 1, len(num_list)):

            if desc == False:
                if num_list[j] < num_list[target_idx]:
                    target_idx = j

            elif desc == True:
                if num_list[j] > num_list[target_idx]:
                    target_idx = j

        num_list[i], num_list[target_idx] = num_list[target_idx], num_list[i]

    return num_list


print(f"정렬 결과 (오름차순): {selection_sort(num_list)}")
print(f"정렬 결과 (내림차순): {selection_sort(num_list, desc=True)}")

# 출력 예시
# 정렬 대상: [20, 4, 3, 9, 6, 19, 17, 13, 11, 8]
# 정렬 결과 (오름차순): [3, 4, 6, 8, 9, 11, 13, 17, 19, 20]
# 정렬 결과 (내림차순): [20, 19, 17, 13, 11, 9, 8, 6, 4, 3]

7. 병합 정렬 프로그램

• 1 부터 20까지의 정수 중 난수를 20개 추출한 뒤 병합 정렬 알고리즘에 기반하여 오름차순과 내림차순으로 정렬하는 프로그램을 만드시오.

import random

num_list = random.sample(range(1, 21), 10)
print(f"정렬 대상: {num_list}")


def merge_sort(num_list, desc=False):

    # 리스트 길이가 2 미만일 경우 분할(재귀) 중단
    if len(num_list) < 2:
        return num_list

    mid_idx = len(num_list) // 2
    left_list = merge_sort(num_list[:mid_idx], desc=desc)
    right_list = merge_sort(num_list[mid_idx:], desc=desc)

    res = list()
    left_idx, right_idx = 0, 0

    # 분할된 리스트별 요소 접근 후 대소 구분하여 res에 추가
    while left_idx < len(left_list) and right_idx < len(right_list):

        if desc == False:
            if left_list[left_idx] < right_list[right_idx]:
                res.append(left_list[left_idx])
                left_idx += 1

            else:
                res.append(right_list[right_idx])
                right_idx += 1

        elif desc == True:
            if left_list[left_idx] > right_list[right_idx]:
                res.append(left_list[left_idx])
                left_idx += 1

            else:
                res.append(right_list[right_idx])
                right_idx += 1

    res += left_list[left_idx:]
    res += right_list[right_idx:]

    return res


print(f"정렬 결과 (오름차순): {merge_sort(num_list)}")
print(f"정렬 결과 (내림차순): {merge_sort(num_list, desc=True)}")

# 출력 예시
# 정렬 대상: [18, 5, 14, 12, 19, 8, 17, 4, 1, 3]
# 정렬 결과 (오름차순): [1, 3, 4, 5, 8, 12, 14, 17, 18, 19]
# 정렬 결과 (내림차순): [19, 18, 17, 14, 12, 8, 5, 4, 3, 1]

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