Sorting: Bubble Sort

🔗 문제 링크

https://www.hackerrank.com/challenges/ctci-bubble-sort/problem?h_l=interview&playlist_slugs%5B%5D=interview-preparation-kit&playlist_slugs%5B%5D=sorting

❔ 문제 설명

Consider the following version of Bubble Sort:

for (int i = 0; i < n; i++) {
    
    for (int j = 0; j < n - 1; j++) {
        // Swap adjacent elements if they are in decreasing order
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
        }
    }  
}

Given an array of integers, sort the array in ascending order using the Bubble Sort algorithm above. Once sorted, print the following three lines:

1. Array is sorted in numSwaps swaps., where numSwaps is the number of swaps that took place.

2. First Element: firstElement, where firstElement is the first element in the sorted array.

3. Last Element: lastElement, where lastElement is the last element in the sorted array.

Hint: To complete this challenge, you must add a variable that keeps a running tally of all swaps that occur during execution.

Example

a = [6,4,1]

swap    a       
0       [6,4,1]
1       [4,6,1]
2       [4,1,6]
3       [1,4,6]

The steps of the bubble sort are shown above. It took swaps to sort the array. Output is:

Array is sorted in 3 swaps.  
First Element: 1  
Last Element: 6  

Function Description

Complete the function countSwaps in the editor below.

countSwaps has the following parameter(s):

• int a[n]: an array of integers to sort

Prints

Print the three lines required, then return. No return value is expected.

Input Format

The first line contains an integer, n, the size of the array a.
The second line contains n space-separated integers a[i].

⚠️ 제한사항

• $2 ≤ n ≤ 600$

• $1 ≤ a[i] ≤ 2 × 10^6$

---

💡 풀이 (언어 : Java)

전에 풀었던 버블 정렬의 복습 문제이다. j에서 i만큼 빼준 최대값 만큼 인덱스를 돌아주면 더 효율적인 알고리즘이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	private static void countSwaps(int n, int[] arr) {
		int count = 0;
		for (int i = 0; i < n; i++) {
            // i 반복 한번 할때마다 뒤에 고정 최대값이 한자리씩 차지하므로 n-i-1
			for (int j = 0; j < n - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					int tmp = arr[j + 1];
					arr[j + 1] = arr[j];
					arr[j] = tmp;
					count++;
				}
			}
		}
		System.out.println(String.format("Array is sorted in %d swaps.", count));
		System.out.println(String.format("First Element: %d", arr[0]));
		System.out.println(String.format("Last Element: %d", arr[n-1]));
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(br.readLine());
		int[] arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
		countSwaps(n, arr);
	}
}