📢 버블 정렬
: 데이터의 인접 요소끼리 비교하고, swap 연산을 수행하여 정렬
문제 1. 백준 2750번 수 정렬하기1
🔎 접근법
두가지 방법을 이용해봤어욤
1. sort() 해서 정렬하기
2. temp를 이용한 정렬
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class bubbleArray1 {
public static void main(String[] args) throws IOException {
/* 백준 2750번 수 정렬하기1 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int count = Integer.parseInt(br.readLine());
int[] nums = new int[count];
for(int i = 0; i < count; i++) {
nums[i] = Integer.parseInt(br.readLine());
}
// 방법 1 sort() 사용
/* Arrays.sort(nums); */
// 방법 2 버블 정렬
for(int i = 0; i < count - 1; i++) {
for(int j = 0; j < count - 1; j++) {
if(nums[j] > nums[j+1]) {
int temp = nums[j];
nums[j] = nums[j+1];
nums[j+1] = temp;
}
}
}
for(int i = 0; i < count; i++) {
System.out.println(nums[i]);
}
}
}
문제2. 백준 1377번 버블 소트
🔎 접근법
1. swap이 언제 끝났는지 알기 위해선 원소의 최대 이동 횟수를 구해야 함
2. 이동한 인덱스 차이를 구해야 함니도
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
public class main {
public static void main(String[] args) throws IOException {
/* 백준 1377번 버블 소트 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine());
mData[] a = new mData[size];
for(int i = 0; i < size; i++) {
a[i] = new mData(Integer.parseInt(br.readLine()),i);
}
Arrays.sort(a);
int max = 0;
for(int i = 0; i < size; i++) {
if(max < a[i].index - i) { // a[i].index - i의 의미 = 원소가 이동한 인덱스 범위
max = a[i].index - i;
}
}
System.out.println(max + 1);
}
}
class mData implements Comparable<mData> { // sort() 함수 실행하기 위한 정렬기준 정하기 위해 구현
int value;
int index;
public mData(int value, int index) {
this.value = value;
this.index = index;
}
/* compareTo 메서드는 두 객체를 비교하여 정렬 순서를 정의
* 음수, 양수, 0으로 반환한다 즉, 첫번째 객체가 두번째 객체보다 작은지 큰지 비교 */
@Override
public int compareTo(mData o) {
return this.value - o.value;
}
}📢 선택 정렬
: 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법
문제 1. 백준 1427번 내림차순으로 자릿수 정렬하기
🔎 접근법
- 값을 입력받을 때 공백 없이 받으니까 구분해 줘야 함
-> String으로 받은 뒤, substring 실행
import java.util.Arrays;
import java.util.Scanner;
public class main {
public static void main(String[] args) {
/* 백준 1427번 내림차순으로 자릿수 정렬하기 */
// 1. 입력받아서 나누기
Scanner scan = new Scanner(System.in);
String str = scan.next();
int [] nums = new int[str.length()];
for(int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(str.substring(i, i + 1));
}
// 2. 정렬하기
// [방법 1] sort() 사용
/* Arrays.parallelSort(nums); */
// [방법 2] 삽입정렬 사용
for(int i = 0; i < nums.length; i++) {
int max = i;
for(int j = i + 1; j < nums.length; j++) {
if(nums[j] > nums[max]) {
max = j;
}
}
if(nums[max] > nums[i]) {
int temp = nums[i];
nums[i] = nums[max];
nums[max] = temp;
}
}
for(int i = 0; i < nums.length; i++) {
System.out.print(nums[i]);
}
}
}
📢 삽입 정렬
: 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입시켜 정렬하는 방식
: 평균 시간 복잡도는 O(N^2)로 느린편
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
/* 백준 11399번 ATM 인출 시간 계산하기 */
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int size = Integer.parseInt(br.readLine()); // 크기
int [] n = new int[size]; // 배열
int [] s = new int[size]; // 합 배열
StringTokenizer line = new StringTokenizer(br.readLine());
for(int i = 0; i < size; i++) {
n[i] = Integer.parseInt(line.nextToken());
}
// 삽입 정렬
for(int i = 1; i < size; i++) {
int insertPoint = i;
int insertValue = n[i];
for(int j = i-1; j >= 0; j--) {
if(n[j] < n[i]) {
insertPoint = j + 1;
break;
}
if(j == 0) {
insertPoint = 0;
}
}
// 오른쪽으로 밀기
for(int j = i; j > insertPoint; j--) {
n[j] = n[j-1];
}
// 삽입
n[insertPoint] = insertValue;
}
s[0] = n[0];
// 합배열
int sum = s[0];
for(int i = 1; i < size; i ++) {
s[i] = s[i-1] + n[i];
sum += s[i];
}
System.out.println(sum);
}
}
~*