|
:: 게시판
:: 이전 게시판
|
이전 질문 게시판은 새 글 쓰기를 막았습니다. [질문 게시판]을 이용바랍니다.
통합규정 1.3 이용안내 인용"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
10/04/20 05:28
선택 정렬은 비교횟수는 (n-1)+(n-2)+...+1 = n(n-1)/2회로 어떤 데이터가 들어와도 일정해요.(오름차순 정렬이라 할 때 정렬되지 않은 데이터들을 모두비교해서 최소 값을 제일 앞의 값과 교환하기 때문이죠.)
그래서 최소한, 최대한의 비교횟수를 가지도록 배열하라고 하면... 어떤 데이터가 들어와도 일정하니 아무런 배열을 적고 n(n-1)/2=7*6/2=21회라고 적으면 될 것 같네요... 만약 최소한의 교환횟수를 가지라는 문제였다면 귤, 딸기, 바나나, 사과, 오렌지, 자두, 참외 순으로 배열해야 한다면 귤, 딸기, 바나나, 사과, 오렌지, 자두, 참외로 하는것이 최소한의 교환횟수를 가지며 0번의 교환을 합니다. 최대한의 교환횟수를 가지도록 배열해야한다면 딸기, 바나나, 사과, 오렌지, 자두, 참외, 귤 일때 이고 이때에는 총 6번의 교환을 합니다. 0회 : 딸기, 바나나, 사과, 오렌지, 자두, 참외, 귤 1회 : 귤, 바나나, 사과, 오렌지, 자두, 참외, 딸기 2회 : 귤, 딸기, 사과, 오렌지, 자두, 참외, 바나나 3회 : 귤, 딸기, 바나나, 오렌지, 자두, 참외, 사과 4회 : 귤, 딸기, 바나나, 사과, 자두, 참외, 오렌지 5회 : 귤, 딸기, 바나나, 사과, 오렌지, 참외, 자두 6회 : 귤, 딸기, 바나나, 사과, 오렌지, 자두, 참외
10/04/20 07:52
귤, 딸기, 바나나, 사과, 오렌지, 자두, 참외 일때 최소 비교가 되겠죠. 이미 정렬이 되어있으니.
최대비교는 이게 역순일때구요.
|
||||||||||