13. Array 정렬 (버블,삽입,선택 정렬)

◾ 버블정렬

인접한 두 값 끼리 비교하면서 정렬되는 방식이다. 

0과 1 / 1과 2 / 2와 3 / 3과 4 위치가 비교된다.

다음 차수는 2와 3 까지 비교한다. (비교 회차가 1씩 줄어들음)

int []num = new int[] {10, 15, 5, 8, 13};
int temp;

System.out.println("source data : ");
for(int i=0; i<num.length;i++) {
    System.out.print(num[i] + "  ");

}System.out.println();

//Bubble sort
// 0;1 1;2 2;3 3;4
// 0;1 1;2 2;3
// 0;1 1;2
// 0;1

    for(int i=1;i<num.length;i++) {		// 뒤로 정렬이 되니까 뒷부분이 i가 되고 앞부분이 j가 됨.
        for(int j=0;j<num.length-i;j++) {
        if(num[j]>num[j+1]) {	//여기서 j+1 하면 ++할 필요x
            temp=num[j];
            num[j]=num[j+1];
            num[j+1]=temp;

        }
    }


        System.out.println(i+ "회전 : " + Arrays.toString(num));

    }

 

◾ 개선된 버블 정렬

do ~ while 문에서 flag 로 정렬 완료시 정렬을 멈출 수 있다.

for 문으로 하는 방법도 있으며, for 문으로 개선된 버블 정렬을 하는 것이 좀 더 빠르다.

int []num = new int[] {20, 40, 12, 55, 45, 60, 66, 80, 85, 90};
int temp, pass;
boolean flag;

////////////////////////////////////////////

pass=1;

do {
    flag = false;

    // 버블소트에서는 for 이중문이었는데 여기서는 do 안에 for...
    for(int i=0; i<num.length-pass; i++) {
        if(num[i]>num[i+1]) {
            temp=num[i];
            num[i]=num[i+1];
            num[i+1]=temp;
            flag = true;
        }
    }

//			System.out.println(pass + "회전 : " + Arrays.toString(num));

    pass++;

}while(flag);

 

◾ 삽입정렬

오름차순 정렬하는 상황이라면, 삽입 정렬은 해당 값을 쇽쇽 빼서 뒤에 위치랑 비교하면서 뒤에 값보다 크다면 정렬을 멈추고 다음 값을 정렬하는 방법이다.

25, 17, 10, 5, 12, 9, 17, 16, 20, 13 이렇게 값이 있다면

💥 2번째 원소인 17을 가지고 그 앞에 25와 비교한다. => 17, 25, [10, 5, 12, 9, 17, 16, 20, 13]

💥 다음으로 3번째 원소인 10을 가지고 앞에 17, 25와 비교한다. => 10, 17, 25 [5, 12, 9, 17, 16, 20, 13]

💥 다음으로 4번째 원소인 5를 가지고 앞에 10, 17, 25와 비교한다. => 5, 10, 17, 25 [12, 9, 17, 16, 20, 13]

 

이런 정렬이 삽입 정렬이다~ 

int []a = new int[] {25, 17, 10, 5, 12, 9, 17, 16, 20, 13};
//10개. a[9] 까지 있음

//		1회전 : 1:0
//		2회전 : 2:1 / 1:0
//		3회전 : 3:2 / 2:1 / 1:0
//		4회전 : 4:3 / 3:2 / 2:1 / 1:0

int key, i, j;

for(i=1; i<a.length; i++) {
    // 처음 정렬에서는 2번째 값인 17이 저장됨-> break 로 다시 오면 다음은 3번째값
    key = a[i]; 
    for(j=i-1; j>=0; j--) {
        //앞 전 값인 a[0]이 더 크다면, 앞 전 값에 key가 들어가야한다.
        if(a[j] > key) { 
            a[j+1] = a[j];
        } else {
            break; //오름차순 정렬할 것이 없다면 break로 다음 회전 이어가기
        }
    }

    a[j+1] = key;

}

 

◾ 선택정렬

선택 정렬은 첫번째 요소를 고정시키고 그 뒤에 요소들과 비교를 해서 콕콕 선택해서 해당 요소들의 위치를 바꾸는 정렬이다.

int []num = new int[] {10, 15, 5, 8, 13};
int temp;

//sort // 데이터가 5개라 4회전까지 가는거야
// 1회전 => 0:1 비교 / 0:2 비교 / 0:3 비교 / 0:4 비교
// 2회전 => 1:2 비교 / 1:3 비교 / 1:4 비교
// 3회전 => 2:3 비교 / 2:4 비교
// 4회전 => 3:4

for(int i=0; i<num.length-1; i++) { //i=0,1,2,3 네번 반복
    for(int j=i+1; j<num.length; j++) {
        if(num[i]>num[j]) {
            temp=num[i];
            num[i]=num[j];
            num[j]=temp;
        }
    }

    // Arrays.toString(배열)); < = 배열의 값을 문자열로 결합하여 변환
    System.out.println((i+1) + "회전 : " + Arrays.toString(num));
}