[JAVA] 백준 2750번 수 정렬하기1 : 버블 정렬 (Bubble Sort)

2750번: 수 정렬하기

 

1. 문제 추상화

 

N개의 수가 주어졌을 때, 오름차순으로 정렬하시오.

 

2. 알고리즘 

 

( 아래 포스팅에 정리해두었으니 참고바랍니다. )

[ JAVA ] 버블정렬 향상 시키기

 

3. 코드 구현

 

3-1) 버블정렬 코드

 

< 일반적인 버블 정렬 >

 

// 일반적인 버블정렬 ( i와 j 를 이용하여 하나씩 모두 비교 )
	public static void doSort() {
		for(int i=0; i<arr.length-1;i++) {
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					swap(j);
				}
			}
		}
	}

 

 

< 교환횟수를 활용한 방법 >

 

public static void doSort() {
		for(int i=0; i<arr.length-1;i++) {
			int exNum = 0; // 교환횟수
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					swap(j);
					exNum++; // 교환이 일어나면 +1
				}
			}
			if(exNum == 0) break; // 교환이 0이면 break;
		}
	}

 

 

< 마지막 교환이 일어난 위치를 활용한 방법>

 

public static void doSort() {
		for(int i=0; i<arr.length-1;i++) {
			int lastSwap = arr.length-1;// 교환이 일어난 미지막 위치
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					swap(j);
					lastSwap = j-1; // 교환이 일어난 위치 최신화
				}
			}
			i = lastSwap; // 교환이 일어난 마지막 위치 i에 삽입
		}
	}

 

3-2) 전체 코드

 

< 일반적인 버블 정렬 >

import java.util.Scanner;

public class Main {
	
	private static int[] arr;
	private static Scanner sc;
	
	public static void main(String[] args) {
		createArr();
		doSort();
		print();
	}
	
	public static void createArr() {
		makeArr();
		setArr();
	}

	public static void doSort() {
		for(int i=0; i<arr.length-1;i++) {
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					swap(j);
				}
			}
		}
	}
	
	public static void print() {
		for( int value : arr) {
			System.out.println(value);
		}
	}
	
	public static void makeArr() {
		sc = new Scanner(System.in);
		int size = sc.nextInt();
		arr = new int[size];
	}

	public static void setArr() {
		for(int i=0; i<arr.length;i++) {
			arr[i] = sc.nextInt();
		}
	}
	
	public static void swap(int j) {
		int tmp = arr[j];
		arr[j] = arr[j-1];
		arr[j-1] =tmp;
	}
}

 

< 교환횟수를 활용한 방법 >

 

import java.util.Scanner;

public class Main {
	
	private static int[] arr;
	private static Scanner sc;
	
	public static void main(String[] args) {
		createArr();
		doSort();
		print();
	}
	
	public static void createArr() {
		makeArr();
		setArr();
	}
	
	public static void doSort() {
		for(int i=0; i<arr.length-1;i++) {
			int exNum = 0;
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					swap(j);
					exNum++;
				}
			}
			if(exNum == 0) break;
		}
	}
	
	public static void print() {
		for( int value : arr) {
			System.out.println(value);
		}
	}
	
	public static void makeArr() {
		sc = new Scanner(System.in);
		int size = sc.nextInt();
		arr = new int[size];
	}

	public static void setArr() {
		for(int i=0; i<arr.length;i++) {
			arr[i] = sc.nextInt();
		}
	}
	
	public static void swap(int j) {
		int tmp = arr[j];
		arr[j] = arr[j-1];
		arr[j-1] =tmp;
	}
}

 

< 마지막 교환이 일어난 위치를 활용한 방법>

 

import java.util.Scanner;

public class Main {
	
	private static int[] arr;
	private static Scanner sc;
	
	public static void main(String[] args) {
		createArr();
		doSort();
		print();
	}
	
	public static void createArr() {
		makeArr();
		setArr();
	}
	
	public static void doSort() {
		for(int i=0; i<arr.length-1;i++) {
			int lastSwap = arr.length-1;
			for(int j=arr.length-1; j>i; j--) {
				if(arr[j] < arr[j-1]) {
					swap(j);
					lastSwap = j-1;
				}
			}
			i = lastSwap;
		}
	}
	
	public static void print() {
		for( int value : arr) {
			System.out.println(value);
		}
	}
	
	public static void makeArr() {
		sc = new Scanner(System.in);
		int size = sc.nextInt();
		arr = new int[size];
	}

	public static void setArr() {
		for(int i=0; i<arr.length;i++) {
			arr[i] = sc.nextInt();
		}
	}
	
	public static void swap(int j) {
		int tmp = arr[j];
		arr[j] = arr[j-1];
		arr[j-1] =tmp;
	}
}