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

Q>

선택정렬을 좀 더 효율적으로 어떻게 바꿀 수 있을까요?

 

A>

선택정렬의 개선 사항은 최대값과 최소값을 동시에 선택한 다음 배열을 두 끝에서 정렬하는 방법입니다.

 

begin
   for i := 0, and j := n-1, increase i by 1, and decrease j by 1, until i>=j, do
      min := minimum element from index i to j
      max := maximum element from index i to j
      i_min := index of min
      i_max := index of max
      exchange the arr[i] and arr[i_min]
      if arr[i_min] is same as max, then
         swap arr[j] and arr[i_min]
      else
         swap arr[j] and arr[i_max]
      end if
   done
end

 

https://www.boostcourse.org/cs112/

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