1. 버블 정렬

정렬 알고리즘은 나무위키가 참 잘 정리했다는 소문을 듣고 공부하러 감

(출처 : https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#fn-10)

일단 동영상부터

버블정렬의 원리는 아주 간단하고 직관적이다.

이웃해있는 값끼리 비교해서 더 작은 값을 앞으로 보내주는 것을 계속 반복해주는 것이다.

바쁜 현대인들을 위해 위 영상에서 일어나는 일을 그림으로 정리해봤다. (힘들어서 첫번째 루프 도는 것만 그림)

이런 짓을 몇 번 더 하고 나면 정렬이 완성된다. 

이중for문을 통해 구현하기 때문에 시간 복잡도는 O(N^2)

정리하자면 제일 직관적으로 이해하기 쉽고 제일 구린 정렬 알고리즘이다.

이 로직을 자바로 구현해보면 이렇다.

<Run.java>

package algorithm;
 
public class Run {
 
    public static void main(String[] args){
 
        int[] sample = {3, 0, 1, 8, 7, 2, 5, 4, 6, 9};
 
        String before += "";
 
        for(int i = 0; i < sample.length; i++){
            before += sample[i] + "\t";
        }
    
        System.out.println("Before arranged : " + before);
 
 
        BubbleSort bs = new BubbleSort();
        String after = bs.sort(sample);
 
        System.out.println("After arranged by Bubble sort : " + after);
    }
 
}

<BubbleSort.java>

package algorithm;
 
public class BubbleSort {
 
    public BubbleSort(){}
 
    public String sort(int[] target){
    
        int temp;
 
        for(int i = 0; i < target.length; i++){
            for(int j = 0; j < target.length - 1; j++){
                if(target[j] > target[j+1]){
                    temp = target[j];
                    target[j] = target[j+1];
                    target[j+1] = temp;    
                }
            }
        }
 
        
        String after = "";
        
        for (int i = 0; i < target.length; i++){
            after += target[i] + "\t";
        }
 
        return after;
    }
}