01. 버블 정렬 (Bubble Sort)

정의

두 인접한 데이터를 비교해서 앞에 있는 데이터가 뒤에 있는 데이터보다 크면 자리를 바꾸는 정렬 알고리즘

j 에 따라 인덱스 위치에 영향을 받음

https://coding-factory.tistory.com/615

 

버블정렬은 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 끝부터 정렬하는 방식을 말합니다. 마찬가지로 코드가 간단하므로 구현이 간편합니다. 정렬을 하는 방식이 물속에서 물위로 올라오는 물방울 모양과 같다하여 버블정렬이라고 합니다. n개의 원소에 대하여 n개의 메모리를 사용합니다. 데이터를 하나씩 비교할 수 있어서 정밀하게 비교가 가능하나 비교횟수가 많아지므로 성능면에서는 좋은 방법이 아닙니다. 첫 번째 원소부터 마지막 원소까지 반복하여 한 단계가 끝나면 가장 큰 원소를 마지막 자리로 정렬하는 식으로 정렬이 됩니다. 

분석

 

버블 정렬 (Bubble Sort)

public class BubbleSort {
    public static void main(String[] args) {

        int[] arr = {5, 2, 9, 7, 14, 3, 1};

        for (int i = 0; i < arr.length - 1; i++) {

            for (int j = 0; j < arr.length - i - 1; j++) {

                int tmp = arr[j];

                if (tmp > arr[j + 1]) {
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                }

            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

 

bubbleSort = [5, 2, 9, 7, 14, 3, 1]

for i in range(len(bubbleSort) - 1):

    for j in range(len(bubbleSort) - i - 1):
        if bubbleSort[j] > bubbleSort[j + 1]:
            bubbleSort[j], bubbleSort[j + 1] = bubbleSort[j + 1], bubbleSort[j]
            
print(bubbleSort)

 

패캠 강의 코드

더 이상 정렬할 필요가 없는 경우 for 문을 돌 필요가 없기 때문에 swap 변수를 주어 판단해준다

public class BubbleSort {
    public static void main(String[] args) {

        int[] arr = {2, 1, 3, 5, 7, 9, 14};
        boolean swap;
        int count = 0;

        for (int i = 0; i < arr.length - 1; i++) {

            swap = false;

            for (int j = 0; j < arr.length - i - 1; j++) {
                count++;
                int tmp = arr[j];

                if (tmp > arr[j + 1]) {
                    arr[j] = arr[j + 1];
                    arr[j + 1] = tmp;
                    swap = true;
                }
            }

            if (swap == false) break;
        }
        System.out.println(Arrays.toString(arr));
        System.out.println("count = " + count);
    }
}

 

주었을 때와 안주었을 때의 실행 횟수 확인

 

bubbleSort = [2, 1, 3, 5, 7, 9, 14]

for i in range(len(bubbleSort) - 1):
    swap = False
    for j in range(len(bubbleSort) - i - 1):
        if bubbleSort[j] > bubbleSort[j + 1]:
            bubbleSort[j], bubbleSort[j + 1] = bubbleSort[j + 1], bubbleSort[j]
            swap = True

    if swap == False:
        break

print(bubbleSort)