알고리즘 : 버블 정렬 BUBBLE SORT
버블정렬 개념
오름차순
인접 2개의 원소 비교
-> 큰값을 오른쪽 (스와핑: 원소값을 서로 바꾼다)
-처음 : 원소가 5개라면 4묶음이니 4번비교한다
-가장 오른쪽부터 먼저 정해짐
- 정해진 값을 두고 나머지로 다시 (비교회수 점점 줄어든다)
>속도가 느린 단점이 있다
스와핑시에 동시 교환이 아닌 임시변수가 필요하다
temp=a; // 템프가 a를 기억한다
a = b; // a는 b가 된다
b= temp; // b는 옛a가 된다
버블정렬 사용
버블 정렬의 비교 동작 루틴을 보면
********
*******
******
*****
****
***
**
*
이러한 형식으로 비교가 이루어진다 남는 수가 점점 줄어들기 떄문이다.
감이 오는가?
//간단한 PHP코드로 설명하며
// $는 변수 앞에 붙여 표현한다
배열을 이용하여 버블정렬을 할 수 있다.
$ar = array( 25, 2, 50 ,3 ,4 ,65, 90); // 무작위 숫자 데이터 입력 7개 ,배열로 생성
for ( $i =5 ; $i >=0; $i++) {
/* 이 외부 for 를 사이클이라 하겠다.
- 이 반복의 기능: 자리1에 맞는 수를 구하면 다음으로.
버블정렬에서 총사이클은 자리에 맞는값이 원소수 만큼 정해져야 하기 떄문에
원소갯수-1 이다 (마지막자리는 남은수 자동) */
//위에서 $i=5인 이유 ( (첨자 0부터 시작이니 또-1 ), 즉 원소갯수-2 이어야 한다.
for($k =0; $k <=$i ; $k++)
// 외부반복에서 온 제어변수 i를 사용하여 비교해야할 수를 파악된다
{ - 내부 반복의 기능: 2개로 묶인 수 비교하여 스와핑
if ($ar[$k] > $ar[$k+1] ) //다음 순 숫자보다 큰가?
{
$temp=$ar[$k]; // 템프가 a를 기억한다
$ar[$k] =$ar[$k+1]; // a는 b가 된다
$ar[$k+1]= $temp; // b는 옛a가 된다
//큰 경우 우측으로 를 수행
}
}
}
// 6번+5번+4번+3번+2번+1번
// 21번의 비교 끝에 7개의 버블정렬이 완료 되었을 것이다.
<?php
$ar = array( 25, 2, 50 ,3 ,4 ,65, 90); // 무작위 숫자 데이터 입력 7개 ,배열로 생성
for ( $i =5 ; $i >=0; $i--) {
for($k =0; $k <=$i ; $k++)
{
if ($ar[$k] > $ar[$k+1] ) //다음 순 숫자보다 큰가?
{
$temp=$ar[$k]; // 템프가 a를 기억한다
$ar[$k] =$ar[$k+1]; // a는 b가 된다
$ar[$k+1]= $temp; // b는 옛a가 된다
//큰 경우 우측으로 를 수행
}
}
}
for($n=0;$n<7;$n++) echo "$ar[$n] ";
?>*-도움이 되었다면 공감을 눌러주세요-*
< IT연구소 쿠키 랩 />