No2750 버블정렬 이용해서 수 정렬하기

[문제]

[입출력 형식]

사실 이 문제는 간단하게 풀고자한다면 sort() 메소드를 이용해서 간단하게 풀 수 있다. 나역시 sort 메소드를 이용해서 몇 초만에 문제를 풀었고, 이후에도 유사한 문제들을 sort 메소드를 이용해서 간단하게 풀었지만 그렇게하면 알고리즘 실력을 쌓을 수 없기 때문에 정렬 알고리즘에 대해서 공부를 다시 하고 알고리즘을 활용해서 문제를 풀어봤다.

오늘 공부한 정렬은 버블정렬으로 버블정렬이란 인접한 두 개의 값을 비교해서 정렬을 해주는 알고리즘 방식이다.

간단하게 구현할 순 있지만 시간 복잡도는 O(n제곱)으로 다른 정렬 알고리즘보다 속도가 느린 편이다!

 

[버블 정렬 과정]

위의 예시를 보고 간략하게 설명을 해보자면 현재 [5 2 3 4 1]이란 값이 저장되어있는 상태이고 오름차순으로 정렬을 해줄 것이다.

1. 처음 인덱스와 그 다음 인덱스의 값을 비교해준다. (5, 2)
2. 5가 더 크므로 두 값을 바꿔준다. [2 5 3 4 1]
3. 다음 1번 인덱스와 2번 인덱스의 값을 비교해주고 (5, 3) 앞의 값이 더 크면 자리를 바꾼다. [2 3 5 4 1]
4. 이 과정을 루프 범위가 끝날 때까지 반복해준다. [2 3 4 1 5]
5. 제일 마지막에 도달한 값은 max값이므로 마지막 인덱스를 제외한 나머지 값들을 똑같이 루프를 돌면서 값을 비교해준다.
6. 비교 대상이 없을때까지 이 과정을 반복한다.

(만약 첫번째 루프에서 swap이 한번도 발생하지 않았다면 이미 정렬이 되어진 값들이 들어온 것이므로 더이상 이 과정을 반복하지 않도록 프로세스를 종료해줄 수 있는 지점을 만들어주는 것이 좋다!)

 

[수도코드]

• int N : 정렬할 수의 갯수
• List나 배열을 선언
• for(0 ~ N-1) 만큼 루프 선언 -> 한번 정렬 과정을 거쳤다면 마지막 인덱스를 제거하고 다시 루프 돌기 위해 for(0 ~ N-1-i) 범위 설정
• if(index i > index i+1) -> swap
• 한번도 swap 과정을 거치지 않았는지 확인하기 위한 변수 지정(boolean or count)
• 정렬이 완료된 값 출력

 

[코드]

List - swap메소드를 이용한 코드

import java.util.*;

public class Main {

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    List<Integer> list = new ArrayList<>();
    int N = in.nextInt(); //N: 정렬할 수의 갯수

    //list에 값 입력 받기
    for(int i=0;i<N;i++) {
        list.add(in.nextInt());
    }

    //버블정렬 구현
    for(int i=0;i<N-1;i++) { 
        int count = 0;
        for(int j=0;j<N-1-i;j++) {
            if(list.get(j) > list.get(j+1)) {
                Collections.swap(list,j,j+1);
                count++;
            }
            //swap이 한번도 이루어지지 않았다면 종료
        }if(count == 0) break;
    }

    //결과 출력
    list.forEach(i -> System.out.println(i));

}
}

* 중첩 for문이 사용된 이유와 범위 설정의 이유 :

총 루프가 도는 과정을 생각해보면 한번 루프가 돌고나면 그 다음부터는 마지막 인덱스를 제외한 상태로 루프를 돌게된다. 그 말은 N-1번째 루프가 실행이 되고나면 전체 정렬 과정이 끝난다는 뜻이다. 따라서 바깥 for문은 break; 조건을 만족하지 않는 이상 무조건 N-1번 실행이 되어야 한다는 말이고, 중첩된 for문은 한번 루프가 돌 때 인덱스 범위를 줄이기 위해 사용되었다. N개의 인덱스가 있을 때 첫번째 루프는 M-1만큼 돌아야하고 두번째 루프는 M-2만큼 돌아야한다. 따라서 N-1-i의 범위가 나오게 되는 것이다.

 

배열을 이용한 코드

import java.util.*;

public class Main {

public static void main(String[] args) {

    Scanner in = new Scanner(System.in);
    int N = in.nextInt(); //N: 정렬할 수의 갯수

    int[] arr = new int[N];

    //배열에 값 입력 받기
    for(int i=0;i<N;i++) {
        arr[i] = in.nextInt();
    }

    //버블정렬 구현
    for(int i=0;i<N-1;i++) {
        for(int j=0;j<N-1-i;j++) {
            if(arr[j] > arr[j+1]) {
                int tmp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = tmp;
            }
        }
    }


    //결과 출력
    for(int i=0;i<N;i++) {
        System.out.println(arr[i]);
    }

}
}

배열을 이용하게 되면 swap 메소드를 사용할 수 없으므로 tmp값을 이용해서 값의 순서를 바꿔주면 된다. 위 코드는 따로 swap 여부를 확인해주기 위한 count변수를 주지 않았는데 이렇게되면 [1 2 3 4 5] 값이 들어와있더라도 N-1번 루프를 돌기 때문에 비효율적이다.