[TIL] 05/26 항해99 18일차 - 버블/선택/삽입 정렬, 문제풀이

 

들어가며

알고리즘 2주차도 끝이 났다. 방향성도 어느정도 잡은 것 같고, 자신감도 많이 회복되었다. 

주차의 마무리로 보는 테스트를 공부 시작한 지 2주만에 스스로 풀어냈다는 거에 굉장한 뿌듯함이 느껴져서 괜히 다른 문제를 스스로 풀어보려고 했다가 시간을 많이 보냈다...ㅎ 결국 못풀었긴 하지만.

 

오늘의 늦은 TIL은 간단하게 정렬 알고리즘들의 개념을 쓰고, 시험으로 푼 문제를 정리해보고자 한다!

 

---

정렬

파이썬에서 정렬은 sort() 함수나 sorted() 함수로 배열이나 리스트 등등의 자료형을 아주 간단하게 오름차순 혹은 내림차순으로 나열할 수 있다. 그러므로 아래에서 정리할 정렬 알고리즘을 굳이 알아둬야하나? 라고 생각할 수 있지만 우리가 사용하는 함수가 어떤 방식으로 동작하고, 어떻게 코드로 구현되어있는지 아는건 중요하다. 마치 수학 문제를 풀 때, 공식을 이용해서 풀면 간단하지만 그 공식이 어떻게 생겨나게 되었는지 이해하고 풀 때랑은 다른 느낌인 것처럼 말이다.

 

 

버블 정렬

신기해서 가져온 그림. 버블 정렬을 실행했을 때 나오는 그림이라고 한다.

 

 

버블 정렬(Bubble sort)은 두 개의 값을 차례로 비교한 후 스왑하여 정렬하는 방식이다.

 

 

가장 쉽고 직관적이며, 아마 알고리즘 초보에게 정렬을 해보라고 하면 가장 먼저 떠올리는 방식이지 않을까 생각한다.

정렬하는 방법은 어렵지 않다. 중첩 for문을 이용하여 i와 j를 스왑해가며 완전히 정렬될 때까지 반복하면 된다. 구현하는 방법이 쉬운만큼 그 성능은 최악이므로 꼭 필요한 경우가 아니면 피하도록 하자.

 

 

버블 정렬 구현하기

def bubble_sort(lst):
    for i in range(1, len(lst)):
        for j in range(0, len(lst) - 1):
            if lst[j] > lst[j + i]:
                lst[j], lst[j + i] = lst[j + i], lst[j]

 

 

선택 정렬

역시나 신기해서 가져온 그림. 선택 정렬을 실행했을 때 나오는 그림이라고 한다.

 

 

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면, 선택 정렬(Seleted sort)은 처음부터 끝까지 훑어서 가장 작은 요소를 찾아 하나씩 정렬해주는 방식이다. 선택 정렬 역시 버블 정렬보다는 빠르지만 역시나 O(n^2)의 시간 복잡도로 좋지 않은 효율을 보여준다.

 

 

선택 정렬 구현하기

def selection_sort(lst):
    iters = len(lst) - 1

    # 값을 두개 비교하는 거니까 len(lst) - 1까지 반복해줘야한다.
    for iter in range(iters):
        # 최솟값의 인덱스를 일단 첫번째 인덱스로 지정해준다.
        minimum = iter

        for cur in range(iter + 1, len(lst)):
            # 첫번째 다음 인덱스부터 반복문을 돌면서 최솟값을 찾는다.
            if lst[cur] < lst[minimum]:
                minimum = cur

        # 최솟값을 들고있는 인덱스를 발견했다면 스왑해주고 반복해준다.
        if minimum != iter:
            lst[minimum], lst[iter] = lst[lst], lst[minimum]

    return lst

 

 

삽입 정렬

삽입 정렬을 알기 쉽게 만든 그림.

 

 

앞쪽이 정렬되어 있다고 가정을 하고 하나씩 범위를 넓혀가며 요소를 삽입하여 정렬하는 방식이다. 위의 두개에 비해서 빠른 속도를 보여주지만, 작은 값이 뒤쪽에 몰려있으면(내림차순의 경우는 큰 값) 아주 나쁜 성능을 보여준다. 다만 이미 정렬되어있는 자료구조에 자료를 하나씩 삽입/제거하는 경우에는 현실적으로 좋은 효율을 내는 정렬 알고리즘이 된다고 한다.

 

 

삽입 정렬 구현하기

def insertion_sort(lst):
    # 첫번째 요소는 정렬이 되어있다고 가정하고 시작한다.
    for i in range(1, len(lst)):
        # 삽입하려는 요소를 변수에 담아준다.
        val = lst[i]

        # 비교 대상의 인덱스는 삽입하려는 인덱스의 바로 앞 요소이므로 삽입 인덱스에 -1을 해준다.
        cmp = i - 1

        # 삽입하려는 요소와 비교 하려는 요소의 대소를 비교해준다.
        # 정렬되어있는 앞쪽 리스트를 모두 탐색하기 때문에 점점 인덱스는 줄어든다.
        while lst[cmp] > val and cmp >= 0:
            # 비교하려는 요소의 다음요소 즉, 삽입하려는 요소의 위치에 비교하려는 요소를 넣고,
            # 비교롤 계속하거나, 비교가 끝났다면 while문을 탈출한다.
            lst[cmp + 1] = lst[cmp]
            cmp -= 1

        # 비교하려는 요소의 인덱스를 줄여나갔으므로, 삽입하려는 요소가 와야하는 위치는 cmp + 1이다.
        lst[cmp + 1] = val

    return lst

 

 

문제 풀이

[Programmers] 방문 길이

[Programmers] 방문 길이

 

 

---

마치며

오늘의 한마디 by 재호님 - 일단 해라.

 

 

오늘의 항해톡은 정말 중요한 개념들이 많았다. OSI 7계층, process & thread, 동기 & 비동기, DB INDEX까지...

시간 관계상 못들은 발표들도 있었지만 이전에 정리를 하려고 했으나 못했던 부분이나 정리를 했음에도 이해가 잘 안됐던 부분들을 알기 쉽게 설명해주셔서 도움이 굉장이 많이 되었던 시간이었다!

 

조만간 꼭 시간을 내서 블로그에 정리하도록 하자!

 

 

 

항해77 팀원들끼리 새벽 3시에

---

출처

 

정렬 알고리즘

 

<파이썬 알고리즘 인터뷰>