[알고리즘] 버블 정렬과 에라토스테네스의 체

1. 버블 정렬

•  인접한 두 원소를 비교하여 서로 바꾸면서 정렬하는 방법
• 시간 복잡도는 O(n^2)

 -예제

출처:https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC

 위와 같이 인접한 원소를 비교하여 큰 값을 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다.

 -코드

def bubleSort(a):
    Sorted = False
    while not Sorted:
        Sorted = True
        for i in range(1, len(a)):
            if a[i - 1] > a[i]:
                a[i - 1], a[i] = a[i], a[i - 1]
                Sorted = False

 

2. 에라토스테네스의 체

• 소수를 찾는 방법의 하나로 에라토스테네스가 발견한 방법
• 시간 복잡도는 O(Nlog(log(N)))

 -예시

출처: https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

 위 이미지와 같이 2부터 n까지 자기 자신으로 나누어서 나머지가 0이 되는 수를 모두 제외하여 소수를 찾습니다.

 

 -코드

def sieve(n):
    candidates = list(range(2, n))  # 소수일 수 있는 수
    i = 0
    while i < len(candidates):
        prime = candidates[i]
        j = i + 1
        while j < len(candidates):
            if candidates[j] % prime == 0:  # 나누어서 나머지가 0이면 숫자 제외
                candidates.pop(j)
            else:
                j += 1
        i += 1
    return candidates