자료구조 08. 정렬 O(n2)-버블솔트,삽입정렬,선택정렬

2019.07.03 TIL

(TIL은 스스로 이해한 것을 바탕으로 정리한 것으로 오류가 있을 수 있습니다)

# 질문에 답하기

1. 정렬 O(n2) - 그나마 제일 좋은것은 insertion이 제일 좋다.

2. 버블솔트

3. 삽입정렬

4. 선택정렬

1. 버블 솔트

• 일반적으로 for문이 2개면 n2이다.

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


if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    bubble_sort(arr)
    print(arr)

2. 삽입 정렬

• [5, 2, 6, 1, 8]
• 첫 번째 인덱스는 지나가고 2번 째 인덱스부터 temp에 넣어서 그 숫자를 첫 번째 인덱스부터 비교한다.
• i를 temp에 넣고, j는 i-1부터 인덱스를 줄여가며 temp와 비교한다. i의 앞쪽은 정렬되어 있을 것이기 때문에 그 해당 위치에 insert를 하는 것이기 때문에 insertion이다.
• insertion은 끝까지 다 비교하지 않아도 되기 때문에 bubble_sort보다 더 효율적이다.

while문을 통한 구현

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        temp = arr[i]
        j = i - 1
        while j!=-1:
            if arr[j] > temp:
                arr[j+1] = arr[j]
                j-=1
            else:
                break
        arr[j+1] = temp

if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    insertion_sort(arr)
    print(arr)    

for문을 통한 구현

def insertion_sort(li):
    n=len(li)
    temp=None
    for i in range(1, n):
        temp=li[i]
        for j in range(i-1, -2, -1): #-2까지 해야지 -1까지 된다.
            if j==-1:
                break
            if li[j] > temp:
                li[j+1]=li[j]
            else:
                break
        li[j+1]=temp

if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    insertion_sort(arr)
    print(arr)    

선택 정렬(selection)

• 첫 번째 인덱스에 적합한 가장 작은 값을 선택한다.
• 그리고 해당 인덱스를 첫 번째 인덱스와 바꾼다.
• i를 0부터 시작해서 일단 첫 번째 인덱스를 가장 작은 값으로 가정하고 시작
• 바깥 포문은 제일 마지막꺼 전 까지만 돌면 되므로 n-2까지
• 안 쪽 포문은 i+1부터 n-1(끝까지)

def selection_sort(arr):
    n = len(arr)

    for i in range(0, n-1):
        min_idx = i
        for j in range(i+1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]

if __name__ == "__main__":
    arr = [7, 2, 5, 12, 6]
    selection_sort(arr)
    print(arr)