(CS50)-알고리즘 기초(선택정렬)

CS50 x edwith 강의를 들으며 정리한 공부 포스팅입니다.

그림출처

핵심 개념

• 선택 정렬
• 배열

선택 정렬

• 배열 안의 자료 중 가장 작은 수(혹은 가장 큰 수)를 찾아 첫 번째 위치(혹은 가장 마지막 위치)의 수와 교환해주는 방식.
• 교환 횟수를 최소화하는 반면 각 자료를 비교하는 횟수는 증가

실행

[선택정렬예시]

• 프로그램은 array라는 배열의 첫 번째 자리(5)에서 시작
• 가장 작은 원소를 찾기 위해 5를 (1, 6, 2, 4, 3)와 비교
• 1이 가장 작은 값이기 때문에 5의 위치와 교환
• 이제 1은 정렬되었으며 나머지 5, 6, 2, 4, 3은 여전히 정렬되지 않은 상태
• 다음은 두 번째 자리(5)인데, 정렬되지 않은 오른쪽(6, 2, 4, 3) 부분만 확인하면 됨
• 2가 정렬되지 않은 배열의 원소 중 가장 작은 원소이므로 5와 자리를 바꿔줌
• 이와 같은 방식으로 계속해서 비교와 교환을 반복
• 5번째 스텝에서 우리는 배열이 정렬되었다는 걸 알수 있지만,
• 컴퓨터는 알지 못하기에 6번째 스텝의 5와 6의 크기 비교까지 마친후에 알고리즘 종료

정리

• 버블 정렬과는 다르게 몇 번의 교환을 해주었는지 횟수를 셀 필요가 없음
• 선택 정렬로 정렬되는 배열은 n-1번의 교환이 필요(버블 정렬의 교환 횟수 보다 작음)
• But, 한 번의 교환이 일어나기 위해서는 정렬되지 않은 수의 모든 비교가 이루어져야 하기에 n^2번의 비교가 이루어 짐.
• 선택 정렬은 최선의 경우에도 최악의 경우에서 수행하는 횟수만큼 비교 및 교환을 해줘야함