3011 - 버블 정렬 +

1441과 같은 버블 정렬이지만, 불필요한 단계는 스킵할 수 있는 알고리즘이 추가적으로 요구된다.

 

예를 들어 1 5 3 2 4 를 오름차순으로 정렬한다면,

 

1단계 - 1 3 2 4 5

2단계 - 1 2 3 4 5 (이미 정렬 완료)

3단계 - 1 2 3 4 5

4단계 - 1 2 3 4 5

 

불필요한 3 4단계는 반복문을 깨고 나와서 실행을 하지 않아야 함.

 

 

## 3011

위와 같음

총 몇 단계가 필요한지 출력하는 코드

import java.util.Scanner;

public class CodeUp3011 {
	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();
		}
		sc.close();
		int i;
		int tmp;

		for (i = 0; i < n - 1; i++) {
			int cnt = 0;
			for (int j = 0; j < n - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					tmp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = tmp;
					cnt++;
				}
			}
			if (cnt == 0)
				break;
		}
		System.out.println(i);

	}
}

- 정해진 포멧이 없어서 편하기도 했지만 이게 가장 적절한 코드인지는 모르겠다.