TIL #11 : 버블 정렬, 선택 정렬, 삽입 정렬

📝 버블 정렬

인접한 두 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

• n개의 데이터가 있는 경우 최대 n-1번의 로직 적용
• 로직을 1번 적용할 때마다, 가장 큰 숫자가 뒤에서 하나씩 결정됨

def BubbleSort(data):
    for i in range(len(data)-1):
        swap =0
        for j in range(len(data)-1-i):
            if data[j]> data[j+1]:
                data[j], data[j+1] = data[j+1], data[j]
                swap +=1
        if swap ==0:  ➜ 이미 정렬된 상태의 데이터란 의미로 for문 나가기
            break
    return data

👏 시간 복잡도

최선	평균	최악
O(n^2)	O(n^2)	O(n^2)

📝 선택 정렬

▪ 주어진 데이터 중, 최소값을 찾음
▪ 해당 최소값을 데이터 맨 앞에 위치한 값과 교체!

def SelectionSort(data):
    for i in range(len(data)-1):
        minIdx = i
        for j in range(i+1, len(data)):
            if data[minIdx] > data[j]:
                minIdx = j
        data[minIdx], data[i] = data[i], data[minIdx]
    return data

👏 시간 복잡도

최선	평균	최악
O(n^2)	O(n^2)	O(n^2)

📝 삽입 정렬

▪ 두 번째 인덱스 부터 시작 ➜ key 값
▪ key 값 앞에 있는 데이터부터 비교해서 key 값 더 작으면 비교한 값을 뒤 인덱스로 복사
👉 key 값이 더큰 데이터를 만날 때까지 반복!
▪ key 값보다 큰 데이터를 만나면 그 데이터 뒤에 key 값을 삽입!

def InsertionSort(data):
    for i in range(1,len(data)):
        key = data[i]
        for j in range(i-1,-1,-1):
            if key < data[j]:
                data[j+1], data[j] = data[j], data[j+1]
            else:
                break
    return data

👏 시간 복잡도

최선	평균	최악
O(n)	O(n^2)	O(n^2)