버블정렬 여러가지 방법 구현

1. 정렬이란?

정렬은 이름, 학번, 키 등 핵심 항목의 대소관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말함.

정렬 알고리즘을 이용해 데이터를 정렬하면 검색을 더 쉽게 할수 있음.

키 값이 작은데이터를 앞으로 놓으면 오름차순(ascending order) 정렬

키 값이 큰 데이터를 앞으로 놓으면 내림차순(descending order) 정렬

내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있는 경우에 사용하는 알고리즘

외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없는 경우에 사용하는 알고리즘

졍렬 알고리즘의 핵심 요소 : 교환, 선택, 삽입

2. 버블정렬

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복한다.

요소의 개수가 n개인 배열에서 n-1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음으로 이동함.

이런 일련의 과정(비교, 교환 작업)을 패스(pass)라고 함.

모든 정렬이 끝나면 n-1회의 패스가 수행되어야 함.

1. 버블정렬 방법 1

package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
 
    }
    
    // 6 4 3 7 1 9 8
    static void bubbleSort(int[] array, int arrayLength){
        for(int i=0; i< arrayLength-1; i++){ 
            System.out.println("패스" + i);
            for(int j=arrayLength-1; j>i; j--){    
                if(array[j-1] > array[j]){ // 앞의 요소가 뒤의 요소보다 크다면
                    swap(array, j-1, j);
                }else{ // 앞의 요소가 뒤의 요소보다 작다면
                    for(int k=0; k<array.length; k++){
                        if(j-1 == k){
                            System.out.print(array[k]+"-");
                        }else{
                            System.out.print(array[k]);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("패스"+i+" 정렬결과 ");
            for(int l=0; l<array.length; l++){
                System.out.print(array[l]);
            }
            System.out.println();
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 1");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}

결과1

버블 정렬 방법 1
배열의 길이: 7
array[0] :6
array[1] :4
array[2] :3
array[3] :7
array[4] :1
array[5] :9
array[6] :8
패스0
643719+8
64371-89
6437+189
643+1789
64+13789
6+143789
패스0 정렬결과 
1643789
패스1
164378-9
16437-89
1643-789
164+3789
16+34789
패스1 정렬결과 
1364789
패스2
136478-9
13647-89
1364-789
136+4789
패스2 정렬결과 
1346789
패스3
134678-9
13467-89
1346-789
패스3 정렬결과 
1346789
패스4
134678-9
13467-89
패스4 정렬결과 
1346789
패스5
134678-9
패스5 정렬결과 
1346789
오름차순 정렬완료
1346789

2. 정렬 된 상태가 있는 요소가 있을때 교환횟수 기록하는 버블 정렬 방법 2

package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort2 {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
        if(idx1 == 0){
            for(int i=0; i<array.length; i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
    
    // 정렬된 상태에서 교환횟수 기록
    static void bubbleSort2(int[] array, int arrayLength){
        for(int i=0; i<arrayLength-1; i++){
            int exchg = 0;                    // 패스의 교환 횟수를 기록합니다.
            System.out.println("패스" + i);
            for(int j=arrayLength-1; j>i; j--){
                if(array[j-1] > array[j]){
                    swap(array, j-1, j);
                    exchg++;
                }else{ // 앞의 요소가 뒤의 요소보다 작다면
                    for(int k=0; k<array.length; k++){
                        if(j-1 == k){
                            System.out.print(array[k]+"-");
                        }else{
                            System.out.print(array[k]);
                        }
                    }
                    System.out.println();
                }
            }
            System.out.println("교환횟수: "+exchg);
            if(exchg == 0) break;        // 교환이 이루어지지 않으면 종료한다.
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 2");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort2(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}

결과2

버블 정렬 방법 2
배열의 길이: 7
array[0] :1
array[1] :3
array[2] :9
array[3] :4
array[4] :7
array[5] :8
array[6] :6
패스0
139478+6
13947+68
1394-678
139+4678
13-49678
1-349678
교환횟수: 3
패스1
134967-8
13496-78
1349+678
134-6978
13-46978
교환횟수: 1
패스2
134697-8
13469+78
1346-798
134-6798
교환횟수: 1
패스3
134679+8
13467-89
1346-789
교환횟수: 1
패스4
134678-9
13467-89
교환횟수: 0
오름차순 정렬완료
1346789

3. 정렬된 요소를 제외하고 정렬해야 하는 위치를 last로 저장하는 버블정렬 방법 3

package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort3 {
    
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
        if(idx1 == 0){
            for(int i=0; i<array.length; i++){
                System.out.print(array[i]);
            }
            System.out.println();
        }
    }
    
    // 앞에 3개의 요소가 정렬된 1 3 9 4 7 8 6 인 배열이 있다고 하면
    // 3개의 요소를 제외한 4개의 요소에 대해 비교 교환을 수행해야 한다.
    // 교환을 수행할 때마다 오른족 요소의 인덱스 값을 last에 저장함.
    static void bubbleSort3(int[] array, int arrayLength){
        int k=0;
        while(k<arrayLength-1){ // 0<6 , 3<6, 4<6
            int last = arrayLength-1; // last = 6
            for(int j= arrayLength-1; j>k; j--){ // j=6, 6>0 // j=6, 6>3
                if(array[j-1] > array[j]){ // array[5] > array[6]
                    swap(array, j-1, j);
                    last = j; // last = 3 // last = 4 // last = 5 // last = 6
                }
            }
            k = last; // k=3 // k= 4 // k=5 // k=6
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 3");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort3(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}

결과3

버블 정렬 방법 3
배열의 길이: 7
array[0] :1
array[1] :3
array[2] :4
array[3] :9
array[4] :6
array[5] :7
array[6] :8
1349+678
13469+78
134679+8
오름차순 정렬완료
1346789

4.  홀수번째 패스는 가장 작은 요소를 맨 앞으로 옮기고 

짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식 사용한 버블정렬

package myTest3;
 
import java.util.Scanner;
 
public class BubbleSort4 {
    
    static void swap1(int[] array, int idx1, int idx2){ // j, j+1
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx2];
        array[idx2] = array[idx1];
        array[idx1] = t;        
    }
 
    // a[idx1]와 a[idx2]의 갑을 바꾼다.
    static void swap2(int[] array, int idx1, int idx2){
        for(int i=0; i<array.length; i++){
            if(idx1 == i){
                System.out.print(array[i]+"+");
            }else{
                System.out.print(array[i]);
            }
        }
        System.out.println();        
        int t = array[idx1];
        array[idx1] = array[idx2];
        array[idx2] = t;
    }
    // 8 9 1 3 4 5 6
    // 1 3 4 8 7 9 2
    // 9 1 3 4 6 7 8 배열이 있다면
    // 두번째 요소부터 정렬되어있지만 bubbleSort3 메소드 사용시 빠른시간안에 정렬작업을 할수 없음.
    // 맨 앞에 있는 요소의 값(9)는 1회의 패스를 거쳐도 한칸씩만 뒤로 옮겨지기 때문
    // 홀수 번째 패스는 가장 작은 요소를 맨 앞으로 옮기고 짝수번째 패스는 가장 큰 요소를 맨 뒤로 옮기는 방식 사용
    // 칵테일 정렬, 쉐이커 정렬
    static void bubbleSort4(int[] array, int arrayLength){
        int k=0;
        int pathCount = 0;
        while(k<arrayLength-1){ // 0<6 , 3<6, 4<6
            int last = arrayLength-1; // last = 6W
            if(k%2 == 0){ // 짝수
                pathCount++;
                System.out.println("짝수패스" + pathCount);
                for(int j= 0; j<arrayLength-1; j++){ // 5 6
                    if(array[j] > array[j+1]){ // array[0] > array[1]
                        swap1(array, j, j+1);
                        last = 1;
                    }
                }
            }else{    // 홀수
                pathCount++;
                System.out.println("홀수패스" + pathCount);
                for(int j= arrayLength-1; j>=k; j--){ // j=6, 6>1; j--;
                    if(array[j-1] > array[j]){ // array[5] > array[6]
                        swap2(array, j-1, j);
                        last = 0; 
                    }
                }
            }            
            k = last; // k=3 // k= 4 // k=5 // k=6
        }
    }
    
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        System.out.println("버블 정렬 방법 4");
        System.out.print("배열의 길이: ");
        int arrayLength = scanner.nextInt();
        int[] array = new int[arrayLength];
        for(int i=0; i<arrayLength; i++){
            System.out.print("array[" + i + "] :");
            array[i] = scanner.nextInt();
        }
        
        bubbleSort4(array, arrayLength);        // 배열 x를 버블 정렬 한다.
        System.out.println("오름차순 정렬완료");
        for(int i=0; i<arrayLength; i++){
            System.out.print(array[i]);
        }
        System.out.println();
    }
}

결과4

버블 정렬 방법 4
배열의 길이: 7
array[0] :8
array[1] :9
array[2] :1
array[3] :3
array[4] :4
array[5] :5
array[6] :6
짝수패스1
89+13456
819+3456
8139+456
81349+56
813459+6
홀수패스2
8+134569
짝수패스3
18+34569
138+4569
1348+569
13458+69
홀수패스4
오름차순 정렬완료
1345689