📌선택정렬

arr= [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
for i in range(len(arr)):
    minIdx=i
    for j in range(i+1, len(arr)):
        if arr[j] < arr[minIdx]:
            minIdx=j
    arr[i], arr[minIdx] = arr[minIdx], arr[i]
    
print(arr)

📘 시간복잡도

2중 for문 사용 : O(N^2)

• 모든 인덱스 순환 : O(N)
• 최솟값 찾은 후 현재 위치와 swap ( 3번 이동) : O(N)

📌삽입정렬

데이터를 하나씩 확인하면서 , 데이터를 적절한 위치에 삽입하는 방법

• 첫번째 숫자는 정렬되어 있닫고 가정하고 2번째 숫자부터 시작한다.
• 작은 숫자를 만날떄 까지 반복한다
  
  
  

arr= [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def insertion(arr):
    for i in range(1, len(arr)):  # 첫번째 요소 이미 정렬되어 있다고 생각 1부터 시작
        for j in range(i, 0, -1):
            if arr[j] < arr[j-1]: 
                arr[j], arr[j-1] = arr[j-1], arr[j] # 매 단계 정렬된 상태가 된다.
            else:									# else 면 이미 정렬된 상태
                break
    return arr
print(insertion(arr))

시간복잡도

2중 반복문 사용: O(N^2)
데이터가 정렬되어 있는 상태에서는 매우 빠르게 동작한다 : O(N)

📌 버블정렬

인접한 수 2개 비교후 (오름차순 일때) 큰 수 먼저 정렬시키는 것

쉬운 코드

arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]


def bubble(arr):
    for i in range(len(arr) - 1, 0, -1):  # 큰 수(마지막)부터 정렬된다

        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr


print(bubble(arr))

2중 반복문만 사용하면 진행중 모두 정렬이 된 상태에서도 모든 반복문을 수행하게되어 비효율 적이다.

최적화

이때 swap변수를 사용하여 swap이 일어나지 않은 때를 모두 정렬된 상태로 인식하게 할 수 있다.

arr= [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

def bubble(arr):
    for i in range(len(arr)-1, 0, -1):
        swapFalse
        for j in range(i):
            if arr[j] > arr[j+1]:
                swapTrue
                arr[j], arr[j+1] = arr[j+1], arr[j]
        if not swap:  		# swap = False 면 0 ~ i-1 까지는 정렬되어 있음
            break
    return arr

print(bubble(arr))

시간복잡도

• 최선 : 자료가 정렬되어 있을 때
  비교횟수 : i번째 실행 (n-i)번 비교 n(n-1)/2

• 최악 : 자료가 역순 정렬되어 있을 때
  비교횟수 : i번째 실행 (n-i)번 비교 n(n-1)/2
  자리교환 횟수 : i번째 실행시 (n-i)번 교환 n(n-i)/2
  총 시간 : n(n-1)

총 시간복잡도 :O(N^2)

참고자료

내용
https://www.daleseo.com/sort-selection/ 님의 블로그
이미지
https://commons.wikimedia.org/wiki/File:Insertion-sort-example.gif
https://commons.wikimedia.org/wiki/File:Bubble-sort-example-300px.gif

📁추가! 재귀로만 구현해본 선택 정렬

arr = [7, 5, 9, 8, 3, 1, 6, 2, 4, 10]


def recur_minIdx(arr, deph):
    if deph == len(arr)-1:  # 0 이라면 0 / 9이면 return
        return deph

    minIdx = recur_minIdx(arr, deph+1)

    if arr[minIdx] > arr[deph]:
        minIdx = deph

    # print("deph : {} minIdx : {}".format(deph, minIdx))

    return minIdx

def swap(arr, deph, minIdx):
    arr[deph], arr[minIdx] = arr[minIdx], arr[deph]


def recur_select(arr, deph):
    # 종료조건
    if deph == len(arr)-1:
        return

    # 최소 위치 찾기
    minIdx = recur_minIdx(arr, deph)
    # 교환
    swap(arr, deph, minIdx)
    # 다음단계
    recur_select(arr, deph+1)


recur_select(arr, 0)
print(arr)