: 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음으로 작은 데이터를 선택해 앞에서 두 번째 데이터와 바꾸는 과정 반복. *GIF
void selectionSort(int[] arr) {
int indexMin, temp;
for (int i = 0; i < arr.length-1; i++) { // 1.
indexMin = i; // 가장 작은 데이터의 인덱스
for (int j = i + 1; j < arr.length; j++) { // 2.
if (arr[j] < arr[indexMin]) { // 3.
indexMin = j;
}
}
// 4. swap(arr[indexMin], arr[i])
temp = arr[indexMin];
arr[indexMin] = arr[i];
arr[i] = temp;
}
System.out.println(Arrays.toString(arr));
}
: 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬 *GIF
void insertionSort(int[] arr)
{
for(int index = 1 ; index < arr.length ; index++){ // 1.
int temp = arr[index];
int prev = index - 1;
while( (prev >= 0) && (arr[prev] > temp) ) { // 2.
arr[prev+1] = arr[prev];
prev--;
}
arr[prev + 1] = temp; // 3.
}
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int start, int end) {
if (start >= end) return; // 원소가 1개인 경우 종료
int pivot = start; // 피벗은 첫 번째 원소
int left = start + 1;
int right = end;
while (left <= right) {
// 왼족에서 부터 피벗보다 큰 데이터를 찾을 때까지 반복
while (left <= end && arr[left] <= arr[pivot]) left++;
// 오른쪽에서 부터 피벗보다 작은 데이터를 찾을 때까지 반복
while (right > start && arr[right] >= arr[pivot]) right--;
// 엇갈렸다면 작은 데이터와 피벗을 교체
if (left > right) {
int temp = arr[pivot];
arr[pivot] = arr[right];
arr[right] = temp;
}
// 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
else {
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
}
// 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
quickSort(arr, start, right - 1);
quickSort(arr, right + 1, end);
}
public static void main(String[] args) {
int n = 10;
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
quickSort(arr, 0, n - 1);
for(int i = 0; i < n; i++) {
System.out.print(arr[i] + " ");
}
}
: 배열의 값과 동일한 인덱스에 갯수를 누적하여 오름차순 정렬
import java.util.*;
public class Main {
// 0부터 9까지의 원소로 이뤄진 배열
public static final int MAX_VALUE = 9;
public static void main(String[] args) {
int n = 15;
// 모든 원소의 값이 0보다 크거나 같다고 가정
int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2};
// 최대 인덱스가 정렬하려는 배열의 최댓값과 동일하도록 배열 선언(모든 값은 0으로 초기화)
int[] cnt = new int[MAX_VALUE + 1];
for (int i = 0; i < n; i++) {
cnt[arr[i]] += 1; // 각 데이터에 해당하는 인덱스의 값 증가
}
for (int i = 0; i <= MAX_VALUE; i++) { // 배열에 기록된 정렬 정보 확인
for (int j = 0; j < cnt[i]; j++) {
System.out.print(i + " "); // 띄어쓰기를 기준으로 등장한 횟수만큼 인덱스 출력
}
}
}
}
: 'implements Comparable' 함으로써 Collections.sort(클래스 객체)했을 때 원하는 기준으로 정렬됨
import java.util.*;
class Fruit implements Comparable<Fruit>{
private String name;
private int score;
public Fruit(String name, int score) {
this.name = name;
this.score = score;
}
public String getName() {
return this.name;
}
public int getScore() {
return this.score;
}
// 정렬 기준 : 오름차순
@Override
public int compareTo(Fruit o) {
if(this.score < o.score) return -1;
return 1;
}
}
public class Java0713_4 {
public static void main(String[] args) {
List<Fruit> fruits = new ArrayList<>();
fruits.add(new Fruit("바나나",2));
fruits.add(new Fruit("사과",5));
fruits.add(new Fruit("당근",3));
Collections.sort(fruits); // Fruit에서 오버라이드한 내둉대로 정렬
for(int i=0; i<fruits.size();i++) {
System.out.print("(" + fruits.get(i).getName() + "," + fruits.get(i).getScore()+ ") ");
}
}
}
// 결과 : [('바나나',2),('당근',3),('사과',5)]
import java.util.*;
// 큐에 좌표를 쉽게 저장하고, 접근하기 위해 클래스 생성!
class Node{
private int y;
private int x;
public Node(int y,int x) {
this.y= y;
this.x= x;
}
public int getX() {
return this.x;
}
public int getY() {
return this.y;
}
}
public class Java0713_3 {
public static int n,m;
public static int[][] arr;
public static int[][] d= {{-1,0},{1,0},{0,-1},{0,1}};
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
sc.nextLine();
for(int i=0;i<n;i++) {
String str = sc.nextLine();
for(int j=0;j<m;j++) {
arr[i][j]=str.charAt(j) - '0';
}
}
System.out.print(bfs(0,0));
}
public static int bfs(int y, int x) {
Queue<Node> q = new LinkedList<>();
q.offer(new Node(y,x));
while(!q.isEmpty()) {
Node node = q.poll();
y = node.getY();
x = node.getX();
// 현재 위치에서 상하좌우 좌표 확인
for(int[] dir:d) {
int ny = y+ dir[0];
int nx = x+dir[1];
if(ny<0||ny>=n||nx<0||nx>=m) continue;
if(arr[ny][nx] == 0) continue;
// 해당좌표를 처음 방문하는 경우에만
if(arr[ny][nx]==1) {
arr[ny][nx] = arr[y][x]+1;
// 현재좌표에 이전좌표까지의 최단거리+1 저장
q.offer(new Node(ny,nx));
}
}
}
// 가장 오른쪽 아래까지의 최단거리 반환
return arr[n-1][m-1];
}
}