버블 정렬

배열의 알고리즘

사람한테 쉽다(배우기 쉽다)<->느림(성능이 안좋음)

 

버블정렬은 1회수행시 가장 큰 값이 맨뒤로 이동하는 로직

큰값들을 빠르게 찾아야할때 =>당장에 빨리 큰값을 찾아야 할때 활용 
쉽기 때문에 정렬할 데이터가 소수일때 유리함

ex)

arr=[3,2,5,1,4]

j     j<5     i      i<ar.length-1-j          temp        arr[i]>arr[i+1]
---------------------------------------------------------------------
0     T      0             T                       0                 T
                                                       3
              1              T                       0                F
              2              T                       0                T
                                                       5
              3              T                       0                T
                                                       5
              4              F

1    T      0             T                        0                F
              1             T                        0                T
                                                       3
              2             T                        0                F
              3             F  

arr=[2,3,1,4,5]

1번 정렬을 마친 상태 == 1회전 정렬이 끝났다.      

public class Test02 {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] arr=new int[5];
		arr[0]=3;
		arr[1]=2;
		arr[2]=5;
		arr[3]=4;
		arr[4]=1;
		for(int j=0;j<arr.length;j++) {//정렬을 몇번할지 결정하는 반복문
			//배열의 요소개수만큼  수행하겠다! == 5번 정렬
			boolean flag=true;//정렬 완료 되었을때를 확인
			for (int i = 0; i < arr.length-1-j; i++) {//배열을 1회 정렬할떄 사용되는 반복문
            	int temp=0;
				if(arr[i]>arr[i+1]) {
					temp=arr[i];
					//temp : 임시 저장변수,임시변수
					//변수 값들을 서로 교환하려면 반드시 tmp가 필요함!
					
					arr[i]=arr[i+1];
					arr[i+1]=temp;
					flag=false;
				}
			}//1번 정렬을 마친 상태 == 1회전 정렬이 끝났다.
			
			if(flag==true) {//정렬이 완료되었으면 종료
				break;
			}
			for (int i = 0; i < arr.length; i++) {//한번 돌때 정렬이 어떻게 되었는지 확인
				System.out.print(arr[i]);
			}
			System.out.println();
			
		}
	}

}

 

위 코드 피드백

[1]
"정렬이 다 되면 종료"를 한다>> while사용해야함
변수 공간 필요,대입연사자,조건식 확인

for문을 사용했다면 굳이 종료를 안해도됨(얼마 차이안남)

[2] 
temp 변수의 사용 범위(scope)
scope가 웹에서는 중요한 이슈!

 

피드백을 통한 내가 생각한 코드

public class Test01 {
	
	public static void main(String[] args) {
		int [] arr=new int[5];

		arr[0]=3;
		arr[1]=2;
		arr[2]=5;
		arr[3]=4;
		arr[4]=1;
		
		int cnt = 0;//반복으로 정렬이 어디까지 완료 되었는지 저장하는 변수
		while(true) {//언제 정렬이 완료될지 모르기에 while를 사용하였다
			boolean flag=true;
			for (int i = 0; i < arr.length-1-cnt; i++) {
				//arr길이 -1 줄인 이유는 현재 index에서 다음 index를 비교하기 때문에 사용했고
				//-cnt는 정렬이 완료된 것을 또 정렬 로직을 돌게 하는것이
                //비효율적이기 때문에 사용하였다
				if(arr[i]>arr[i+1]) {
					int temp=arr[i];
					arr[i]=arr[i+1];
					arr[i+1]=temp;
					flag=false;
				}
			}			
			if(flag==true) break;//정렬이 완료되면 true받게 되어 무한반복문 종료
			cnt++;//횟수 증가
			for (int i = 0; i < arr.length; i++) {//한번 돌때 정렬이 어떻게 되었는지 확인
				System.out.print(arr[i]);
			}
			System.out.println();
		}
    }
}