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

정렬 알고리즘(Sorting Algorithms)

: 데이터를 특정 순서로 정렬하는 알고리즘

 

선택 정렬(Selection Sort)

: 배열의 가장 최소값(or최대값)을 선택해서 배열의 앞부분으로 이동시키는 방식.

• 배열 전체에서 최소값(or최대값)을 찾음
• 그 값을 배열의 맨 앞에 위치한 값이랑 교환
• 맨 앞에 정렬된 애들을 제외하고, 위 두 과정 반복

 

▶ 선택 정렬 구현 코드

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 = 비교인덱스)
            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 반환

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]

 

사실 선택 정렬은 실제로 사용되는 경우가 굉장히 제한적이고,

퀵 정렬, 병합 정렬, 힙 정렬 등의 고급 알고리즘이 주로 사용된다고 한다.

 

단점

• 시간 복잡도가 O(n^2)임. 데이터가 클 경우 매우 비효율적이다.
• 같은 값이 있을 때 상대적인 순서가 보장되지 않아서 안정성이 떨어진다.

굳이 찾아본 장점

• 구현이 간단하고 단순하다. (어려운데..)
• 입력된 배열 내에서 정렬을 수행하기 때문에, 추가 메모리를 사용하지 않는다.

언제 사용할까

• 작은 데이터셋에서 간단하게 정렬이 필요할 경우.
• 추가로 메모리를 사용하면 안될 경우.

 

▶ 선택 정렬 코드 흐름도

 

흐름도 그려보다가 생각한건데

 

루프가 한번 실행될 때마다 남은 배열에서 최소값 or 최대값을 찾아내니까,

특정 순위까지만 순서를 세우고 싶을 때는 유리하게 쓸 수 있지 않을까

 

예를들어 100개 배열이 있는데 5위까지만 알고 싶을 때?

루프 5번만 실행하면 맨 앞부터 1,2,3,4,5위가 세워질테고 나머지는 알 바 아니니깐

 

다른 정렬까지 다 공부해보면 알게되겠지

---

삽입 정렬(Insertion Sort)

: 배열에서 순서대로 값을 지정하고, 배열의 정렬된 부분에서 올바른 위치에 그 값을 삽입하는 방식.

• 두 번째 요소부터 시작해서 앞의 요소들과 자신의 크기를 비교함
• 자신보다 큰값일 경우 요소들을 뒤로 한 칸씩 밀어주고, 작은 값을 만날 경우 그 바로 뒤에 삽입됨
• 이 과정을 배열 끝까지 반복

 

▶ 선택 정렬 구현 코드

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 + 1] = arr[j]           # key값이 arr[j]보다 작으면 arr[j]의 다음값에 arr[j]를 복제(오른쪽으로 복제)
            j -= 1                        # 왼쪽으로 한칸씩 진행하면서 계속 오른쪽으로 비교/복제 반복
        arr[j + 1] = key                  # while 루프를 탈출하면 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]

 

삽입 정렬도 마찬가지로 실제로 사용되는 경우는 제한적이라고 한다.

 

단점

• 최악의 경우 시간 복잡도가 O(n^2)임. 데이터가 클 경우 매우 비효율적이다.
• 특히 데이터가 역순일 경우(최악), 헛수고 과정이 엄청 포함되기 때문에 특히 느리다.

굳이 찾아본 장점

• 코드 구현이 쉽고 직관적이다. (어려워ㅜ)
• 최선의 경우 시간 복잡도가 O(n)임.
• 동일한 값의 상대적 순서를 유지하기 때문에 안정적이다.

언제 사용할까

• 작은 데이터셋에서 간단하게 정렬이 필요할 경우.
• 데이터가 거의 정렬되어 있는 경우

 

▶ 선택 정렬 코드 흐름도

삽입 정렬은 자기보다 큰 수는 뒤쪽으로 복제해서 덮어버리기 때문에 원래 값을 기억하려면 메모리에 key를 저장해놓는 과정이 필요하다.

 

자신이 들어가야 할 위치를 찾아 삽입되어 정렬하는 방식이니까

이미 정렬되어 있는 배열에 새로운 데이터를 한 개 추가하는 상황에 효율적일 것 같다.

거의 정렬되어 있는 상태일 때 사용한다는 게 이말이구나.

 

그래서 실시간으로 들어오는 사용자의 입력 데이터를 즉시 처리하여 데이터 리스트에 추가해야 하는 상황에 사용한다구 한다. 

 

 

---