[문제풀이] 06-02. 버블 정렬

인프런, 자바(Java) 알고리즘 문제풀이

Sorting and Searching - 0602. 버블 정렬

🗒️ 문제

🎈 나의 풀이

	private static int[] solution(int[] arr) {
        int tmp;

        for(int i=0; i<arr.length-1; i++) {
            for(int j=0; j<arr.length-1; j++) {
                if(arr[j] > arr[j+1]) {
                    tmp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }
            }
        }
        return arr;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];

        for(int i=0; i<n; i++) arr[i] = sc.nextInt();

        arr = solution(arr);

        for(int i : arr) System.out.print(i + " ");
    }

🖍️ 강의 풀이

  public int[] solution(int n, int[] arr){
		for(int i=0; i<n-1; i++){
			for(int j=0; j<n-i-1; j++){
				if(arr[j]>arr[j+1]){
					int tmp=arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=tmp;
				}
			}	
		}
		return arr;
	}
	public static void main(String[] args){
		Main T = new Main();
		Scanner kb = new Scanner(System.in);
		int n=kb.nextInt();
		int[] arr=new int[n];
		for(int i=0; i<n; i++) arr[i]=kb.nextInt();
		for(int x : T.solution(n, arr)) System.out.print(x+" ");
	}

💬 짚어가기

해당 문제는 정렬 알고리즘 중 하나인 버블 정렬이다.
배열을 순회하며 n번 쨰 요소와 n+1번 째 요소의 값을 비교한다.
만일 뒤에 오는 요소 의 값이 더 큰 경우 두 요소의 값을 swap하여 정렬한다.

두개의 중첩 반복문을 순회하여 $O(n^2)$의 시간 복잡도를 갖는다.