버블, 선택, 삽입 정렬

버블 정렬

def bubbleSort():  ##개선된 버블 정렬
    global n
    size = n
    while True:
        flag = True
        for i in range(size-1):
            if lis[i] > lis[i+1]:
                temp = lis[i]
                lis[i] = lis[i+1]
                lis[i+1] = temp
                flag = False
        if flag == True:
            break

n = int(input())
lis = list(map(int, input().split()))
bubbleSort()
for l in lis:
    print(l, end=' ')

• 리스트 전체(n)를 돌며 앞뒤로 비교하여 정렬하는데 이를 n번 반복
• 시간 복잡도 O(n^2)

선택 정렬

import sys

def selectionSort():
    for i in range(len(li)):
        min_num = li[i]
        min_index = i
        for j in range(i+1, len(li)):
            if li[j] < min_num:
                min_index = j
                min_num = li[min_index]
        temp = li[i]
        li[i] = li[min_index]
        li[min_index] = temp

n = int(input())
li = list(map(int, input().split()))
selectionSort()
for l in li:
    print(l, end=" ")

• 리스트 전체(n)를 돌며 최솟값을 n번 찾아 정렬
• 시간 복잡도 O(n^2)

삽입 정렬

def insertionSort():
    for i in range(1, len(arr)):
        j = i - 1
        key = arr[i]
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j+1] = key

n = int(input())
arr = list(map(int, input().split()))
insertionSort()
for a in arr:
    print(a, end=" ")

• 두 번째 원소부터 시작하여 첫 번째 원소까지 내려가며 자신이 위치해야 하는 곳을 찾아 삽입
• 시간 복잡도 O(n^2)

💡 세 정렬 간 수행시간 비교
1. 버블 정렬이 일반적으로 가장 느리다.
2. 선택 정렬은 배열의 상태(정렬되어있는지 아닌지)와 상관없이 항상 동일한 수행 시간이 걸린다.
3. 일반적으로 셋 중 가장 빠르지만 값이 내림차순(반대로) 정렬되어 있는 경우 성능이 많이 떨어진다.
4. 삽입 정렬의 경우 정렬된 배열에 몇 가지 값을 추가로 삽입하고 다시 정렬하는 경우에 성능이 좋다.