데이터 스쿨 4주차 학습내용 정리 - 2

정렬

정렬(sorting)은 배열의 요소를 오름차순 또는 내림차순으로 정렬하는 작업입니다. 정렬 알고리즘은 다양한 종류가 있습니다.

버블 정렬

버블 정렬(bubble sort)은 아래 그림과 같이 정렬 알고리즘 중 하나입니다. 버블 정렬은 배열의 인접한 두 요소를 비교하여 더 큰 값을 뒤로 이동시켜 정렬하는 방식입니다.

nums = [10, 2, 7, 21, 0]

length = len(nums) - 1
for i in range(length):
    for j in range(length - i):
        if nums[j] > nums[j+1]:
            # temp = nums[j]
            # nums[j+1] = nums[j]
            # nums[j] = temp
            nums[j], nums[j+1] = nums[j+1], nums[j]

print(nums)

파이썬에서는 해당 인덱스의 자리를 바꿀때
temp = nums[j]
nums[j+1] = nums[j]
nums[j] = temp
다음과 같은 코드를
nums[j], nums[j+1] = nums[j+1], nums[j] 로 간단하게 나타낼수 있다

실습

새 학년이 되어 학급에 20명의 새로운 학생들이 모였다. 학생들을 키 순서로 줄 세워 보자. 학생들의 키는 random 모듈을 이용해서 170 ~ 185사이로 생성한다

import copy
import random
def bubbleSort(ns, deepCopy = True):
    if deepCopy:
        cns = copy.copy(ns)
    else:
        cns = ns

    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

students = []
for i in range(20):
    students.append(random.randint(170, 186))
print(students)
print(bubbleSort(students, deepCopy=True))

170 ~ 185 사이의 난수 20개를 생성하여 버블 정렬 하였습니다.

얕은 복사와 깊은 복사

해당 코드에서 copy 모듈을 사용한 이유는 객체를 복사하면 원본 객체와 별도의 독립된 객체가 생성되는데 이렇게 하면 원본 객체를 수정해도 복사된 객체에 영향을 미치지 않아서 원본데이터 또한 출력하고 싶은 경우 다음과 같이 deepcopy를 True로 하여 카피본을 생성하여 원본데이터와 버블정렬이 된 상태를 출력할 수 있도록 하였습니다.

삽입 정렬

삽입 정렬(insertion sort)은 이미 정렬된 배열에 새로운 요소를 삽입하는 방식으로 정렬하는 알고리즘입니다. 하지만 아직 이해는 안갑니다.

nums = [5, 10, 2, 1, 0]
# 오름차순
for i1 in range(1, len(nums)):
    i2 = i1 - 1
    cNum = nums[i1]

    while nums[i2] > cNum and i2 >= 0:
        nums[i2 + 1] = nums[i2]
        i2 -= 1

    nums[i2 + 1] = cNum
    print(f'nums : {nums}')

# 내림차순
# nums = [0, 5, 2, 10, 1]
#
# for i1 in range(1, len(nums)):
#     i2 = i1 - 1
#     cNum = nums[i1]
#
#     while nums[i2] < cNum and i2 >= 0:
#         nums[i2 + 1] = nums[i2]
#         i2 -= 1
#
#     nums[i2 + 1] = cNum
#     print(f'nums : {nums}')

삽입 정렬은 아직 소화가 안되서 다음에 설명 드리겠습니다.

선택 정렬

선택 정렬(selection sort)은 배열에서 최솟값을 찾아 맨 앞으로 이동시키는 방식으로 정렬하는 알고리즘입니다.

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

for i in range(len(nums) - 1):
    minIdx = i

    for j in range(i+1, len(nums)):
        if nums[minIdx] > nums[j]:
            minIdx = j

    nums[i], nums[minIdx] = nums[minIdx], nums[i]

print(nums)

리스트의 길이를 계산하고 리스트의 마지막 원소까지 반복합니다. 리스트의 처음부터 끝까지 순회하면서 현재 원소보다 작은 원소를 찾고 찾은 원소가 있으면 현재 원소와 교환합니다.

실습

선택정렬 알고리즘을 이용해서 학생 20명의 시험 점수를 오름차순과 내림차순으로 정렬하는 모듈을 만들어보자. 시험 점수는 50부터 100까지로 한다

def sortNumber(ns, asc=True):

    if asc:
        for i in range(len(ns) - 1):
            minIdx = i

            for j in range(i+1, len(ns)):
                if ns[minIdx] > ns[j]:
                    minIdx = j
            ns[i], ns[minIdx] = ns[minIdx], ns[i]
    else:
        for i in range(len(ns) - 1):
            minIdx = i
            for j in range(i+1, len(ns)):
                if ns[minIdx] < ns[j]:
                    minIdx = j
            ns[i], ns[minIdx] = ns[minIdx], ns[i]
    return ns

import random
import selectmod as sm

scores = random.sample(range(50, 101), 20)
print(f'scores : {scores}')
print(f'scores length : {len(scores)}')
print(sm.sortNumber(scores))
print(sm.sortNumber(scores, False))

asc가 True인지 False인지에 따라서 오름차순인지 내림차순인지를 결정할 수 있도록 하였다