시간 복잡도
정렬 과정
첫번째 원소 부터 인접한 원소끼리 비교하여 자리를 교환하면서 마지막 자리까지 이동하는 방법그림으로 이해하기
아래는 5개의 item이 있을때 오른 차순으로 정렬하는 방법을 나타낸다.PASS 1
item수 N=5이면
첫번째 loop의 갯수는 다음 원소와 비교하므로 마지막 지점에서는 비교할 대상이 없어져서 N-1번 까지 loop를 돈다.
for(i=0;i<N-1;i++){
if(data[i]<data[i+1]){
swap(data[i],data[i+1])
}
}
빨간색 item은 비교 후 swap된 item을 의미한다.
PASS 2
두번째 pass에서는 마지막 item이 완료되었기 때문에 비교할 필요가 없어진다. 따라서 이전에 만든 의사 코드의 수정이 필요하다. N-2 회 만큼의 loop가 돌아야 한다.
for(i=0;i<N-2;i++){
if(data[i]>data[i+1]){
swap(data[i],data[i+1])
}
}
PASS 3, PASS 4
전체 item N=5일때 PASS는 4까지 돌면된다. 왜냐하면 마지막 2개 남았을때까지만 하면 되기때문이다.
그럼 pass를 j라고 하면 j:0->N-1 로 만들 수 있다.
최종 의사 코드는 아래와 같습니다.
for(j=0;j<N-1;j++){
for(i=0;i<N-1-j;i++){
if(data[i]>data[i+1]){
swap(data[i],data[i+1])
}
}
}
C언어로 구현하기
C, pasted 1 second ago:
Output:
|
참고
https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC
댓글 없음:
댓글 쓰기