[알고리즘] 선택정렬, 삽입정렬코드

선택정렬

def selection_sort(arr):                # 함수정의, 배열받기
    n = len(arr)                        # n = 배열길이
    for i in range(n):                  # i반복 : 0부터 ~ n-1까지 (i = 기준인덱스)
        min_idx = i                     # 최소인덱스 = i로 지정해놓고 비교시작!
        for j in range(i + 1, n):       # j반복 : i+1부터 ~ n-1까지 (j = 비교인덱스)  # 엥? 근데 i=7일때는??
            if arr[j] < arr[min_idx]:   # 비교인덱스의 값 < 최소인덱스의 값 일 경우,
                min_idx = j             # 최소인덱스 = 비교인덱스 j로 바꿔줌.
                
        # 내부for끝 : (앞에서부터 i개를 제외한)배열에서 최소값 위치 발견!
        
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
        # i인덱스값 <-> 최소인덱스값 swap해줌.
        # 결과 : 배열의 (앞에서 i개 제외하고) 맨 앞으로 최소값을 보내줌!

    return arr                          # 정렬된 arr 반환

# Example usage
if __name__ == "__main__":              # 이 파일을 직접 실행할때만 아래가 실행되게 하는 코드라구한다.
    arr = [44, 490, 83, 1, 0, 34, 65, 97] # 예시 배열
    sorted_arr = selection_sort(arr)    # sorted_arr 변수에 return값 저장
    print(sorted_arr)                   # sorted_arr 출력 [0, 1, 34, 44, 65, 83, 97, 490]

 

 

 

삽입정렬

def insertion_sort(arr):                  # 함수정의, 배열받기
    for i in range(1, len(arr)):          # i반복 : 1부터 ~ n-1까지 (i = 기준인덱스)
        key = arr[i]                      # 일단 key 변수에 기준값 저장해놓기

        j = i - 1                         # j: 기준값의 바로 전 인덱스부터 시작해서
        while j >= 0 and key < arr[j]:    # j가 -1이 될때까지 or key값이 arr[j]보다 클때까지 진행
            arr[j + 1] = arr[j]           # key값이 arr[j]보다 작으면 arr[j]의 다음값에 arr[j]를 복제
            j -= 1                        # j가 1씩 작아지면서 계속 비교/복제 반복
        arr[j + 1] = key                  # arr[j+1]에 저장했던 key 넣어줌
        
        # while문 끝 : key 변수가 자기 자리에 삽입됨!(자기부터 앞쪽 배열만 고려함)
    
    return arr                             # 외부 for문까지 다 완료한 배열리턴

if __name__ == "__main__":                 # 이 파일을 직접 실행할때만 아래가 실행되게 하는 코드라구한다.
    arr = [44, 490, 83, 1, 0, 34, 65, 97]  # 예시 배열
    sorted_arr = insertion_sort(arr)       # sorted_arr 변수에 return값 저장
    print(sorted_arr)                      # sorted_arr 출력 [0, 1, 34, 44, 65, 83, 97, 490]