[정렬] 버블정렬

정렬

정렬 알고리즘	정의	시간복잡도
삽입	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식	O(N) ~ O(N^2)
버블	데이터의 인접 요소끼리 비교하고, swap 연산을 수행하며 정렬하는 방식	O(N^2)
선택	대상에서 가장 크거나 작은 데이터를 찾아가 선택을 반복하면서 정렬하는 방식	O(N^2)
퀵	pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식	O(NlogN) ~ O(N^2)
힙	이진트리를 이용하여 최대힙(오름차순)/최소힙(내림차순) 트리를 구성해 정렬하는 방식	O(NlogN)
병합	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식	O(NlogN) + 추가적인 메모리 필요
기수	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식	O(N) + 추가적인 메모리 필요

 

버블정렬

데이터의 인접 요소끼리 비교하며, 차례대로 제일 큰 숫자를 맨 뒤로 보내며 정렬하는 방식

10

40

30

20

10

30

40

20

10

30

20

40

• 위의 방식대로, 큰 숫자를 뒤로 보내며 정렬하는 방식 (40이 맨뒤로 갔음)
• O(N^2)의 시간복잡도를 가짐

 

버블정렬 과정

1. 비교 연산이 필요한 루프 범위를 설정
2. 인접한 데이터 값을 비교
3. swap조건에 부합ㅂ하면 swap 연산을 수행
4. 루프범위가 끝날때까지 2~3 반복
5. 정렬 영역을 설정 (다음 루프를 실행할때는 이 영역 제외)
6. 비교 대상이 없을때까지 1~5 반복

 

버블정렬 구현

public static void main(String[] args) throws Exception {
        
        int []arr = {5,2,1,4,3};

        for (int i =0; i < arr.length; i++){
            for(int j =0; j< arr.length -1 -i; j++){ // 이미 정렬된 맨뒤 부분 제외 ( arr.length -1 -i )
                if (arr[j] > arr[j+1]){
                    int temp = arr[j+1];
                    arr[j+1] = arr[j];
                    arr[j] = temp;
                }
            }
        }

        for (int i : arr) {
            System.out.println(i);
        }
    }