🤖 알고리즘

해커랭크. Sorting: Bubble Sort (java)

ttoance 2022. 3. 26. 19:36
반응형
 

Sorting: Bubble Sort | HackerRank

Find the minimum number of conditional checks taking place in Bubble Sort

www.hackerrank.com

 

자바 [JAVA] - 거품 정렬 (Bubble Sort)

[정렬 알고리즘 모음] 더보기 1. 계수 정렬 (Counting Sort) 2. 선택 정렬 (Selection Sort) 3. 삽입 정렬 (Insertion Sort) 4. 거품 정렬 (Bubble Sort) - [현재 페이지] 5. 셸 정렬 (Shell Sort) 6. 힙 정렬 (He..

st-lab.tistory.com

- 시간복잡도 :  O(n2) 

ㄴ 하나도 swap가 일어나지 않은 경우에 턴을 종료하는 변수를 두어 성능을 개선할 수 있음. 

for (int i = 1; i < a.size(); i ++) {
    
    boolean swapped = false; 
        
    for (int j = 0; j < (a.size() - i); j++) {
        if (a.get(j) > a.get(j + 1)) {
            int temp = a.get(j + 1);
            a.set(j + 1, a.get(j));
            a.set(j, temp);
            
            swapped = true; 
        }
    }            
    
    // 턴 종료
    if(swapped == false) {
        break;
    }
}

 

 

내 소스코드  

더보기 
import java.io.*;
import java.math.*;
import java.security.*;
import java.text.*;
import java.util.*;
import java.util.concurrent.*;
import java.util.function.*;
import java.util.regex.*;
import java.util.stream.*;
import static java.util.stream.Collectors.joining;
import static java.util.stream.Collectors.toList;

class Result {

    /*
     * Complete the 'countSwaps' function below.
     *
     * The function accepts INTEGER_ARRAY a as parameter.
     */

    public static void countSwaps(List<Integer> a) {
    // Write your code here
    
        int swaps = 0;
        for (int i = 1; i < a.size(); i ++) {
            // debug 
            // System.out.println(i + " : " + a.get(i));
            
            for (int j = 0; j < (a.size() - i); j++) {
                // debug
                // System.out.println(i + " : " + a.get(j) + " > " + a.get(j + 1) );
                if (a.get(j) > a.get(j + 1)) {
                    int temp = a.get(j + 1);
                    a.set(j + 1, a.get(j));
                    a.set(j, temp);
                    swaps++;
                }
            }
            
            // debug 
            // System.out.println(i + " : " + a.get(i));
            // System.out.println(a);
            
        }
        System.out.println(String.format("Array is sorted in %s swaps.", swaps));
        System.out.println(String.format("First Element: %s ", a.get(0)));
        System.out.println(String.format("Last Element: %s ", a.get(a.size() - 1)));

    }

}

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(bufferedReader.readLine().trim());

        List<Integer> a = Stream.of(bufferedReader.readLine().replaceAll("\\s+$", "").split(" "))
            .map(Integer::parseInt)
            .collect(toList());

        Result.countSwaps(a);

        bufferedReader.close();
    }
}

 

반응형