[5일차] 04 정렬 : 04-1 버블 정렬, 04-2 선택 정렬

함께 푼 문제

[백준 / 정렬] 23968 : 알고리즘 수업 - 버블 정렬 1 (python)

[백준 / 정렬] 23881 : 알고리즘 수업 - 선택 정렬 1 (python)

 

버블 정렬

데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식

• 간단하게 구현 가능
• 시간 복잡도는 O(n^2)으로 속도가 느린 편.
• 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 그 영역 뒤에 있는 데이터가 모두 정렬됐다는 뜻이므로 프로세스를 종료하여 시간복잡도를 줄일 수 있다.

파이썬 구현

A = [3, 1, 2, 5, 4]
N = len(A)

for i in range(N-1, 0, -1):
    flag = True #swap이 발생했는지 확인

    for j in range(i):
        if A[j] > A[j+1]:
            A[j], A[j+1] = A[j+1], A[j]
            flag = False   

    if flag:  #swap이 한 번도 발생하지 않았으므로 종료
        break

print(A) #1,2,3,4,5

 

선택 정렬

대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식

• 구현하기 복잡함.
• 시간 복잡도는 O(n^2)으로 속도가 느린 편.
• 코딩테스트에서 많이 사용하지 않음.

파이썬 구현

A = [8, 9, 6, 10, 7]
N = len(A)

for i in range(N):
    Min = i
    for j in range(i, N):
        if A[Min] > A[j]:
            Min = j
    if Min != i:
        A[Min], A[i] = A[i], A[Min]

print(A) #6, 7, 8, 9, 10