TIL 항해W4 알고리즘 - 버블정렬, 선택정렬, 삽입정렬

🏁 버블소트, 선택정렬, 삽입정렬 구현하기

 

버블소트, 선택정렬, 삽입정렬을 구현해보았다.

 

버블소트의 개념을 숙지한 다음에, 코드를 구현해보았다. 

혼자 어느정도 해보고 막힐때 답안코드를 참고하였다.

답안과는 다른 방식으로 구현하였지만, 그 과정은 동일하다.

# 버블소트 구현해보기(혼자+답안참고)
lst = [4, 6, 2, 9, 1]
def bubble(lst):
    for j in range(1, len(lst)): # 1,2,3,4
        # print('j:',j)
        # 점점 for문 범위를 줄이기 위해서 j만큼 빼줌
        for i in range(len(lst)-j): # 5-1, 5-2, 5-3, 5-4
            if lst[i] > lst[i+1]:
                lst[i], lst[i+1] = lst[i+1], lst[i]
                # print(lst)
        # for문을 한바퀴 돌면 최대값이 맨 뒤에 있음
    return lst
# print(lst)  # 구현코드를 메소드로 안감싸면, 정렬된 리스트 출력됨
print(bubble(lst))
print(bubble([3, 2, 1, 5, 3, 2, 3]))

assert bubble([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

 

선택정렬은 처음 구현해본 코드가 정렬 결과는 맞는데, 과정을 출력해보니, 정렬 과정이 다르다는 것을 발견하였다.

그래서 그 부분을 수정하여 다시 구현해보았다.

# 선택정렬 구현해보기
def select(lst):
    for i in range(len(lst)-1):
        for j in range(1, len(lst)-i):
            if lst[i] > lst[i+j]:
                lst[i], lst[i+j] = lst[i+j], lst[i]
        print('_',lst)

    return lst
# 되긴 됬는데, 선택정렬이 아닌가?
# 최소값을 찾으면서, 중간에 찾은 lst[i]보다 작은애를 발견할때마다 swap을 해주는군

# 선택정렬 완성본
def select2(lst):
    for i in range(len(lst)-1):
        minTemp = i  # 최소값을 찾기 위해 한번 도는 중에 최소값 index 임시저장
        for j in range(1, len(lst)-i):
            # if lst[i] > lst[i+j]:
            #     if lst[minTemp] > lst[i+j]:
            #         print(f'i: {i}, i+j: {i+j}, temp: {minTemp}')
            #         minTemp = i+j
            if lst[i] > lst[i+j] and lst[minTemp] > lst[i+j]:  # 상동
                # print(f'i: {i}, i+j: {i+j}, temp: {minTemp}')
                minTemp = i+j
        # print('minIdx:',minTemp)
        lst[i], lst[minTemp] = lst[minTemp], lst[i]
        # print('_',lst)

    return lst

# print(select([4, 6, 2, 9, 1]))
print(select2([4, 6, 2, 9, 1]))

 

그 다음 삽입정렬을 구현해보았다.

출처: https://commons.wikimedia.org/wiki/File:Insertion-sort.svg

index 0번째는 놔두고, 1번째 요소부터 왼쪽의 요소와 비교하여, 왼쪽보다 자기가 작으면 자리를 스왑한다.

왼쪽을 한칸씩 이동하며 계속 비교한다.

# 삽입정렬 구현해보기
def insert(lst):
    for i in range(1, len(lst)): # 1,2,3,4 현재 들어온 신병 index
        for j in range(i-1, -1, -1): # 0 / 1,0 / 2,1,0
            # print(f'i:{i}, j:{j}')
            if lst[j] > lst[i]: # 내 왼쪽에 있는 요소가 더 크면, 자리 스왑
                lst[i], lst[j] = lst[j], lst[i]
            i -= 1  # 나의 index도 왼쪽으로 한칸 이동했으니 -1 해주기

    return lst

print(insert([4, 6, 2, 9, 1]))

for i in range(5,-1,-1):
    print(i)

assert insert([4, 6, 2, 9, 1]) == [1, 2, 4, 6, 9]
assert insert([3, 2, 1, 5, 3, 2, 3]) == [1, 2, 2, 3, 3, 3, 5]

 

강의 코드와 다르게 구현하였지만, 같은 방식으로 동작하는 코드를 작성하여 기뻤다.😁

예시 리스트를 종이에 적어보고, 값을 비교해야 하는 과정을 그려보고,

인덱스의 변화를 적어보고 이를 코드로 구현하였다.