1. 정렬
여러 개의 데이터를 일정한 기준에 따라 순서대로 배치하는 것
2. 삽입 정렬
배열의 요소를 하나씩 선택한 뒤, 그 요소가 들어갈 알맞은 위치를 찾아 삽입하는 방식
2-1 코드
public static void insertionSort(int[] a) {
// i = 1부터 시작하는 이유:
// 0번째 요소는 앞에 비교할 값이 없으므로
// 일단 정렬된 상태라고 본다.
for(int i = 1; i < a.length; i++) {
int j;
// 현재 삽입할 값
// 예: a[i] 값을 앞쪽의 알맞은 위치에 넣을 예정
int tmp = a[i];
// j는 현재 선택한 위치 i부터 시작
// j > 0 : 배열의 맨 앞을 넘지 않도록 하는 조건
// a[j - 1] > tmp : 앞쪽 값이 tmp보다 크면 뒤로 밀어야 함
for(j = i; j > 0 && a[j - 1] > tmp; j--) {
// 앞쪽 값이 tmp보다 크므로 한 칸 뒤로 이동
a[j] = a[j - 1];
}
// 반복문이 끝난 위치 j가 tmp가 들어갈 자리
a[j] = tmp;
}
}tmp는 현재 선택된 값
앞쪽 값들이 tmp보다 크면 한칸씩 뒤로 밀고, 알맞은 자리에 tmp를 삽입
2-2 순서
하나를 선택한다.
↓
앞쪽 데이터들과 비교한다.
↓
큰 값들을 뒤로 민다.
↓
알맞은 위치에 삽입한다.
3. 선택 정렬
정렬되지 않은 부분에서 가장 작은 값을 찾아 맨 앞으로 보내는 방식
3-1 코드
public static void selectionSort(int[] a) {
// i는 현재 정렬할 위치
// 마지막 요소는 자동으로 정렬되므로 a.length - 1까지만 반복
for(int i = 0; i < a.length - 1; i++) {
// min은 가장 작은 값의 인덱스를 저장하는 변수
// 처음에는 현재 위치 i를 최솟값 위치라고 가정
int min = i;
// i 다음 위치부터 배열 끝까지 비교
// 정렬되지 않은 부분에서 최솟값 찾기
for(int j = i + 1; j < a.length; j++) {
// 현재 j 위치의 값이 min 위치의 값보다 작다면
if(a[j] < a[min]) {
// 최솟값 위치를 j로 변경
min = j;
}
}
// 최솟값을 찾았으므로
// 현재 위치 i와 최솟값 위치 min을 교환
int tmp = a[i];
a[i] = a[min];
a[min] = tmp;
}
}3-2 순서
정렬되지 않은 부분에서 최솟값을 찾는다.
↓
최솟값을 맨 앞으로 보낸다.
↓
다음 위치에서 다시 반복한다.
4. 퀵 정렬
기준 값을 하나 정한 뒤, 그 기준값보다 작은 값은 왼쪽, 큰 값을 오른쪽으로 나누면서 정렬하는 방식
이때 기준 값은 피벗이라고 한다
4-1 코드
public static void quickSort(int[] a, int left, int right) {
// 왼쪽에서 오른쪽으로 이동할 커서
int lc = left;
// 오른쪽에서 왼쪽으로 이동할 커서
int rc = right;
// 피벗 선택
// 여기서는 정렬 범위의 가운데 값을 피벗으로 사용
int x = a[(lc + rc) / 2];
do {
// 왼쪽 커서는 피벗보다 작은 값을 만나면 계속 오른쪽으로 이동
// 피벗보다 크거나 같은 값을 만나면 멈춤
while(a[lc] < x) {
lc++;
}
// 오른쪽 커서는 피벗보다 큰 값을 만나면 계속 왼쪽으로 이동
// 피벗보다 작거나 같은 값을 만나면 멈춤
while(a[rc] > x) {
rc--;
}
// lc가 rc보다 왼쪽에 있거나 같은 위치라면 교환 가능
if(lc <= rc) {
// 왼쪽에서 찾은 큰 값과
// 오른쪽에서 찾은 작은 값을 교환
int tmp = a[lc];
a[lc] = a[rc];
a[rc] = tmp;
// 교환 후 커서를 한 칸씩 이동
lc++;
rc--;
}
// 왼쪽 커서와 오른쪽 커서가 엇갈릴 때까지 반복
} while(lc <= rc);
// 왼쪽 부분에 아직 정렬할 값이 남아 있으면 다시 퀵 정렬
if(left < rc) {
quickSort(a, left, rc);
}
// 오른쪽 부분에 아직 정렬할 값이 남아 있으면 다시 퀵 정렬
if(right > lc) {
quickSort(a, lc, right);
}
}4-2 변수 의미
변수의미
| 변수 | 의미 |
| left | 정렬할 범위의 시작 인덱스 |
| right | 정렬할 범위의 끝 인덱스 |
| lc | 왼쪽에서 오른쪽으로 이동하는 커서 |
| rc | 오른쪽에서 왼쪽으로 이동하는 커서 |
| x | 피벗 값 |
4-3 순서
피벗을 정한다.
↓
피벗보다 작은 값은 왼쪽으로 보낸다.
↓
피벗보다 큰 값은 오른쪽으로 보낸다.
↓
나뉜 왼쪽/오른쪽을 다시 정렬한다.
5. 병합 정렬
배열을 계속 반으로 나눈 뒤, 작은 단위부터 정렬하면서 다시 합치는 정렬
5-1 코드
// 병합할 때 임시로 값을 저장할 배열
// 왼쪽 배열 값을 잠시 보관하는 용도로 사용
static int[] buff;
public static void mergeSort(int[] a) {
// 원본 배열과 같은 크기의 임시 배열 생성
buff = new int[a.length];
// 배열 전체 범위를 정렬
// 시작 인덱스: 0
// 끝 인덱스: a.length - 1
mSort(a, 0, a.length - 1);
}
public static void mSort(int[] a, int left, int right) {
// left가 right보다 작을 때만 나눌 수 있음
// 예: left == right 이면 요소가 1개라 더 이상 나눌 필요 없음
if(left < right) {
// 배열을 반으로 나누기 위한 가운데 인덱스
int center = (left + right) / 2;
// buff 배열의 인덱스
int p = 0;
// buff 배열을 읽을 때 사용할 인덱스
int j = 0;
// 원본 배열 a에 다시 값을 넣을 위치
int k = left;
// 왼쪽 부분 정렬
mSort(a, left, center);
// 오른쪽 부분 정렬
mSort(a, center + 1, right);
// 왼쪽 부분 배열을 buff에 복사
// 예: a[left] ~ a[center] 값을 buff에 저장
for(int i = left; i <= center; i++) {
buff[p++] = a[i];
}
// 오른쪽 부분의 시작 위치
int i = center + 1;
// buff에 저장된 왼쪽 부분과
// a 배열의 오른쪽 부분을 비교하면서 작은 값을 a에 넣음
while(i <= right && j < p) {
// buff[j] <= a[i] 이면 buff[j]를 a[k]에 넣고 j 증가
// 아니면 a[i]를 a[k]에 넣고 i 증가
a[k++] = (buff[j] <= a[i]) ? buff[j++] : a[i++];
}
// 오른쪽 부분은 이미 a 배열 안에 남아 있으므로
// buff에 남은 값만 원본 배열 a에 복사하면 됨
while(j < p) {
a[k++] = buff[j++];
}
}
}
5-2 흐름
배열을 반으로 나눈다.
↓
왼쪽을 정렬한다.
↓
오른쪽을 정렬한다.
↓
두 부분을 작은 값부터 다시 합친다.
6. 버블 정렬
옆에 있는 두 값을 비교해서 순서가 틀리면 바꾸는 정렬
6-1-1 코드
public static void bubbleSort(int[] a) {
// 배열 전체를 여러 번 반복
// 한 번 반복할 때마다 작은 값이 앞쪽으로 이동
for(int i = 0; i < a.length - 1; i++) {
// 교환 횟수 저장 변수
// 한 번도 교환이 없으면 이미 정렬된 상태라고 판단 가능
int cnt = 0;
// 뒤쪽에서 앞쪽 방향으로 인접한 두 값 비교
// j는 배열의 마지막 인덱스부터 시작
for(int j = a.length - 1; j > i; j--) {
// 앞 값이 뒤 값보다 크면 순서가 잘못된 상태
if(a[j - 1] > a[j]) {
// 두 값 교환
int tmp = a[j - 1];
a[j - 1] = a[j];
a[j] = tmp;
// 교환이 일어났으므로 cnt 증가
cnt++;
}
}
// 이번 반복에서 한 번도 교환이 없었다면
// 이미 정렬이 끝난 상태이므로 반복 종료
if(cnt == 0) {
break;
}
}
}6-1-2 코드
public static void bubbleSort2(int[] a) {
// 앞에서부터 인접한 요소 두 개를 비교해가며 정렬
// 한 번 반복할 때마다 가장 큰 값이 오른쪽으로 이동
for(int i = 0; i < a.length - 1; i++) {
// 교환 횟수 저장 변수
int cnt = 0;
// 앞에서부터 인접한 두 값 비교
// a[j]와 a[j + 1]을 비교
for(int j = i; j < a.length - 1 - i; j++) {
// 앞 값이 뒤 값보다 크면 교환
if(a[j] > a[j + 1]) {
// 두 값 교환
int tmp = a[j + 1];
a[j + 1] = a[j];
a[j] = tmp;
// 교환 횟수 증가
cnt++;
}
}
// 교환이 한 번도 없으면 이미 정렬된 상태
if(cnt == 0) {
break;
}
}
}6-2 흐름
앞에서부터 두 개씩 비교한다.
↓
앞 값이 더 크면 바꾼다.
↓
큰 값이 점점 오른쪽으로 이동한다.
↓
반복하면서 정렬된다.
7. 이진탐색트리
데이터를 크기 기준으로 왼쪽 / 오른쪽에 나누어 저장하는 자료구조
현재 노드보다 작은 값 → 왼쪽
현재 노드보다 큰 값 → 오른쪽
7-1 Node 클래스
트리에서 데이터 하나를 저장하는 단위를 노드(Node)라고 한다
class Node<K, V> {
private K key; // 비교 기준이 되는 값
private V data; // 실제 저장할 데이터
private Node<K,V> left; // 왼쪽 자식 노드
private Node<K,V> right;// 오른쪽 자식 노드
}
| 이름 | 뜻 |
| key | 비교 기준이 되는 값 |
| data | 실제로 저장할 데이터 |
| left | 왼쪽 자식 노드 |
| right | 오른쪽 자식 노드 |
7-2 K, V 제네릭
public class BinarySearchTree<K,V>K = key의 자료형
V = data의 자료형
V = data의 자료형
BinarySearchTree<Integer, Data> tree = new BinarySearchTree<Integer, Data>();
key는 Integer 타입
data는 Data 타입
7-3 root
private Node<K,V> root;root는 트리의 시작 노드
트리는 검색, 추가할 때 항상 root부터 시작
7-4 key 비교
int cond = com(key, n.getKey());
비교 결과에 따라 왼쪽으로 갈지, 오른쪽으로 갈지 결정
| 결과 | 의미 | 이동 방향 |
| 음수 | 찾는 key가 현재 key보다 작음 | 왼쪽 |
| 0 | key가 같음 | 찾음 |
| 양수 | 찾는 key가 현재 key보다 큼 | 오른쪽 |
7-5 검색 search()
검색은 원하는 key를 가진 데이터를 찾는 기능
흐름
root부터 시작
↓
찾는 key와 현재 노드 key 비교
↓
같으면 데이터 반환
↓
작으면 왼쪽 이동
↓
크면 오른쪽 이동
↓
끝까지 못 찾으면 null 반환
Node<K,V> n = root;
while(true) {
if(n == null) {
return null;
}
int cond = com(key, n.getKey());
if(cond == 0) {
return n.getValue();
} else if(cond < 0) {
n = n.left;
} else {
n = n.right;
}
}root부터 시작해서 key를 비교하고, 작으면 왼쪽 노드, 크면 오른쪽 노드로 이동
key와 같으면 해당 노드의 data를 반환
7-6 추가 add()
노드 추가 시 규칙
작으면 왼쪽
크면 오른쪽
if(root==null) {
root = new Node<K,V>(key,data,null,null);
}else {
addNode(root,key,data);
}root가 있다면 addNode()를 이용해 들어갈 위치를 찾음
흐름
추가할 key와 현재 노드 key 비교
↓
같으면 추가하지 않음
↓
작으면 왼쪽으로 이동
↓
크면 오른쪽으로 이동
↓
비어 있는 위치를 찾으면 새 노드 추가
7-7 출력 print()
출력 순서
왼쪽 출력
↓
현재 노드 출력
↓
오른쪽 출력
private void printSubTree(Node node) {
if(node != null) {
printSubTree(node.left);
System.out.println(node.key + " " + node.data);
printSubTree(node.right);
}
}7-8 삭제 remove()
1. 왼쪽 자식이 없는 경우
2. 오른쪽 자식이 없는 경우
3. 자식이 2개 있는 경우
7-8-1 삭제할 노드 찾기
Node<K,V> p = root;
Node<K,V> parent = null;
boolean isLeftChild = true;
| 변수 | 의미 |
| p | 현재 확인 중인 노드 |
| parent | 현재 노드의 부모 노드 |
| isLeftChild | 현재 노드가 부모의 왼쪽 자식인지 확인 |
7-8-2 왼쪽 자식이 없는 경우
삭제할 노드의 왼쪽 자식이 없다면, 삭제할 노드 대신 오른쪽 자식을 연결
if(p.left == null) {
parent.left = p.right;
}7-8-3 오른쪽 자식이 없는 경우
삭제할 노드의 오른쪽 자식이 없다면, 삭제할 노드 대신 왼쪽 자식을 연결
else if(p.right == null) {
parent.left = p.left;
}7-8-4 자식이 2개 있는 경우
Node<K,V> left = p.left;
while(left.right != null) {
parent = left;
left = left.right;
}
p.key = left.key;
p.data = left.data;왼쪽 서브트리에서 가장 오른쪽으로 계속 이동하면 가장 큰 값을 찾을 수 있다.
그 값을 삭제할 노드에 덮어써서 트리 규칙을 유지
| 개념 | 설명 |
| Tree | 나무처럼 가지가 뻗는 자료구조 |
| Node | 데이터 하나를 저장하는 단위 |
| root | 트리의 시작 노드 |
| key | 비교 기준 |
| data | 실제 저장할 값 |
| left | 현재 key보다 작은 값이 연결되는 방향 |
| right | 현재 key보다 큰 값이 연결되는 방향 |
| search | key를 비교하며 데이터 찾기 |
| add | 규칙에 맞는 위치에 노드 추가 |
| remove | 규칙이 깨지지 않게 노드 삭제 |
| 중위 순회 | 왼쪽 → 현재 → 오른쪽 순서로 출력 |
'FullStack Study > 9주차' 카테고리의 다른 글
| JAVA 풀스택 40일차 - Algorithm (재귀함수 / 이중연결리스트 / 스택,큐) (0) | 2026.05.22 |
|---|---|
| JAVA 풀스택 39일차 - JDBC (MVC 패턴) (0) | 2026.05.21 |
| JAVA 풀스택 38일차 - JDBC (MVC 패턴) (0) | 2026.05.20 |
| JAVA 풀스택 37일차 - JDBC2 (0) | 2026.05.19 |