버블 정렬,기수 정렬, 계수 정렬

버블정렬

정렬 되는 모습이 거품이 올라오는 모습과 비슷하다 하여 붙여진 이름

버블 정렬은 각 자리 에 있는 수와 뒤에 있는 수 를 비교하여 앞에 있는수가 작으면 유지 ,앞에 있는 수가 크면 스왑을 하게 되는데, 이과정을 모든 자리에 대해서 진행한다.

  public 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]) {
                        // 두 원소의 위치를 교환
                        int temp = arr[j];
                        arr[j] = arr[j + 1];
                        arr[j + 1] = temp;
                    }
                }
            }
        }

• for문의 루프시작은 0이기 때문에 아웃루프의 n은 n-1 이다 .

장점
구현이 매우 간단하다.
단점
순서에 맞지 않은 요소를 인접한 요소와 교환한다.
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업이 자료의 이동 작업보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

알고리즘의 복잡도

버블정렬은 외부 루프를 N-1번 도는 동안, N-1, N-2, N-3, ... , 1 번 인접한 원소들을 비교한다.

따라서 T(n) = (n-1)+(n-2)+(n-3)+...+1 = (n-1)*n/2

O(n) = n^2 이다.

최상, 평균, 최악 모두 일정

기수정렬