TIL

선택정렬 O(n^2)

arr = [18,6,66,44,9,22,14]

temp_min_index=0


length=len(arr)

for num in range(length):
    if num == length-1:
        break
    temp_min = arr[num]

    for i in range(num,length):
        if temp_min > arr[i]:
            temp_min = arr[i]
            temp_min_index = i
            # print(temp_min)
            # print(temp_min_index)
        else:
            continue # 최소값 6찾음
    
    temp = arr[num]
    arr[num] =temp_min
    arr[temp_min_index] = temp

print(arr)


# 시간 복잡도 O(n^2)

삽입 정렬 ( O(N^2) )

1.이미 정렬된 배열에 새로운 데이터 넣을때 유용함

arr =[3,5,6,11,13,2,9,6]

list_len = len(arr)

#선택 정렬

for num in range(list_len-1): #마지막은 요소는 이미 다 정렬이 된 상태
    min_num = arr[num]  #임시 최소값 설정

    for i in range(num,list_len):#최댓값 선택, 삽입 이후 가장 왼쪽값 제외
        if min_num > arr[i]:
            min_num = arr[i]
            min_num_index = i
        else:
            continue



    temp = arr[num] #가장 왼쪽 배열 값
    arr[num] = min_num #가장 왼쪽 배열에 실제 가장 작은값 넣기
    arr[min_num_index] = temp #있던 자리에 첫번째 요소 값 넣기

print(arr)

arr.append(int(input())) #값 추가



appended_len = len(arr)

key = arr[appended_len-1]


for i in range(appended_len-1,0,-1):

    if key < arr[i-1]: #왼쪽칸 비교
        arr[i] = arr[i-1] # 오른쪽 shift

    else :#키가 왼쪽 보다 클때
        arr[i] = key
        break
print(arr)

2.하나씩 삽입하는 정렬