자료구조_정렬 ② 버블정렬

 

[1] 버블정렬

---

(1) 버블정렬 개념 

bubble 정렬

인접한 두 값의 대소 관계를 비교하여 오름차순이나 내림차순 형태로 값을 교환하여 정렬한다 

각 인덱스 값을 비교하여 패스쓰루를 반복하기 때문에 시간복잡도가 크다

- 정렬되지 않은 배열이 주어졌을때 오름차순으로 정렬하기

- 정렬되지 않은 배열이 주어졌을때 중복 값을 찾기 

- 정렬되지 않은 배열이 주어졌을때 최대값 찾기 

- 단순 정렬

(2) 버블정렬 과정 

1. 인덱스 1과 인덱스 2를 비교하여

인덱스1 > 인덱스 2 의 값이면 두 항목을 교환한다 

인덱스1 < 인덱스 2 의 값이면 아무것도 하지 않는다 

2. 인덱스 포인터를 +1 옮긴다 

3. 인덱스 2 와 인덱스 3을 비교하여 .... 똑같은 작업을 반복한다 

4. 인덱스 0부터 인덱스 마지막까지 비교 후 다시 처음 인덱스 0 과 인덱스 1을 다시 비교하여 완벽하게 교환되는 항목이 없을때까지 반복한다 (왜냐하면 이후 단계에서 교환이 적용되었을때 교환 적용된 인덱스와 비교 안해봤기 때문에 다시 비교한다 ) 

 

(3)시간복잡도 O(N⌒2)

 

int [] arr = { 3 , 1 , 5 , 7 , 10 }

정렬되지 않은 배열의 값을 오름차순으로 정렬하기 

인덱스 i 와 인덱스 i+1 를 비교한다 

첫번째 패스쓰루의 마지막 인덱스 값은 이미 정렬이 끝났기 때문에 반복할때마다 인덱스 1을 줄여준다 

 

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

 

(3-1) 선형 해결법 : O(N)

버블 정렬의 시간복잡도를 해결하기 위해 선형 해결법을 사용한다

빈 배열을 만들어 검색하는 배열의 값을 인덱스로 넣는다

 

1. 배열 값에 중복값이 있다면 true , 없다면 false 반환한다

 

arr [] { 3 , 1 ,  7 , 5 , 1 , 10 }

new existingNumbers [] = { } 

 

3은 인덱스 3으로 

1은 인덱스 1으로 

7은 인덱스 7으로

5은 인덱스 5으로

1은 인덱스 1에 이미 값이 있다 

10은 인덱스 10으로

 

existingNumbers [] = { 1 , null , null , 3 , null , 5, null , 7 , null , null ,10 }

 

public static boolean hasDuplicateValue2(int[] array) {
    ArrayList<Integer> existingNumbers = new ArrayList<>();

    for (int value : array) {
        if (existingNumbers.contains(value))
            return true;
        else
            existingNumbers.add(value);
    }

    return false;
}

 

2. 최대값을 찾는다 

for 반복문으로 배열의 값과 임의의 greatestNumber 숫자와 비교하여 큰 숫자를 찾아 그 값을 greatestNumber에 담아 반환한다 

public static int greatestNumber2(int[] array) {
    int greatestNumber = array[0];
    
    for (int number : array) {
        if (number > greatestNumber)
            greatestNumber = number;
    }
    
    return greatestNumber;
}