24.03.19

bubble sort 알고리즘

// 14
public static void main(String[] args) {

		//정렬(sort)하기
		Scanner kb = new Scanner(System.in);
		
		int n = kb.nextInt();
		int [] data = new int[n];
		
		for (int i = 0; i < n; i++) {
		data[i] = kb.nextInt();
		}
		
		//bubble sort
		for (int i = n-1; i > 0; i--) {
			//data[0] ~ data[i]
			for (int j = 0; j < i; j++) {
				if (data[j] > data[j + 1]) {
					//data[j] 와 data[j + 1]의 자리를 바꾼다(swap)
					int tmp = data[j];
					data[j] = data[j + 1];
					data[j + 1] = tmp;
				}
			}
		}
		
		System.out.println("sort data : ");
		for (int i = 0; i < n; i++) {
			System.out.print(data[i]);
		}
	}

정수 tmp가 입력되었을 때 뒤에서부터 j의 값과 비교
tmp가 j보다 작으면 j를 i+1칸(한칸 뒤)으로 옮긴다

// 15
public static void main(String[] args) {

		//n개의 정수를 입력받는데, 정수가 하나씩 입력될 때마다 현재까지 입력된 정수들을 오름차순으로 정렬해 출력
		//bubble sort로도 되지만 불필요한 많은 과정이 필요해서 효율적이진 않다
		Scanner kb = new Scanner(System.in);
		
		int n = kb.nextInt();
		int [] data = new int[n];
		
		for (int i = 0; i < n; i++) { //
			int tmp = kb.nextInt();
			
			int j = i - 1;
			while (j >= 0 && data[j] > tmp) {
				data[j + 1] = data[j]; // 한칸 뒤로 이동
				j--;
			}
			data[j + 1] = tmp;
			
			//출력
			for (int k = 0; k <= i; k++) {
				System.out.print(data[k] + " ");
				System.out.println();
			}
		}
	}

출력값을 이렇게 정수가 입력되는 동시에 배열을 나타내주면
훨씬 효율적
5
4
4
2
2 4
9
2 4 9
6
2 4 6 9
1
1 2 4 6 9