[부스트코스]알고리즘 퀴즈 6

Q>

선택 정렬의 실행 시간의 하한도 버블 정렬처럼 더 단축시킬 수 있을까요?

 

A>

최악의 성능 : O (n2)

최상의 케이스 성능 : O (n2)

평균 케이스 성능 : O (n2)

최악의 공간 복잡성 : 총 O (n), 보조 O (1)

선택 정렬은 버블 정렬과 유사하지만 다른점은 1 패스당 스왑이 1개 뿐이라는 점이 있습니다.

그래서 어떤 점에서 보면 버블 정렬보다 선택 정렬이 더 최적화 되어있다고 할 수 있습니다.

 

https://www.boostcourse.org/cs112

모두를 위한 컴퓨터 과학 (CS50 2019)