버블정렬BubbleSort

예를들어 {10, 9, 8, 7} 배열이 있을때
인덱스 0번, 1번 비교해서 왼쪽이 더크면 스왑
인덱스 1번, 2번 비교해서 왼쪽이 더크면 스왑
...
인덱스 2번, 3번 비교해서 왼쪽이 더크면 스왑

이런식으로 정렬하는 방식이다
한번 순회 할때마다 오른쪽 끝에서 부터 큰 값들이 차례대로 배치된다

1회전 마친후 {9, 8, 7, 10}
2회전 마친후 {8, 7, 9, 10}
3회전 마친후 {7, 8, 9, 10}

그러므로 순회할때마다 비교횟수가 줄어든다. 이미 오른쪽에 배치된 가장 큰 값과 비교할 필요는 없으니까
1회전 시에는 0인덱스 부터 3인덱스 까지 비교
2회전 시에는 0인덱스 부터 2인덱스 까지 비교
3회전 시에는 0인덱스 부터 1인덱스 까지 비교

시간복잡도 O(N^2)

장점
쉽다. 공간복잡도O(N)

단점
비효율적

public class BubbleSort {
    ArrayList<Integer> list;

    BubbleSort()
    {
        list = new ArrayList<>();
    }

    void Add(Integer value)
    {
        list.add(value);
    }

    void Sort()
    {
        int temp = 0;
        for(int i = 0; i < list.size(); ++i)
        {
            for(int j = 0; j + 1 < list.size()-i; ++j)
            {
                if(list.get(j) > list.get(j+1))
                {
                    temp = list.get(j);
                    list.set(j, list.get(j+1));
                    list.set(j+1, temp);
                }
            }
        }
    }

    @Override
    public String toString() {
        return "BubbleSort{" +
                "list=" + list +
                '}';
    }
}

public static void main(String[] args) 
{
	BubbleSort bs = new BubbleSort();

	bs.Add(10);
    bs.Add(9);
    bs.Add(8);
    bs.Add(7);

	bs.Sort();

    System.out.println(bs);

   }

공간복잡도는 n이다.

시간복잡도는
등차수열의 합 공식을 통해 유도할 수 있다 출처(GPT4)

등차수열의 합 공식은 다음과 같습니다.
S_n = n(2a_1 + (n-1)d) / 2

이 문제의 경우, a_1은 첫 번째 항이므로 n-1이고, d는 공차로서 -1입니다. n은 항의 개수로, 주어진 수열의 경우 n개의 항이 있습니다.

공식에 주어진 값을 대입하면 다음과 같습니다.
S_n = n(2(n-1) + (n-1)(-1)) / 2

이제 식을 간단히 해보겠습니다.
S_n = n((2n-2) - (n-1)) / 2
S_n = n(2n-2 - n + 1) / 2
S_n = n(n-1) / 2

이렇게 주어진 수열 (n-1) + (n-2) + ... + 2 + 1의 합은 등차수열의 합 공식을 사용하여 (n-1) * n / 2로 구할 수 있습니다.

근데 나는 등차수열의 합 공식을 외울 자신이 없어서 물어봤다 공식을 몰라도 구할 수 있냐고

등차수열의 합 공식을 알지 못해도, 문제에 주어진 수열 (n-1) + (n-2) + ... + 2 + 1의 합을 구하는 방법을 알려드리겠습니다.

주어진 수열은 다음과 같이 나타낼 수 있습니다.

S = (n-1) + (n-2) + ... + 2 + 1

이제 수열의 항을 역순으로 나열한 새로운 수열을 만들어 보겠습니다.

S' = 1 + 2 + ... + (n-2) + (n-1)

S와 S'를 합해보면 각 항이 n이 되는 새로운 수열이 만들어집니다.

S + S' = (n) + (n) + ... + (n) + (n)

위 수열에는 총 n-1개의 항이 있습니다. 따라서 합은 다음과 같습니다.

S + S' = (n-1) × n

이제 양변을 2로 나눠주면 원래의 수열 S의 합을 구할 수 있습니다.

S = [(n-1) × n] / 2

이렇게 등차수열의 합 공식을 알지 못해도, 주어진 수열의 합을 유도할 수 있습니다. 이 방법은 가우스의 덧셈이라고 불리며, 어린 시절 가우스가 발견한 방법입니다.

간단하게 구할 수 있다. 가우스라는 사람이 어린시절에 발견했다고 한다;; 와우 진짜 천재구나...

CS 공부하면서 복습하게 되었다
다시 짜보는데 왜 막힐까;;

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


        //int[] arr = {5, 20, 6, 10, 2};
        int[] arr = {20, 10, 6, 5, 2};

        int counter = 0;

        for (int i = 0; i < arr.length; i++) {
            for (int j = 1; j < arr.length-i; j++) {
                counter++;
                if(arr[j-1] > arr[j]){
                    int temp = arr[j];
                    arr[j] = arr[j-1];
                    arr[j-1] = temp;
                }

            }
        }

        for (int i : arr){
            System.out.println(i);
        }
        System.out.println("count: " + counter);
    }
}