[알고리즘 이론] 정렬 Sort - 2-2 비교 기반 알고리즘 (버블 정렬)

💡예시에 대한 가정
- 입력 크기 n
- 입력 배열 A[0…. n-1]
- 입력 데이터 : 양의 정수
- 정렬 방식 : 오름차순 (1, 2, 3, 4,…)

 

2-2) 버블 정렬 (Bubble sort)

• 모든 인접한 두 데이터를 차례로 비교 후,
  왼쪽 데이터가 더 큰 경우 오른쪽 데이터와 자리를 바꾸는 방식을 반복
• 정렬 과정 : 비교 진행 방향 →, ← 에 따라 비교
  • 비교 진행 방향에 따라 정렬 과정이 달라짐 
    • 왼 → 오 : 큰 값 부터 찾아 오른쪽 끝 부터 위치 (오른쪽 끝부터 정렬)
    …. < 세 번째로 큰< 두번째로 큰 < 가장 큰
    • 왼 ← 오: 가장 작은 값부터 찾아 왼쪽 끝부터 위치 (왼쪽 끝부터 정렬)
    가장 작은 < 두 번째로 작은 < 세번째로 작은 < …..

왼쪽 → 오른쪽

50과 20을 비교
→ “50이 20보다 크다”
→ 그럼 50이 오른쪽!!

1단계의 비교 후 결과 : 가장 큰 값이 오른쪽

왼쪽 ← 오른쪽

10과 40을 비교
→ “10이 40보다 작다”
→ 그럼 10이 왼쪽!!

1단계 비교후 결과 :가장 작은 값이 왼쪽

 

3. 특징

• 성능 : O(n²)
• 제자리 정렬 알고리즘 : 입력 배열 A 이외 상수개(i, j, tmp) 의 저장 공간만 필요
• 안정적 정렬 알고리즘 : [40, 40, 40] 이 있으면 위치교환 미발생
• 선택 정렬보다 데이터 교환이 많이 발생 - 선택정렬보다 비효율적

 

[JS code]

function bubbleSort(A) {
    const n = A.length; 

    for (let i = 0; i < n - 1; i++) { // 단계 : (n-1)번 반복

        for (let j = 0; j < n - 1; j++) { // 왼쪽에서 오른쪽으로 진행하는 경우
            if (A[j] > A[j + 1]) { // ‘왼쪽 데이터 > 오른쪽 데이터’이면

                // A[j]와 A[j+1]의 위치를 바꿈.  예: [50, 10] -> [10, 50]
                let temp = A[j]; // A[j]를 임시로 저장
                A[j] = A[j + 1]; // A[j]에 A[j+1] 값을 대입
                A[j + 1] = temp; // A[j+1]에 임시로 저장한 값을 대입
            }
        }

    }

    return A; // 정렬된 배열을 반환합니다.
}

 

 

4. 개선된 버블 정렬 알고리즘 

• 루프의 반복 횟수를 줄임
  • 1번째 조건 추가 :
    자리바꿈이 발생하지 않으면 이미 정렬 된 상태이면, 이후 비교 없이 종료
  • 2번 째 조건 추가 :
    무조건 왼쪽/오른쪽 끝까지 이동하며 두 데이터를 비교할 필요 없음
     for (j=0; j < (n-1) - i ; j++) 

• 최악의 경우 : 입력 데이터가 역순으로 정렬된 경우 
  • 기존 버블 정렬, 개선된 버블정렬 둘 다 O(n²)
• 최선의 경우 : 입력 데이터가 원하는 순서로 이미 정렬된 경우 
  • 기존 버블 정렬 : 모든 단계 수행 = O(n²)
  • 개선된 버블 정렬 : n번 비교, 자리바꿈 0번 = O(n)

 

[JS code]

function advancedBubbleSort(A) {
    const n = A.length; 

    for (let i = 0; i < n - 1; i++) {
        let sorted = true; // 이미 정렬된 상태로 가정

        for (let j = 0; j < n - 1 - i; j++) { // 왼쪽에서 오른쪽으로 진행
        
            if (A[j] > A[j + 1]) { // 만약 A[j]가 A[j+1]보다 크다면
            
                // A[j]와 A[j+1]의 위치를 바꿈
                let temp = A[j]; 
                A[j] = A[j + 1]; 
                A[j + 1] = temp; 
                
                sorted = false; // 자리바꿈 발생 → 전체적으로 미정렬 상태
                
            }
        }
        
        if (sorted) break; // 이미 정렬된 상태이므로 종료
    }

    return A;
}