[TTL] 2023.3.3

🤔 Bubble Sort에 대한 의문점

package src.workshop;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class Test {
    static StringBuilder sb = new StringBuilder();

    public static void main(String[] args) {
        long beforeTime;
        long afterTime;
        long timeDiff;

        int[] arr = NoOverlab();
        beforeTime = System.currentTimeMillis();
        selectionSort(arr);
        afterTime = System.currentTimeMillis();
        timeDiff = afterTime - beforeTime;
        System.out.println("Normal Case 소요 시간(ms): " + timeDiff);

        int[] arr2 = testWorstCase();
        beforeTime = System.currentTimeMillis();
        selectionSort(arr2);
        afterTime = System.currentTimeMillis();
        timeDiff = afterTime - beforeTime;
        System.out.println("Worst Case 소요 시간(ms): " + timeDiff);
    }

    private static int[] testNormalCase() {
        Random random = new Random();
        int[] arr = new int[100000];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = random.nextInt();
        }
        return arr;
    }

    private static int[] NoOverlab() {
        Random random = new Random();
        Set<Integer> set = new HashSet<>();

        while (set.size() < 100000) {
            set.add(random.nextInt());
        }

        int[] arr = new int[set.size()];
        int i = 0;
        for (int num : set) {
            arr[i++] = num;
        }
        return arr;
    }

    private static int[] testWorstCase() {
        int[] arr = new int[100000];

        for (int i = 0; i < arr.length; i++) {
            arr[i] = arr.length - i;
        }
        return arr;
    }


    private static void bubbleSort(int[] arr) {
        int n = arr.length;

        for (int i = 0; i < n - 1; i++) {
            for (int j = 0; j < n - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {
                    // Swap arr[j] and arr[j+1]
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }
}

Bubble Sort를 구현하고 코드를 돌려보았는데, 결과가 나오기 이전에 Normal Case의 경우에는 교환연산이 반드시 일어나는것이 아니지만, Worst Case의 경우 교환연산이 무조건적으로 일어나기 때문에 당연히 Worst Case가 가장 오래 걸릴 것으로 생각했다.
그러나 결과는 예상과 달리

Normal Case 소요 시간(ms): 13697
Worst Case 소요 시간(ms): 9309

어째서 이런 결과가 나오게 된 것일까?... 흠..? 모르겠다 ㅋㅋ
ChatGPT에 물어보기도 했는데

이상한 답을 내놓기도 한다... 궁금해서 다시 물어보니 자기 설명이 틀렸다고 하네;;

결과적으로 답을 알 수 없어 동료분들께 테스트를 부탁드렸더니 Normal Case가 더 오래걸리는건 똑같다고 하신다.

그래서 대신 ChatGPT에게 코드를 주고 100번 돌린 후 평균값을 출력해달라 부탁해보았다.

Bubble Sort Normal Case 소요 시간(ms): 6672.56
Bubble Sort Worst Case 소요 시간(ms): 248296.49

왜 나의 환경에서는 예상한 결과가 안나오고, GPT에서는 예상 결과가 나오는지 의문이다.

자료정리

스프링 MVC
스프링 이해를 위한 자바 고급 - 1
스프링 이해를 위한 자바 고급 - 2
자바스크립트
데일리 알고리즘 9주차