02. 빅오 표기법 & 버블소트, 선택정렬

빅오표기법

알고리즘을 하기에 앞서서 빅오표기법에 대한 이해가 필요합니다.

빅오표기법은 알고리즘을 수행하는 것에 있어 얼마나 많은 횟수를 통해서

실행되는 지에 관해 수학적 수식을 통해서 보여주는 것을 의미합니다.

O(n) O(n2) O(log n)

O(n)		O(n2)		O(log n)
원소	횟수	원소	횟수	원소	횟수
1	1	1	1	1	0
2	2	2	4	2	1
3	3	3	9	3	2
4	4	4	16	4	2
10	10	10	100	10	4
100	100	100	10000	100	7

위의 표처럼 빅오표기법에 의해 발생할 수 있는 최악의 조건들은 위와 같다.

그만큼 효율성 있는 알고리즘을 찾아야 되는 것이라고 생각한다.

Burble Sort

버블소트는 1사이클을 통해서 가장 큰 수를 가장 마지막 인덱스에 넣는 것이다.

{3,5,1,7,9,0}이 있다면 {3,5}를 비교하고, {5,1}을 비교한 후에 위치를 바꾸고, 

{5,7}을 비교하고 {7,9}를 비교하고, {9,0}을 비교해서 교환한다.

이처럼 한 번의 사이클을 통해 '9'라는 가장 큰 숫자를 마지막 인덱스에 놓는 직관적이고 단순한 정렬이다.

버블소트는 O(n2)로 표현된다.

그 이유는 최악의 조건에서 5개의 원소의 리스트가 있다면

4+3+2+1 = 10 번의 검색이 필요하고

4+3+2+1 = 10 번의 교환이 필요하다.

그렇기 때문에 비효율적인 소트라고 한다.

하지만 구현하기가 쉽고 직관적인 장점이 있다.

public class BurbleSortExample {
    public static void main(String[] args) {
        int[] boxs = {3,7,2,1,4,8,9,0};//burble sort는 가장 큰 값부터 정렬 된다. 결국 인덱스 하나씩 깍을 수 있겠다.
        BurbleSortExample burbleSort = new BurbleSortExample();//객체 생성
        burbleSort.sortWithBurble(boxs);
    }
    
    public void sortWithBurble(int[] notSortedBox) {
        System.out.println("START");
        int burbleSize = notSortedBox.length;//box의 size를 for문 1회마다 1개씩 깍기 위해서 사용.
        for(int j=0; j<notSortedBox.length-1;j++) {//버블소트의 사이클
            boolean sortedBool = true;
            for(int i=0; i<burbleSize-1; i++) {//한 사이클의 횟수
                if(notSortedBox[i] > notSortedBox[i+1]) {
                    //sort가 되지 않은 상태
                    sortedBool = false;
                    //앞에 수가 뒤에서보다 작은 경우
                    int temp = notSortedBox[i];
                    notSortedBox[i] = notSortedBox[i+1];
                    notSortedBox[i+1] = temp;
                    //값을 교환
                }
            }
            if(sortedBool) {
                //sort가 된 상태라면 for문 종료
                break;
            }
            //출력
            for(int i=0; i<notSortedBox.length-1;i++) {
                System.out.print(notSortedBox[i]+" ");
            }
            //횟수를 1회씩 줄이기 위해서 burbleSize 줄여나감
            burbleSize = burbleSize - 1;
            System.out.println(String.format(":::%d번째 burble", j+1));
        }
    }
}
 

Selection Sort

선택정렬은 1사이클 통해서 가장 작은 값이나 가장 큰 값을 찾아낸 후에

그 값을 for문의 index에 맞게 맞춰주는 것이다.

{3} -> {5} 비교

{3} -> {1} 비교, 저장

{1} -> {7} 비교

{1} -> {9} 비교

{1} -> {0} 비교, 저장, 스왑

선택정렬은 O(n2)로 표현된다.

그 이유는 최악의 조건에서 5개의 원소의 리스트가 있다면

4+3+2+1 = 10 번의 검색이 필요하고

1+1+1+1 = 4 번의 교환이 필요하다.

public class SelectionSortExample {
    public static void main(String[] args) {
        int[] box = {3,7,2,1,4,8,9,0};
        SelectionSortExample selection = new SelectionSortExample();
        selection.sortWithSelectionSort(box);
    }
    
    public void sortWithSelectionSort(int[] notSortedBox) {
        for(int j=0; j<notSortedBox.length-1; j++) {
            int minIndex = -1;//가장 작은 인덱스
            int minNum = 99999999;//가장작은 숫자
            for(int i=j; i<notSortedBox.length; i++) {
                //i값을 하나씩 크게 해줘야하기 때문에 i=j를 통해서 for문의 인덱스와 같게 함.
                if(notSortedBox[i]<=minNum) {
                    //minNum보다 선택한 인덱스의 아이템 값이 작을 경우에 정보를 저장시켜둠.
                    minIndex = i;
                    minNum = notSortedBox[i];
                }
            }
            
            //for문이 끝난 후에 값을 바꿔줌
            int temp = notSortedBox[j];
            notSortedBox[j] = notSortedBox[minIndex];
            notSortedBox[minIndex] = temp;
            
            //배열의 값을 확인
            for(int i=0;i<notSortedBox.length;i++) {
                System.out.print(notSortedBox[i]+" ");
            }
            System.out.println(String.format(":::%dth sorted", j+1));
        }
 
    }
}
 

1인 개발을 하고 있는 백수입니다...

2018/10/21 - [나의 일기] - (리뷰) 시간표 어플리케이션 - 담다

2018/07/15 - [나의 일기] - #담아두다 #일상 #다이어리 #어플리케이션