버블정렬

문제 . N개 숫자가 입력되면 오름차순으로 선택정렬하시오.

 

입력 예시

6
13 5 11 7 23 15

 

답 : 

5 7 11 13 15 23

 

 

나의 답변

public class Main {	
	
	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 temp = arr[j]; 
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		return arr;
	}
	public static void main(String[] args) {
		Main T = new Main();
		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 x : T.solution(n, arr)) {
			System.out.print(x + " ");
		}
	}
}

 

 

---

 

버블정렬

 

배열의 연속된 두 항목을 가리켜서 비교한다. 두 항목의 순서가 뒤바뀌어있으면 교환한다.

패스스루를 돌 때마다 가장 큰 값, 즉 '버블'이 올바른 위치에 위치한다.

 

원소 N개가 있을 때

비교횟수는 (N - 1) + (N - 2) + (N - 3) + ... + 1번의 비교이다. 

교환횟수는 비교할때마다 순서가 바뀌어있을시 일어난다. 

최대횟수는 배열이 역순으로 이뤄졌을 때 일어난다.

버블정렬은 n^2 단계이며 시간 복잡도가 O(n^2)이기 때문에 비효율적이다.

선택정렬도 O(n^2)이지만 버블정렬이 2배 더 느리다.