[알고리즘] 정렬1 - 선택 정렬, 거품 정렬, 삽입 정렬 구현해보기

 

 

선택 정렬  : 가장 작은 데이터를 선택하여 맨 앞 부터 순서대로 정렬해 나가는 알고리즘

거품 정렬 : 오른쪽부터 인접한 두 개의 원소를 비교하여 자리를 교환하는 방식의 정렬 알고리즘

삽입 정렬  : 모든 요소를 앞에서 부터 정렬 범위를 확장시켜나가며 정렬을 진행하는 알고리즘

 

---

 

1. 선택 정렬(Selection Sort) 구현

 

'''
# 시간복잡도 (n^2)
'''

def selection_sort(lst):
    for i in range(len(lst)-1):
    	# 최저점
        min_idx = i
        for j in range(i+1, len(lst)):
            if lst[min_idx] > lst[j]:
                min_idx = j
        lst[i], lst[min_idx] = lst[min_idx], lst[i]

    return lst


# 테스트 
a = [4, 2, 7, 1, 9, 3]
print(selection_sort(a))

 

 

 

2. 거품 정렬(Bubble Sort) 구현

 

def bubble_sort(lst):
    for i in range(len(lst)-1):

        # 이미 정렬되어 있는지 체크하는 변수
        isSort = True

        # 한 턴이 끝나면 맨 뒤는 가장 큰 수가 정렬되어 있으므로,
        # 정렬할 필요가 없어 -i를 해준다
        for j in range(len(lst)-1-i):
        	# 오름차순 기준 (내림차순으로 하고 싶을 경우 부호 반대(<))
            if lst[j] > lst[j+1]: 
                lst[j], lst[j+1] = lst[j+1], lst[j]
            isSort = False

        if isSort == True:
            break

    return lst


# 테스트
a = [4, 2, 7, 1, 9, 3]
print(bubble_sort(a))

 

 

 

3. 삽입 정렬(Insertion Sort) 구현

 

def insertion_sort(lst):
    for i in range(len(lst)-1):
        for j in range(i+1, 0, -1):
            if lst[j] < lst[j-1]:
                lst[j], lst[j-1] = lst[j-1], lst[j]
            else:
                break
    return lst


# 테스트
a = [4, 2, 7, 1, 9, 3]
print(insertion_sort(a))