[백준]2750번 수 정렬하기1 - 버블정렬

sort() 함수 사용하면 쉽게 끝날 문제지만, 정렬을 직접 구현해보자!

버블정렬 참고
두 인접한 데이터의 크기를 비교해 정렬하는 방법.
인접한 데이터간 swap 연산을 통해 정렬

생각한 풀이
마지막 교환이 일어난 위치를 활용한 방법(참고)

import java.util.Scanner;

public class Practice15 {
	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();
		}

		for(int i=0; i<arr.length-1; i++) {
			int lastSwap = 0; // 교환이 일어난 마지막 위치
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					int tmp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] =tmp;
					lastSwap = j-1; // 교환이 일어난 위치 최신
				}
			}
			i = lastSwap; // 교환이 일어난 마지막 위치 i에 삽입
		}
		
		for (int i = 0; i < N; i++) {
			System.out.println(arr[i]);
		}
		sc.close();
	}
}

난 내가 해낸 줄 알았음

근데 놀랍게도 시간초과... 짱나네..?

그래서 그냥 책에 있는대로 그냥 현재 배열 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수를 바꾸도록 코드를 변경함.

import java.util.Scanner;

public class Practice15 {
	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();
		}

		// 변경한 코드
		for(int i=0; i<arr.length-1; i++) {
			for(int j=0; j<arr.length-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]);
		}
		sc.close();
	}
}

훨씬 간결해졌다.

그리고 통과했다.

내가 생각한 풀이가 시간초과로 실패하면 기분이 더럽다는걸 이번에 깨달았음..