본문 바로가기
Java/Java 알고리즘

[알고리즘] 1-1. 버블 정렬 #

앤 썸 2022. 6. 27. 16:48
반응형

1. 버블 정렬

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

-간단하게 구현 가능하지만, 시간 복잡도가 O(n^2)로 느리다.

-루프를 돌면서 인접한 데이터간 swap 연산으로 정렬

 

  1. 비교 연산이 필요한 루프 범위 설정
  2. 인접한 데이터 값 비교
  3. swap 조건에 부합하면 swap 연산 수행
  4. 루프 범위 끝날 때까지 비교와 swap연산 반복
  5. 정렬된 영역을 빼고 나머지 실행
  6. 비교 대상이 없을 때까지 해당 과정 반복

 

문제 15. 수 정렬하기1

[백준 온라인 저지 2750번]

N개의 수가 주어졌을 때 이를 오름차순 정렬하는 프로그램을 작성하시오.

 

입력
1 번째 줄에 수의 개수 N(1 < N < 1,000), 2번째 줄부터 N개의 줄에 숫자가 주어진다. 이 수는 절댓값
이 1,000보다 작거나 같은 정수다. 수는 중복되지 않는다.

 

출력
1 번째 줄부터 N개의 줄에 오름차순 정렬한 결과를 1 줄에 1 개씩 출력한다.

 

예제 입력

5 //수의 개수
5
2
3
4
1

 

예제 출력

1
2
3
4
5

1단계. 문제 분석하기

-> O(n^2)의 시간복잡도

 

3단계. 슈도코드 작성하기

N(정렬할 수 개수)
A(정렬할 배열 선언)
for(i : 0 ~ N - 1)
 {
  for(j : 0 ~ N - 1 - i)
  {
   현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기)
  }
 }
A 배열 출력

 

 

package sorting.ch04;

import java.util.Scanner;

public class sorting01_q15 {
	public int[] solution(int n, int [] arr) {
		
		//for, while문
		for(int i=0;i<n;i++) {
			for(int j=0;j<n-1-i;j++) {
				//맨 뒤부터 정렬이 된다.  -> 정렬된 부분은 swap에서 제외.
				if(arr[j]>arr[j+1]) {
					int tmp=arr[j];
					arr[j]= arr[j+1];
					arr[j+1]= tmp;
				}
			}
		}
		return arr;
	}
	public static void main(String[] args) {
		sorting01_q15 T  =new sorting01_q15();
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i=0;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		for(int x: T.solution(n, arr)) {
			System.out.println(x);
		}
		
	}
}

 

 

+) 세련된 풀이

package sorting.ch04;

import java.util.Scanner;

public class sorting01_q15_sol {
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0 ;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		for(int i=0;i<n-1; i++) {
        //비교를 자기 자신보다 +1한 수와 비교하기 때문에 n이 아니라 n+1이어도 가능하다.
			for(int j=0;j<n-1-i;j++) {
				if(arr[j]>arr[j+1]) {
					int tmp= arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=tmp;
				}
			}
		}
		for(int i=0;i<n;i++) System.out.println(arr[i]);
	}

}

 

문제 16. 버블 소트 프로그램1 #

 

위 코드에서 n은 배열의 크기, a는 수가 들어 있는 배열이다. 수는 배열의 1 번 방부터 채운다.

위와 같은 코드를 실행시켰을 때 어떤 값이 출력되는지를 구하는 프로그램을 작성하시오.

 

bool change = false; 
for(int i = 1; i <= n + 1; i++) 
{
change = false;
for(int j = 1; j <= n - i; j++) { 
if(a[j] a[j + 1]) { 
change = true;
swap(a[j], a[j + 1]); 
}
}
if(change == false) {
cout « i « '\n'; 
break;
}
}

 

입력
1 번째 줄에 N이 주어진다. 비은 500,000보다 작거나 같은 자연수다. 2번째 줄부터 N개의 줄에 A[1]부
터 A[N]까지 1 개씩 주어진다. A에 들어 있는 수는 1,000,000보다 작거나 같은 자연수 또는 0이다.

 

출력
정답을 출력한다.

 

예제 입력

5 //배열의 크기
10
1
5
2
3

 

예제 출력

3

1단계. 문제 분석하기

-> 버블 정렬의 swap이 한 번도 일어나지 않은 루프를 찾는 문제

-> 버블 정렬의 이중 for문에서 안쪽 for문을 돌 때, swap이 일어나지 않았다면 모든 데이터가 정렬되어있다는 것을 이용

 

#안쪽 for문이 몇 번 수행됐는지 구하는 아이디어

 

: 안쪽 루프는 1에서 n-j까지 (즉, 왼쪽에서 오른쪽으로 이동하면서 swap을 수행)

-> 특정 데이터가 안쪽 루프에서 swap의 왼쪽으로 이동할 수 있는 최대 거리는 1

-> 데이터의 정렬 전 index와 정렬 후 index를 비교해 왼쪽으로 가장 많이 이동한 값을 찾아서 해결

 

 

2단계. 손으로 풀어 보기

  1. sort 함수로 배열을 정렬한다. [sort함수의 시간 복잡도는 O(nlogn)]
  2. 각 데이터마다 정렬 전 index 값에서 정렬 후 index값을 빼 최댓값을 찾는다.
  3. swap이 일어나지 않은 반복문이 한 번 더 실행되기 때문에 최댓값에 +1

 

3단계. 슈도코드  작성하기

N(데이터 개수) A(데이터 배열, 단 클래스를 데이터로 담는 배열)
for(N만큼 반복하기)
{ 
 A 배열 저장하기
}

A 배열 정렬하기
for(N만큼 반복하기)
{
 A[i]의 정렬 전 index - 정렬 후 index 계산의 최댓값을 찾아 저장하기
}
최댓값 +1을 정답으로 출력하기

별도 클래스 선언하기
mData(데이터 표현)
{
 index, value를 가지며
 value 기준 오름차순 정렬 함수 Comparable 구현하기
}

 

package sorting.ch04;

import java.util.Arrays;
import java.util.Scanner;

public class sorting01_q16 {
	static class mData implements Comparable<mData> {
		int index;
		int value;

		mData(int index, int value) {
			index = this.index;
			value = this.value;
		}

		@Override
		public int compareTo(mData o) {

			return o.value - this.value;
		}
	}

	public int solution(int n, mData[] arr) {

		Arrays.sort(arr);
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			max = Math.max(max, arr[i].index);
		}
		return max + 1;
	}

	public static void main(String[] args) {
		sorting01_q16 T = new sorting01_q16();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		mData[] arr = new mData[n];
		for (int i = 0; i < n; i++) {
			int index = i;
			int value = kb.nextInt();
			arr[i] = new mData(index, value);
		}

		System.out.println(T.solution(n, arr));

	}

}

-> 정렬 전 index와 정렬 후 index를 뺀 최댓값을 구하는 연산 구현 실패

 

 

package sorting.ch04;

import java.util.Arrays;
import java.util.Scanner;

public class sorting01_q16 {
	static class mData implements Comparable<mData> {
		int index;
		int value;

		mData(int index, int value) {
			this.index=index;
			this.value=value;
		}

		@Override
		public int compareTo(mData o) {

			return this.value - o.value;
		}
	}

	public int solution(int n, mData[] arr) {
		
		Arrays.sort(arr);
		int max = Integer.MIN_VALUE;
		for (int i = 0; i < n; i++) {
			if (max < arr[i].index - i)
				max = arr[i].index - i;

			// max = Math.max(max, arr[i].index - i);
		}
		return max + 1;
	}

	public static void main(String[] args) {
		sorting01_q16 T = new sorting01_q16();
		Scanner kb = new Scanner(System.in);

		int n = kb.nextInt();
		mData[] arr = new mData[n];
		for (int i = 0; i < n; i++) {
			int index = i;
			int value = kb.nextInt();
			arr[i] = new mData(index, value);

		}
		
		System.out.println(T.solution(n, arr));

	}

}

 

+) 세련된 풀이

package sorting.ch04;

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

public class sorting01_q16_sol2 {

	public static void main(String[] args) throws IOException {
		// Scanner kb = new Scanner(System.in);

		// Scanner 대신 BufferedReader 이용
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		int n = Integer.parseInt(reader.readLine());
		mData[] arr = new mData[n];

		for (int i = 0; i < n; i++) {
			arr[i] = new mData(Integer.parseInt(reader.readLine()), i);
		}

		Arrays.sort(arr);
		int max = 0;
		for (int i = 0; i < n; i++) {
			if (max < arr[i].index - i)
				max = arr[i].index - i;
			// max = Math.max(max, arr[i].index);
		}
		System.out.println(max + 1);

	}
}

class mData implements Comparable<mData> {
	int value;
	int index;

	public mData(int value, int index) {
		// super?
		super();
		this.value = value;
		this.index = index;

	}

	@Override
	public int compareTo(mData o) {
		return this.value - o.value;
		// value 기준 오름차순
	}
}
반응형
저작자표시 비영리

'Java > Java 알고리즘' 카테고리의 다른 글

[알고리즘] 1-2. 선택 정렬 #  (0) 2022.06.27
[알고리즘] 문제 풀이 순서 정리  (0) 2022.06.27
[알고리즘] 1. 정렬  (0) 2022.06.27
[알고리즘] 4-2. 클래스 이진트리  (0) 2022.03.03
[알고리즘] 4-1. 검색 트리  (0) 2022.03.03

'Java/Java 알고리즘' Related Articles

티스토리툴바