[Java] 배열 원소 중 최대값 구하기, 기본 정렬 알고리즘(선택, 버블, 삽입)_220726

최대값 구하기

class Max {
	public static void main(String[] args) {
		int[] arr = { 3, 2, 1, 5, 1 };
        // 최대값 초기값 세팅
        int max = arr[0];
        // 최대값 구하기
            for (int num : arr) {
            if (num > max) {
            max = num;
            }
        }         
        // 최대값 출력        
        System.out.println(max);
    }
}

---

기본 정렬 알고리즘

 

int [] array;

new int { 3, 5, 1, 2, 4 };

 

위 배열의 크기를 아래와 같이 오름차순으로 정리하고 싶은 경우 선택, 버블, 삽입정렬을 사용할 수 있다.

{ 3, 5, 1, 2, 4 } -> { 1, 2, 3, 4, 5 }

 

선택 정렬 (Selection Sort)

선택 정렬은 가장 작은 수를 찾아서 앞으로 보내는 행동을 계속하는 것

 

정렬 방법:

1. 배열의 처음부터 끝까지 반복문을 통해 돌면서 가장 작은 수를 찾는다.

2.  가장 작은 수를 배열의 맨 앞으로 보낸다.

3.  그 다음 배열부터 끝까지 또 작은 수를 찾아 맨 앞으로 보내고, 배열이 끝날 때까지 위의 행위를 계속해서 정렬한다.

:선택 정렬의 시간 복잡도는 배열의 길이 n을 n회 2중 반복문을 돌아야 하기 때문에 n^2, O(n^2)

 

출처: https://kim-oriental.tistory.com/15

선택정렬

 

import java.util.Arrays;

public class selectionSort {
	public static void main(String[] args) {
		int[] a = { 3, 5, 1, 2, 4 };
		int tempValue, tempJ = 0;
		for (int i = 0; i < a.length; i++) {  // 배열 처음부터 끝까지 반복 (i는 현재 위치)
			int min = Integer.MAX_VALUE;  // 제일 작은 수를 찾기 위해, min은 int의 최대 값으로 임시 세팅
			for (int j = i; j < a.length; j++) {
				if (a[j] < min) {  // 현재 위치부터 배열 마지막까지 반복문 돌면서 최소 값을 계속 찾음
					min = a[j];
					tempJ = j;
				}
			}
			tempValue = a[i]; // 찾은 최소값과 현재 위치의 값과 서로 바꿈
			a[i] = a[tempJ];
			a[tempJ] = tempValue;
		}
		System.out.println(Arrays.toString(a));
	}
}

출처: https://kim-oriental.tistory.com/15

기본 정렬 알고리즘 - 선택정렬, 버블 정렬, 삽입 정렬

 

 

 

2. 버블 정렬 (Bubble Sort)

버블정렬은 오름차순 정렬의 경우, 바로 오른쪽 옆에 있는 숫자와 크기를 비교해서 그 숫자가 크기가 작으면 서로 자리를 바꿔주면서 정렬 // 자주 사용하지는 않으나 쉬움;

 

정렬 방법:

1. 맨 처음 반복에서 가장 큰 수를 가장 오른쪽으로 보낸다.

2. 다시 배열 시작부터 배열의 크기 - 1, n-1까지 다시 반복을 돌면서 옆의 수와 비교하면서 정렬을 계속한다.

3. 그다음 작은 수는 그다음 오른쪽에 놓인다.

4. 이런 식으로 계속 반복을 돌게 되면서 정렬한다.

: 버블 정렬의 시간 복잡도 역시 배열의 길이 n을 n회 2중 반복문을 돌아야 하기 때문에 n^2, O(n^2)

버블정렬

 

import java.util.Arrays;

public class bubbleSort {
	public static void main(String[] args) {
		int[] a = { 3, 5, 1, 2, 4 };
		int tempValue;
		for (int i = 0; i < a.length; i++) {
			for (int j = 0; j < a.length - i - 1; j++) { // 0 ~ n, 0 ~ n-1 번 반복를 돌면서 바로 옆 숫자릴 비교
				if (a[j] > a[j + 1]) {  // 바로 오른쪽 숫자와 비교하여 크기가 클 경우, 서로 위치를 바꿈
					tempValue = a[j];
					a[j] = a[j + 1];
					a[j + 1] = tempValue;
				}
			}
		}
		System.out.println(Arrays.toString(a));
	}
}

 

3. 삽입 정렬 (Insertion Sort)

삽입 정렬은 숫자를 한 개 선택하고 선택된 숫자를 적절한 위치에 삽입하는 정렬 방법

 

정렬 방법:

1. 오름차순의 경우, 배열의 왼쪽에서 두 번째 숫자( 배열[1] )를 제일 먼저 선택한 후, 선택된 숫자의 왼쪽 숫자의 크기를 비교해서 숫자가 더 작다면 서로 위치를 바꿔준다.

2. 한 칸 오른쪽 숫자를 선택한 후에 왼쪽 숫자들을 비교해서 정렬을 하게 되는데, 왼쪽 숫자들은 정렬이 되어 있는 상태이기 때문에 바로 왼쪽 옆 숫자 한 개씩 비교하면서 선택된 숫자보다 작은 숫자가 나올 때까지만 이동한다.

3. 나보다 작은 숫자를 찾으면 그 오른쪽 옆으로 삽입을 하는 식으로 모든 숫자를 다 선택해서 삽입할 때까지 동작한다.

: 시간 복잡도는 배열의 상태에 따라 모두 숫자를 비교를 하고 위치를 바꿔야 할 Worst Case의 경우 n^2이 되고, Best Case의 경우 n번 만으로도 정렬이 가능;

다만 시간 복잡도는 최악의 경우를 표기하기에 O(n^2);

삽입 정렬

 

import java.util.Arrays;

public class insertionSort {

	public static void main(String[] args) {
		int[] a = { 3, 5, 1, 2, 4 };
		int tempValue, target;
		for (int i = 1; i < a.length; i++) {
			tempValue = a[i]; // 선택된 숫자를 임시 저장
			target = i - 1;  // 비교 대상의 위치
			while (target >= 0 && a[target] > tempValue) { // 왼쪽 끝까지 가거나, 자신보다 작은 수를 만나기 전까지 이동하면 삽입될 위치를 찾음
				a[target + 1] = a[target]; // 나보다 큰 수는 오른쪽으로 한칸 이동
				target--; // 그 다음 비교대상을 왼쪽으로 한 칸 이동
			}
			a[target + 1] = tempValue;  // 적정한 위치를 찾아 선택된 숫자를 삽입
		}
		System.out.println(Arrays.toString(a));
	}
}