기본 정렬 알고리즘(버블, 삽입, 선택)

1. 버블 정렬

• for문을 한 번 돌면 마지막에는 무조건 큰 숫자가 담긴다
• 기준 인덱스와 바로 뒤 인덱스를 비교하여 앞에가 크면 자리를 바꾼다
• 이중 for문을 돈다 ( 처음 for은 처음 부터 끝까지 -1, 두번째 for은 총 길이 - 처음for문의 인덱스 -1)
• 시간 복잡도는 O($n^2$)
• 정확하게는 $\frac { n * (n - 1)}{ 2 }$

def bubblesort(list_):
    for idx1 in range(len(list_) - 1):
        for idx2 in range(len(list_) - idx1 - 1):
            if list_[idx2] > list_[idx2+1]:
                list_[idx2], list_[idx2+1] = list_[idx2+1], list_[idx2]
    return list_

• 한 번도 스왑swap이 안 된다면 정렬이 되어있는 상태이므로 끝내줄 수 있다.

def bubblesort(list_):
    for idx1 in range(len(list_) - 1):
        swap = False
        for idx2 in range(len(list_) - idx1 - 1):
            if list_[idx2] > list_[idx2+1]:
                list_[idx2], list_[idx2+1] = list_[idx2+1], list_[idx2]
                swap = True
        if swap == False:
            break
    return list_

2. 삽입 정렬

• 기준과 기준 다음 데이터를 비교하고 기준보다 작으면 기준 역순으로 작을 때마다 자리를 바꿔주며 정렬하는 것
• 이중 for문을 돈다(처음 for은 len(리스트)-1, 두번째 for은 처음보다 1큰 인덱스에서부터 역순으로 1번째 까지
• 시간 복잡도는 O($n^2$)
• 정확하게는 O($n*(n-1)\over2$)$\frac { n * (n - 1)}{ 2 }$

#나
def insert_sort(ary):
    for idx1 in range(len(ary)-1):
        if li[idx1] > li[idx1 + 1]:
            for idx2 in range(idx1+1,0,-1):
                if ary[idx2-1] > ary[idx2]:
                    ary[idx2-1], ary[idx2] = ary[idx2], ary[idx2-1]
                else:
                    break
    return ary

#패캠
def insertion_sort(data):
    for index in range(len(data) - 1):
        for index2 in range(index + 1, 0, -1):
            if data[index2] < data[index2 - 1]:
                data[index2], data[index2 - 1] = data[index2 - 1], data[index2]
            else:
                break
    return data

#스파르타코클
def insertion_sort(array):
    n = len(array)
    for i in range(1, n):
        for j in range(i):
            if array[i - j - 1] > array[i - j]:
                array[i - j - 1], array[i - j] = array[i - j], array[i - j - 1]
            else:
                break
    return array

3. 선택 정렬

• 해당 리스트에서 최솟값을 찾아서 현재의 맨 앞과 바꾼다
• 시간 복잡도는 O($n^2$)
• 정확하게는 $\frac { n * (n - 1)}{ 2 }$

def select_sort(li):
    for idx1 in range(len(li)-1):
        low_idx = idx1
        for idx2 in range(idx1+1, len(li)):
            if li[idx2] < li[low_idx]:
                low_idx = idx2

        li[idx1],li[low_idx] = li[low_idx], li[idx1]
    return li
select_sort([2,3,4,1,6,4,9,2])