선택 정렬 자세히 알아보기

1. 반복문 설정

두 개의 중첩된 반복문을 사용합니다. 외부 반복문은 배열을 통과하는 횟수를 결정하고, 내부 반복문은 최소값을 찾기 위해 배열의 요소를 비교합니다.

반복문 설정

for i in range(n):
  for j in range(i + 1, n):

2. 최소값 찾기 및 교환

내부 반복문에서, 최소값을 찾아 현재 위치의 값과 교환합니다.

최소값 찾기 및 교환

if arr[j] < arr[min_index]:
  min_index = j # 최소값의 인덱스 저장

arr[i], arr[min_index] = arr[min_index], arr[i] # 최소값과 현재 위치의 값 교환

선택 정렬 시간 복잡도

1. 최악, 최선, 평균 시간 복잡도 (Worst, Best, and Average-Case Time Complexity): 모두 O(n^2)

   • 선택 정렬은 배열의 각 위치에 대해 나머지 전체 배열을 탐색하여 가장 작은(또는 가장 큰) 요소를 찾습니다. 이 과정은 배열의 크기가 n일 때, 첫 번째 요소에 대해 n-1번, 두 번째 요소에 대해 n-2번 등 총 ((n-1) + (n-2) + ... + 1)번, 즉 n(n-1)/2 번의 비교를 필요로 합니다.

   n(n-1)/2를 빅오 표기법으로 표기하면, 시간복잡도는 O(n^2)가 됩니다.

   • 선택 정렬의 시간 복잡도는 입력 데이터의 정렬 상태에 관계없이 항상 일정합니다. 즉, 이미 정렬된 배열이든, 역순으로 정렬된 배열이든, 무작위로 배치된 배열이든 시간 복잡도는 변하지 않습니다.

다음 내용이 궁금하다면?

코드프렌즈 PLUS 멤버십 가입 or 강의를 등록해 주세요!

강의 등록하기로그인하기