[백준/Java] 2750번 수 정렬하기 1 (버블정렬)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

// 버블 정렬
public class Main {
	public static void main(String[] args) throws Exception {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		// 숫자의 개수 N 입력받기
		int N = Integer.parseInt(st.nextToken());

		// 배열
		int[] A = new int[N];
		
		// 배열에 N개의 수 입력받기
		for(int i=0; i<N; i++) 
		{
			st = new StringTokenizer(br.readLine());
			A[i] = Integer.parseInt(st.nextToken());
		}
		
		// 오름차순으로 정렬하기
		// Arrays.sort(A);
		
		// 버블 정렬
		for (int i = 0; i<N-1; i++)
		{
			for(int k = 0; k < N-1 -i; k++)
			{
				if(A[k] > A[k+1])
				{
					int tmp = A[k];
					A[k] = A[k+1];
					A[k+1] = tmp;
				}
			}
		}
		
		// 정렬된 배열 출력하기
		for(int i=0; i<N; i++) 
		{
			System.out.println(A[i]);
		}
		br.close();
		
		
	}
}

버블정렬 bubble sort 은

두 인접한 데이터의 크기를 비교해

정렬하는 방법입니다.

 

간단하게 구현할 수 있지만,

시간 복잡도는 O(n^2)으로 

다른 정렬 알고리즘보다 속도가 느린 편입니다.

 

루프를 돌면서 인접한 데이터 간의

swap 연산으로 정렬합니다.

 

 

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

 

이렇게 작성을 했었는데...

		// 버블 정렬
		for (int i = 1; i<N; i++)
		{
			for(int k = 0; k < i; k++)
			{
				if(A[k] > A[i])
				{
					int tmp = A[k];
					A[k] = A[i];
					A[i] = tmp;
				}
			}
		}

 

이렇게 작성하는 게 더 효율적인 건가?

		// 버블 정렬
		for (int i = 0; i<N-1; i++)
		{
			for(int k = 0; k < N-1 -i; k++)
			{
				if(A[k] > A[k+1])
				{
					int tmp = A[k];
					A[k] = A[k+1];
					A[k+1] = tmp;
				}
			}
		}