(알고리즘) 정렬 (1) - 개요 및 버블 정렬

정렬이란?

핵심 항목(Key)을 기준으로 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업

 

---

버블 정렬

이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬

 

public class BubbleSort2 {
    public static void main(String[] args) {
        System.out.println("버블 정렬 왼쪽부터");
        Scanner sc = new Scanner(System.in);
        System.out.println("요솟수 : ");
        int num = sc.nextInt();
        int[] array = new int[num];

        for (int i=0 ; i < num ; i++) {
            array[i] = sc.nextInt();
        }
        bubbleSort(array, num);
        System.out.println("결과");

        for (int i=0 ; i<num ; i++) {
            System.out.printf("x["+i+"]="+array[i]+ " ");
        }
    }
    private static void bubbleSort(int[] array, int length) {
        for (int i=0 ; i<length-1 ; i++) {
            for (int k=i ; k<length-1 ; k++) {
                if (array[k] > array[k+1]) 
                    swap(array, k);
            }
        }
    }

    private static void swap(int[] array, int i) {
        int temp = array[i];
        array[i] = array[i+1];
        array[i+1] = temp;
    }
}

 

버블 정렬의 이동평균 횟수는 n(n-1) / 2이다.

• 첫 패스의 비교 횟수 : 1 ~ n-1  -> n-1
• 두 번째 패스 비교 횟수  : 2 ~ n-1 -> n-2
• ...
• (n-1) + (n-2) + (n-3) +... + 2+1