지혜의 개발공부로그

Data Structure, O(N^2) Sorting

28 Feb 2020 | Data Structure

개인공부 후 자료를 남기기 위한 목적임으로 내용 상에 오류가 있을 수 있습니다.
잘못된 부분이 있다면 댓글로 남겨주세요! :)

O(N^2) Sorting

  • Worst case
  • without divide and conquer approach
  • Sequential comparisons with two index
    • nested loop that ranges
    • outer loop: the first to the end
    • inner loop: from the outer loop’s index to end
  • Variants
    • Insertion Sort
    • Selection Sort
    • Bubble Sort
  • Prods and cons
    • 단점: 시간 복잡도
    • 장점: 구현이 쉽다.

Selection sort algorithm

def selection_sort(lst):
    for i in range(len(lst)):
        for j in range(i+1,  len(lst)):
            if lst[i] < lst[j]:
                lst[i], lst[j] = lst[j], lst[i]
    return lst

selection_sort(lst)
[1, 9, 3, 4, 2, 5]
[1, 2, 9, 4, 3, 5]
[1, 2, 3, 9, 4, 5]
[1, 2, 3, 4, 9, 5]
[1, 2, 3, 4, 5, 9]
[1, 2, 3, 4, 5, 9]
  • Total iteration

Bubble sort algorithm

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

bubble_sort(lst)
[2, 3, 4, 1, 5, 9]
[2, 3, 1, 4, 5, 9]
[2, 1, 3, 4, 5, 9]
[1, 2, 3, 4, 5, 9]
[1, 2, 3, 4, 5, 9]

Insertion sort algorithm

def insertion_sort(lst):
    for i in range(len(lst)):
        key = lst[i]
        # i - 1부터 시작해서 왼쪽으로 하나씩 확인
        # 왼쪽 끝까지(0번 인덱스) 다 봤거나
        # key가 들어갈 자리를 찾으면 끝냄
        j = i - 1
        while j >= 0 and lst[j] > key:
            lst[j + 1] = lst[j]
            j = j - 1
        # key가 들어갈 자리에 삽입
        # 왼쪽 끝까지 가서 j가 -1이면 0번 인덱스에 key를 삽입
        lst[j + 1] = key
        print(lst)
    return lst

[9, 2, 3, 4, 1, 5]
[2, 9, 3, 4, 1, 5]
[2, 3, 9, 4, 1, 5]
[2, 3, 4, 9, 1, 5]
[1, 2, 3, 4, 9, 5]
[1, 2, 3, 4, 5, 9]

Related Posts