선택 정렬

최유연·2021년 9월 21일
0

알고리즘이론

목록 보기
6/7

☝ 선택 정렬이란 차례로 가장 작은 값을 가장 앞으로 보내는 행위를 반복하여 정렬하는 방법이다.

🎫 개념

우선 정렬해야 하는 배열의 가장 작은 값을 첫번째 값으로 가정하고, 정렬을 반복하다보면 마지막으로 남은 값은 자동으로 제자리를 찾아가게 되므로 배열의 길이가 N일 경우, 가장 작은 값을 맨 앞으로 보내는 행위를 N-1번 반복한다. 이때 이중for문을 사용하여 정렬이 된 나머지 파트 중 가장 작은 요소를 찾아내는 행위를 반복한다.

❓ 예시

예를 들어 [35, 47, 84, 15, 17, 22, 29] 이라는 배열 arr이 있다고 하자.

✔ step1
가장 작은 값은 15이다.
[15, 35, 47, 84, 17, 22, 29]

✔ step2
15를 제외한 나머지 값 중 가장 작은 값은 17이다.
[15, 17, 35, 47, 84, 22, 29]

✔ 일련의 과정을 반복하면
[15, 17, 22, 29, 35, 47, 84]

💻 선택 정렬 코드 구현 (python)

def select_sort(arr, N):
    lowest = 0
    for i in range(N-1): #가장 작은 요소를 맨앞으로 보내는 행위는 N-1번
        for j in range(i+1,len(arr), 1): #
            if arr[j] < arr[lowest]:
                lowest = j
        arr[i], arr[lowest] = arr[lowest], arr[i]

    return arr


if __name__ == '__main__':
    N = int(input())
    arr = []
    for _ in range(N):
        arr.append(int(input()))

    arr = select_sort(arr, N)
    for i in arr:
        print(i)

⏰ 시간 복잡도 및 Big O 표기

2중 for문이 N에 달려있으므로 N(N+1)/2를 Big O 표기법으로 표현하면 O(N^2)이다.

profile
프론트엔드 도메인 지식을 지닌 백엔드 개발자로 성장하기 위한 기록

0개의 댓글