Chapter 06-2. 정렬 알고리즘_버블 정렬

버블 정렬(bubble sort)

이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘

단순 교환 정렬(straight exchange sort)이라고도 함

 

버블 정렬을 이용해 요솟수가 n인 숫자 배열 오름차순 정렬

• 끝에 있는 두 요소 비교 후 더 작은 값 왼쪽으로 교환 → n-1번 비교, 교환하면 가장 작은 요소가 맨 처음으로 이동, 이런 일련의 과정(비교, 교환)을 패스(pass)라고 함
• 배열의 두번째 이후 요소를 비교, 교환하는 패스 수행(맨 앞을 가장 작은 수로 정렬해 놨기에 패스를 수행할 때마다 정렬할 요소가 하나씩 줄어듬) → n-2회 반복
• 모든 정렬이 끝나려면 패스가 n-1번 수행되야 함 → n-1개 요소의 정렬이 끝나면 마지막 요소는 이미 끝에 놓이기 때문

// 변수 i값을 0부터 n-2까지 1씩 증가시키며 패스를 n-1번 수행하는 프로그램
for(int i = 0; i < n - 1; i++) {
	// a[i], a[i+1], ... a[n-1]에 대해 끝에서부터 앞쪽으로 스캔하며 이웃하는 두 요소 비교, 교환
	// a[j]와 a[j-1]을 비교 -> 한 번의 패스에서는 j값이 i+1이 될 때까지 비교, 교환을 수행하면 됨
	// i가 0인 첫 패스에선 j값이 1이 될때까지 반복, i가 1이면 j가 2가 될때까지 반복함
}

 

버블 정렬(버전 1)

package ch06_2;

import java.util.Scanner;

// 버블 정렬(버전 1)
public class Ex01_bubbleSort {
    // a[idx1]과 a[idx2]의 값을 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 버블 정렬
    static void bubbleSort(int[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            for (int j = n - 1; j > i; j--) { // 패스
                // 뒷 숫자보다 앞 숫자가 크면 값 교환
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("버블 정렬(버전 1)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 버블 정렬

        System.out.println("오름차 순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}
/*
버블 정렬(버전 1)
요솟수: 5
x[0]: 6
x[1]: 4
x[2]: 3
x[3]: 1
x[4]: 8
오름차 순으로 정렬했습니다.
x[0] = 1
x[1] = 3
x[2] = 4
x[3] = 6
x[4] = 8
 */

 

단순 교환 정렬(각 패스를 앞 -> 뒤 순서로 수행)

package ch06_2;

import java.util.Scanner;

// 단순 교환 정렬(각 패스를 앞 -> 뒤 순서로 수행)
public class Ex02_bubbleSortR {
    // a[idx1]과 a[idx2]의 값을 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 단순 교환 정렬
    static void bubbleSort(int[] a, int n) {
        for (int i = n-1; i > 0; i--) {
            for (int j = 0; j < i; j++) { // 맨앞 -> 맨끝 순서로 스캔
                // 뒷 숫자보다 앞 숫자가 크면 값 교환
                if (a[j] > a[j + 1]) {
                    swap(a, j, j + 1);
                }
            }
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("단순 교환 정렬(버블 정렬)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 단순 교환 정렬

        System.out.println("오름차 순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}
/*
단순 교환 정렬(버블 정렬)
요솟수: 5
x[0]: 2
x[1]: 8
x[2]: 4
x[3]: 6
x[4]: 9
오름차 순으로 정렬했습니다.
x[0] = 2
x[1] = 4
x[2] = 6
x[3] = 8
x[4] = 9
 */

 

단순 교환 정렬(교환 과정을 자세히 출력)

package ch06_2;

import java.util.Scanner;

// 단순 교환 정렬(교환 과정을 자세히 출력)
public class Ex03_bubbleSortEx {
    // 배열 요소 a[idx1]과 a[idx2]를 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 단순 교환 정렬
    static void bubbleSort(int[] a, int n) {
        int cCnt = 0; // 비교 횟수
        int sCnt = 0; // 교환 횟수

        for (int i = 0; i < n - 1; i++) {
            System.out.printf("패스%d : \\n", i + 1);
            for (int j = n - 1; j > i; j--) {
                for (int k = 0; k < n - 1; k++) {
                    // 배열 가장 마지막 바로 앞까지 출력 - 앞, 뒤 비교해서 앞숫자 크다면 +, 작다면 - 출력
                    System.out.printf("%3d %c", a[k], (k != j - 1) ? ' ' : (a[j - 1] > a[j] ? '+' : '-'));
                }
                System.out.printf("%3d\\n", a[n - 1]); // 배열 가장 마지막 숫자 출력

                cCnt++; // 비교 횟수수 증가
                if (a[j - 1] > a[j]) {
                    // 앞 숫자가 뒷 숫자보다 크다면 교환
                    sCnt++; // 교환 횟수 증가
                    swap(a, j - 1, j);
                }
            }
            // swqp으로 바뀐 배열 출력
            for (int j = 0; j < n; j++) {
                System.out.printf("%3d ", a[j]);
            }
            System.out.println();
        }
        System.out.println("비교를 " + cCnt + "회 했습니다.");
        System.out.println("교환을 " + sCnt + "회 했습니다.");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("단순 교환 정렬(버블 정렬)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 단순 교환 정렬

        System.out.println("오름차순으로 정렬하였습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}

 

알고리즘 개선하기 1 - 해당 패스에서 교환 횟수가 0이면 정렬 종료

package ch06_2;

import java.util.Scanner;

// 버블 정렬(버전 2)
public class Ex04_bubbleSort2 {
    // a[idx1]과 a[idx2]의 값을 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 버블 정렬
    static void bubbleSort(int[] a, int n) {
        for (int i = 0; i < n - 1; i++) {
            int exchg = 0; // 패스를 교환하는 횟수를 저장
            for (int j = n - 1; j > i; j--) { // 패스
                // 뒷 숫자보다 앞 숫자가 크면 값 교환
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    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 nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 버블 정렬

        System.out.println("오름차 순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}

 

단순 교환 정렬(버전 2: 교환 과정을 자세히 출력)

package ch06_2;

import java.util.Scanner;

// 단순 교환 정렬(버전 2: 교환 과정을 자세히 출력)
public class Ex05_bubbleSortEx2 {
    // 배열의 요소 a[idx1]과 a[idx2]를 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 단순 교환 정렬
    static void bubbleSort(int[] a, int n) {
        int cCnt = 0; // 비교 횟수
        int sCnt = 0; // 교환 횟수

        for (int i = 0; i < n - 1; i++) {
            int exchg = 0; // 패스에 의한 교환 횟수
            System.out.printf("패스%d: \\n", i+1);

            // 맨 끝부터 맨 앞+1까지 비교하며 반복
            for (int j = n-1; j > i; j--) {
                for (int k = 0; k < n - 1; k++) {
                    // 비교할 뒷숫자와 앞숫자, 앞숫자가 크면 교환해야하니 + 작으면 비교만 한거니 -
                    System.out.printf("%3d %c", a[k], (k != j - 1) ? ' ' : (a[j - 1] > a[j] ? '+' : '-'));
                    }
                System.out.printf("%3d\\n", a[n-1]); // 가장 마지막 숫자 출력

                cCnt++;
                if (a[j - 1] > a[j]) {
                    swap(a, j - 1, j);
                    exchg++;
                    sCnt++;
                }
            }
            for (int k = 0; k < n; k++) {
                System.out.printf("%3d ", a[k]);
            }
            System.out.println();
            if(exchg == 0) break; // 교환이 이루어지지 않으므로 멈춤
        }
        System.out.println("비교를 " + cCnt + "회 했습니다.");
        System.out.println("교환를 " + sCnt + "회 했습니다.");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("단순 교환 정렬(버블 정렬)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 단순 교환 정렬

        System.out.println("오름차순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}
/*
단순 교환 정렬(버블 정렬)
요솟수: 4
x[0]: 2
x[1]: 7
x[2]: 5
x[3]: 9
패스1: 
  2    7    5 -  9
  2    7 +  5    9
  2 -  5    7    9
  2   5   7   9 
패스2: 
  2    5    7 -  9
  2    5 -  7    9
  2   5   7   9 
비교를 5회 했습니다.
교환를 1회 했습니다.
오름차순으로 정렬했습니다.
x[0] = 2
x[1] = 5
x[2] = 7
x[3] = 9
 */

 

알고리즘 개선하기 2 - 교환이 일어나지 않는 인덱스 이후부터 다시 비교, 교환하기

package ch06_2;

import java.util.Scanner;

// 버블 정렬(버전 3)
public class Ex06_bubbleSort3 {
    // a[idx1]과 a[idx2]의 값을 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 버블 정렬
    static void bubbleSort(int[] a, int n) {
        int k = 0; // a[k]보다 앞쪽은 정렬을 마친 상태
        while (k < n - 1) {
            int last = n -1; // 마지막으로 요소를 교환한 위치
            for (int i = n-1; i > k; i--) {
                if (a[i - 1] > a[i]) {
                    swap(a, i-1, i);
                    last = i;
                }
            }
            k = last;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("버블 정렬(버전 3)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 버블 정렬

        System.out.println("오름차 순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}

 

단순 교환 정렬 정렬(버전 3: 교환 과정을 자세히 출력)

package ch06_2;

import java.util.Scanner;

// 단순 교환 정렬 정렬(버전 3: 교환 과정을 자세히 출력)
public class Ex07_bubbleSortEx3 {
    // a[idx1]과 a[idx2]의 값을 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 단순 교환 정렬
    static void bubbleSort(int[] a, int n) {
        int cCnt = 0; // 비교 횟수
        int sCnt = 0; // 교환 횟수

        int pass = 0;
        int k = 0; // a[k]보다 앞쪽은 정렬을 마친 상태
        while (k < n - 1) {
            System.out.printf("패스%d: \\n", ++pass);
            int last = n -1; // 마지막으로 요소를 교환한 위치
            for (int i = n-1; i > k; i--) {
                for (int j = 0; j < n - 1; j++) {
                    System.out.printf("%3d %c", a[j], (j != i - 1) ? ' ' : (a[i - 1] > a[i] ? '+' : '-'));
                }
                System.out.printf("%3d\\n", a[n-1]);
                cCnt++;
                if (a[i - 1] > a[i]) {
                    swap(a, i-1, i);
                    last = i;
                    sCnt++;
                }
            }
            k = last;
        }
        System.out.println("비교를 " + cCnt + "회 했습니다.");
        System.out.println("교환을 " + sCnt + "회 했습니다.");
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("버블 정렬(버전 3)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        bubbleSort(x, nx); // 배열 x를 버블 정렬

        System.out.println("오름차 순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}
/*
버블 정렬(버전 3)
요솟수: 5
x[0]: 2
x[1]: 3
x[2]: 9
x[3]: 6
x[4]: 7
패스1: 
  2    3    9    6 -  7
  2    3    9 +  6    7
  2    3 -  6    9    7
  2 -  3    6    9    7
패스2: 
  2    3    6    9 +  7
비교를 5회 했습니다.
교환을 2회 했습니다.
오름차 순으로 정렬했습니다.
x[0] = 2
x[1] = 3
x[2] = 6
x[3] = 7
x[4] = 9
 */

 

양방향 버블 정렬(셰이커 정렬)

package ch06_2;

import java.util.Scanner;

// 양방향 버블 정렬(셰이커 정렬)
public class Ex08_shakerSort {
    // a[idx1]과 a[idx2]의 값을 교환
    static void swap(int[] a, int idx1, int idx2) {
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    // 양방향 버블 정렬(셰이커 정렬)
    static void shakerSort(int[] a, int n) {
        int left = 0; // a[left]보다 앞쪽은 정렬을 마친 상태
        int right = n - 1; // a[right]보다 뒤쪽은 정렬을 마친 상태
        int last = right; // 마지막으로 요소를 교환한 위치
        while (left < right) {
            // 뒤에서부터 작은 요소 맨 앞으로 옮기기
            for (int i = right; i > left; i--) {
                if (a[i - 1] > a[i]) {
                    swap(a, i - 1, i);
                    last = i;
                }
            }
            left = last;

            // 앞에서부터 큰 요소 맨 뒤로 옮기기
            for (int i = left; i < right; i++) {
                if (a[i] > a[i + 1]) {
                    swap(a, i, i + 1);
                    last = i;
                }
            }
            right = last;
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        System.out.println("양방향 버블 정렬(셰이커 정렬)");
        System.out.print("요솟수: ");
        int nx = scanner.nextInt();
        int[] x = new int[nx];

        for (int i = 0; i < nx; i++) {
            System.out.print("x[" + i + "]: ");
            x[i] = scanner.nextInt();
        }

        shakerSort(x, nx); // 배열 x를 양방향 버블 정렬

        System.out.println("오름차 순으로 정렬했습니다.");
        for (int i = 0; i < nx; i++) {
            System.out.println("x[" + i + "] = " + x[i]);
        }
    }
}
/*
양방향 버블 정렬(셰이커 정렬)
요솟수: 5
x[0]: 2
x[1]: 9
x[2]: 7
x[3]: 3
x[4]: 5
오름차 순으로 정렬했습니다.
x[0] = 2
x[1] = 3
x[2] = 5
x[3] = 7
x[4] = 9
 */