티스토리 뷰

C, C++/정올

1157 : 버블정렬

j0n9m1n1 2016. 6. 6. 20:24
반응형

1157 : 버블정렬

제한시간: 1Sec    메모리제한: 32mb
해결횟수: 669회    시도횟수: 1167회   



거품 정렬(Bubble sort)이란? 두 인접한 원소를 검사하여 자리를 바꾸는 과정을 반복하며 정렬하는 방법이다.

다음과 같은 과정으로 정렬을 한다.
1. 첫번째 값과 두번째 값을 비교하여 첫번째 값이 크면 자리를 바꾼다.
2. 두번째 값과 세번째 값을 비교하여 두번째 값이 크면 자리를 바꾼다.
3. 위와 같이 반복하여 N-1번째 값과 N번째 값을 비교하여 N-1번째 값이 크면 자리를 바꾼다. 이 단계가 끝나면 N번째에 가장 큰 수가 자리하게 된다. (한단계완료)
4. N번째를 제외하고 1~3을 반복하면 N-1번째에 두 번째로 큰수가 자리한다. (2단계 완료) 
5. 위와같은 작업을 N-1번 반복하면 모든 데이터가 순서대로 정렬된다.

예를 들어 수열 {62, 23, 32, 15} 가 있을 때 아래와 같은 과정으로 정렬이 된다.

e3050b66a1b29a01767400d7560a4131_1449727

(분홍식 칸은 정렬이 끝나 더이상 확인 안해도 되는 값이다.)

정렬되지 않은 수열이 주어지면 버블정렬의 각 단계가 끝날때마다 결과를 출력하는 프로그램을 작성하시오

 

 

첫줄에 수열의 길이 N(4≤N≤100)이 주어진다.
두 번째 줄에 N개의 0이상 100이하의 정수가 주어진다.



처음 상태를 제외하고 정렬과정의 각 단계별 결과를 "출력예"와 같이 출력한다.


 [Copy]
4
62 23 32 15
 [Copy]
23 32 15 62
23 15 32 62
15 23 32 62



#include <stdio.h>


int main() {

 

int num[100] = {0, }, i, j, k, N, temp;

scanf("%d", &N);


  for (i = 0; i < N; i++) {

 

    scanf("%d", &num[i]); 

}


for (i = 0; i < N - 1; i++) {


for (j = 0; j < N - 1; j++) {

    

    if (num[j] > num[j + 1]){

   

temp = num[j + 1];

    num[j + 1] = num[j];

num[j] = temp;

    }

else{

}

}

for(k = 0; k < N; k++){

printf("%d ", num[k]);

}

puts("");

  }

}



'C, C++ > 정올' 카테고리의 다른 글

1039 : 도미노  (0) 2016.06.06
1146 : 선택정렬  (0) 2016.06.06
1071 : 약수와 배수  (0) 2016.06.06
1307 : 문자사각형1  (0) 2016.06.06
1303: 숫자사각형1  (0) 2016.06.06
댓글

티스토리 방명록

최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday