#012 버블 정렬

# 문제)

아래와 같이 정렬되지 않은 배열이 있을때 버블 정렬을 사용하여 오름차순 정렬하여라.

<초기>

5

2

4

3

1

버블 정렬이란 인접한 두개의 원소끼리 비교하여 정렬해가는 방법을 말한다.

O(n^2) 성능을 가짐.

먼저, 정렬이 진행되는 순서를 보며 규칙성을 찾아보자.

<1회전>

2

5

4

3

1

2

4

5

3

1

2

4

3

5

1

2

4

3

1

5

<2회전>

2

4

3

1

5

2

3

4

1

5

2

3

1

4

5

<3회전>

2

3

1

4

5

2

1

3

4

5

<4회전>

1

2

3

4

5

1회전이 완료되면 맨 마지막 원소는 정렬이 완료 됬다는 것을 알 수 있다.

즉, 정렬이 진행 되는 과정을 보면 회전 수가 진행 될 때마다 비교하는 횟수가 그에 맞게 감소하고 있는 것을 알 수 있다.

package dataStructure.sort.bubble;

public class BubbleSort {

    private int[] array;

    private int size;

    private int maxSize;

   

    public BubbleSort(int maxSize) {

        // TODO Auto-generated constructor stub

        this.maxSize = maxSize;

        this.array = new int[this.maxSize];

        this.size = 0;

    }

   

    public void add(int value) {

        if(size >= maxSize) {

            System.out.println("max size.. so, can't add..");

            return;

        }

        array[size++] = value;

    }

   

    public void add(int...values) {

        if((this.size + values.length) >= this.maxSize) {

            System.out.println("max size.. so, can't add..");

            return;

        }

       

        for(int i=0; i<values.length; i++) {

            this.array[this.size++] = values[i];

        }

    }

   

    public int size() {

        return size;

    }

   

    public void remove(int index) {

        if(0 <= index && index<=maxSize-1) {

            array[index] = -1;

        }else {

            System.out.println("invalid index. ");

        }

    }

   

    public void sort() {

        for(int i=0; i<size; i++) {

            for(int j=0; j<size-i-1; j++) {

                if( array[j] > array[j+1] ) {

                    swap(j,j+1);

                }

            }

        }

    }

   

    private void swap(int currentIndex, int nextIndex) {

        int temp = array[currentIndex];

        array[currentIndex] = array[nextIndex];

        array[nextIndex] = temp;

    }

   

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        StringBuilder result = new StringBuilder();

        result.append("[");

        int i = 0;

        while(i < size) {

            result.append(array[i]);

            if(i != (size - 1) ) {

                result.append(",");

            }

            i++;

        }

        result.append("]");

        return result.toString();

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        BubbleSort bubble = new BubbleSort(10);

        bubble.add(5,2,4,3,1);

        System.out.println(bubble);

        bubble.sort();

        System.out.println(bubble);

    }

}

# 응용문제)

이미 정렬된 경우 계속 반복하여 정렬을 수행한다. 이를 개선할 수 있는 방법은?

정렬이 필요한 경우, swap이 발생됨을 알 수 있다.

따라서 한번도 swap이 발생하지 않았다는 것은 이미 정렬 되었음을 의미한다.

package dataStructure.sort.bubble;

public class BubbleSort {

    private int[] array;

    private int size;

    private int maxSize;

   

    public BubbleSort(int maxSize) {

        // TODO Auto-generated constructor stub

        this.maxSize = maxSize;

        this.array = new int[this.maxSize];

        this.size = 0;

    }

   

    public void add(int value) {

        if(size >= maxSize) {

            System.out.println("max size.. so, can't add..");

            return;

        }

        array[size++] = value;

    }

   

    public void add(int...values) {

        if((this.size + values.length) >= this.maxSize) {

            System.out.println("max size.. so, can't add..");

            return;

        }

       

        for(int i=0; i<values.length; i++) {

            this.array[this.size++] = values[i];

        }

    }

   

    public int size() {

        return size;

    }

   

    public void remove(int index) {

        if(0 <= index && index<=maxSize-1) {

            array[index] = -1;

        }else {

            System.out.println("invalid index. ");

        }

    }

   

    public void sort() {

        boolean isSorted = false;

        for(int i=0; i<size; i++) {

            System.out.printf("[%d번째] \n",(i+1));

            isSorted = true;

            for(int j=0; j<size-i-1; j++) {

                System.out.printf("\t[%d번째] ",(j+1));

                if( array[j] > array[j+1] ) {

                    swap(j,j+1);

                    isSorted = false;

                }

                System.out.println();

            }

            if(isSorted) {

                break;

            }

        }

    }

   

    private void swap(int currentIndex, int nextIndex) {

        int temp = array[currentIndex];

        array[currentIndex] = array[nextIndex];

        array[nextIndex] = temp;

        System.out.printf("swap ");

    }

   

    @Override

    public String toString() {

        // TODO Auto-generated method stub

        StringBuilder result = new StringBuilder();

        result.append("[");

        int i = 0;

        while(i < size) {

            result.append(array[i]);

            if(i != (size - 1) ) {

                result.append(",");

            }

            i++;

        }

        result.append("]");

        return result.toString();

    }

   

    public static void main(String[] args) {

        // TODO Auto-generated method stub

        BubbleSort bubble = new BubbleSort(10);

        //bubble.add(5,2,4,3,1);

        bubble.add(1,2,3,4,5);

        System.out.println(bubble);

        bubble.sort();

        System.out.println(bubble);

    }

}