1. 알고리즘이란?
https://why-dev.tistory.com/6?category=917883
2. 정렬
- 정의 : 이름,학번,키 등 핵심항목(key)의 대소관계에 따라 순서대로 값을 나열하는 것
- 안정성 : 키값이 같은 요소의 순서가 정렬 후에도 유지되는 것
(ex. 같은 점수를 지닌 두 학생에 대해 학번으로 순번을 지정)
- 내부 정렬과 외부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 내부 정렬을 사용한다.
- 정렬의 속도 비교 :
3. 버블정렬, 선택정렬, 삽입정렬
- Big O는 셋 다 n^2이지만, 속도는 다르다. - (정렬이 안 된 자료들을 정렬할때) 버블정렬 보다는 선택정렬이 교환횟수가 적어서 상대적으로 더 빠르다. - (이미 정렬이 어느 정도 된 경우) 삽입정렬을 쓰는 것이 좋다 |
1) 버블정렬
원리 ) 안쪽에서 두개의 값을 비교한다
--> 한 줄 비교가 다 끝나면 마지막 값이 가장 큰 값(또는 가장 작은 값)
--> 안 쪽은 n-1-i 만큼 두개씩 비교 & swap하면 된다.
바깥쪽에서 이 과정을 n-1만큼 반복한다.
[코드]
package _02_정렬;
import java.util.Arrays;
public class _04_BubbleSort {
public static void main(String[] args) {
int[] arr = new int[10];
random(arr);
System.out.println(Arrays.toString(arr));
//오름차순 버블 정렬을 구현하라
int tmp;
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
System.out.println(Arrays.toString(arr));
//내림차순 버블 정렬을 구현하라
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j < arr.length-1-i; j++) {
if (arr[j] < arr[j+1]) {
tmp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = tmp;
}
}
}
System.out.println(Arrays.toString(arr));
}
public static int[] random(int[] arr) {
OUTER :
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random()*10)+1;
for (int j = 0; j < i; j++) {
if (arr[j] == arr[i]) {
i--;
continue OUTER;
}
}
}
return arr;
}
}
>> 결과
[10, 3, 8, 9, 4, 1, 7, 5, 2, 6]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
2) 선택정렬
원리 ) i index를 min(or max)으로 지정하고, 나머지 값들을 하나씩 비교한 뒤, 교환한다.
[코드]
package _02_정렬;
import java.util.Arrays;
public class _05_SelectionSort {
public static void main(String[] args) {
int[] arr = new int[10];
random(arr);
System.out.println(Arrays.toString(arr));
//오름차순 선택정렬을 구현하라
int min, tmp;
for (int i = 0; i < arr.length-1; i++) {
min = i; // 하나의 요소를 min으로 선택(이 값보다 작은 값을 찾는다)
for (int j = i+1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
//i위치값과 min값을 swap
tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
System.out.println(Arrays.toString(arr));
//내림차순 선택정렬을 구현하라
int max;
for (int i = 0; i < arr.length-1; i++) {
max = i;
for (int j = i+1; j < arr.length; j++) {
if (arr[j] > arr[max]) {
max = j;
}
}
//i위치값과 max값을 swap
tmp = arr[i];
arr[i] = arr[max];
arr[max] = tmp;
}
System.out.println(Arrays.toString(arr));
}
public static int[] random(int[] arr) {
OUTER :
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random()*10)+1;
for (int j = 0; j < i; j++) {
if (arr[j] == arr[i]) {
i--;
continue OUTER;
}
}
}
return arr;
}
}
>> 결과
[2, 9, 8, 5, 10, 1, 6, 4, 3, 7]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
3) 삽입 정렬 (Insertion Sort)
- 거의 다 정렬된 상태의 데이터를 다시 정렬할 때, 가장 효과적인 알고리즘 (위 정렬 속도 비교 확인)
- 원리 : 아직 정렬되지 않은 부분의 첫번째 요소를 정렬한 부분의 알맞은 위치에 삽입한다.
- 장점 : 정렬이 되었거나 또는 그 상태에 가까우면 정렬 속도가 아주 빠름
- 단점 : 삽입할 곳이 멀리 떨어지면 이동(대입)하는 횟수가 많다
(ex. 0~10까지 중 0제외 나머지는 정렬된 상태이나, 0값이 인덱스의 끝에 위치)
[코드]
package _02_정렬;
import java.util.Arrays;
public class _02_InsertionSort {
public static void main(String[] args) {
int[] arr = new int[10];
random(arr);
System.out.println(Arrays.toString(arr));
//오름차순 삽입정렬을 구현하라
int tmp;
for (int i = 1; i < arr.length; i++) {
tmp = arr[i];
int j;
for (j = i; j > 0 && arr[j-1] > tmp; j--) {
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
System.out.println(Arrays.toString(arr));
//내림차순 삽입정렬을 구현하라
for (int i = 1; i < arr.length; i++) {
tmp = arr[i];
int j;
for (j = i; j > 0 && arr[j-1] < tmp; j--) {
arr[j] = arr[j-1];
}
arr[j] = tmp;
}
System.out.println(Arrays.toString(arr));
}
public static int[] random(int[] arr) {
OUTER :
for (int i = 0; i < arr.length; i++) {
arr[i] = (int)(Math.random()*10)+1;
for (int j = 0; j < i; j++) {
if (arr[j] == arr[i]) {
i--;
continue OUTER;
}
}
}
return arr;
}
}
>> 결과
[3, 1, 6, 4, 10, 2, 5, 7, 9, 8]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
4. 셸 정렬 (Shell Sort)
[ 출처 ]
- 자바의 정석, 남궁성
- Do it! 자료구조와 함께 배우는 알고리즘 입문 [자바편], bogyoh shibata지음
- 기타 : 유투브
'자료구조, 알고리즘 > 알고리즘' 카테고리의 다른 글
[자료구조] 스택 (0) | 2022.04.18 |
---|---|
[검색] 선형탐색과 이진탐색 (0) | 2022.04.12 |
[자바의 정석] 스택과 큐 (0) | 2022.03.30 |
[자바의 정석] ArrayList/LinkedList (0) | 2022.03.29 |
[자바의 정석] 컬렉션 프레임웍(Collection Framework) 기초 (0) | 2022.03.29 |