728x90
들어가기 전
예를 들어 선택 정렬의 로직을 배우고 "선택"이라는 이름과 로직이 매칭이 잘 안 되었다.
그러다 보니까, 로직을 강제로 암기를 하게 되고 시간이 지나면 까먹는 문제가 생긴다.
즉, 선택과 정렬 등의 단어가 왜 사용하고 있는지 어원을 이해 해보자!!!
정렬 알고리즘
1. 퀵 정렬(Quick Sort)
동작 방법
코드 작성
2. 선택 정렬(Selection Sort)
어원편
선택 정렬(Selection Sort)에서 선택이라는 단어는 정렬되지 않은 데이터 중에서 가장 작은(또는 가장 큰) 값을 "선택"하여 정렬된 부분으로 이동시키는 방식에서 유래했습니다.
동작 방법
코드 작성
public class Main {
public static void main(String[] args) {
int[] arr = {3, 6, 1, 8, 2, 4};
for (int i = 0; i <arr.length - 1; i++) { // 배열의 마지막까지 확인할 필요가 없다.
int minIndex = i;
for (int j = i + 1; j<arr.length; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// swap
int temp = arr[minIndex];
arr[minIndex] = arr[i];
arr[i] = temp;
}
System.out.println("arr = " + Arrays.toString(arr));
}
}
3. 삽입 정렬(Insertion Sort)
어원편
값을 정렬된 부분에 알맞은 위치에 삽입한다. 마치 손에 카드를 들고 정렬하는 방식과 유사합니다. 새로운 카드를 알맞은 자리에 "삽입"하는 방식으로 정렬을 진행.
동작 방법
코드 작성
import java.util.*;
public class Main {
public static void main(String[] args) {
int[] arr = {7,2,3,8};
insertion_sort(arr, arr.length);
}
private static void insertion_sort(int[] a, int size) {
for (int i = 1; i < size; i++) {
int target = a[i];
int j = i - 1;
// target이 a[j]보다 작을 경우, j를 하나씩 왼쪽으로 이동
while (j >= 0 && target < a[j]) {
a[j + 1] = a[j]; // a[j]를 한 칸 뒤로 이동
j--;
}
a[j + 1] = target; // target을 적절한 위치에 삽입
}
System.out.println("a = " + Arrays.toString(a));
}
}
4. 버블 정렬(Bubble Sort)
동작 방법
회전은 배열크기 - 1 번 수행하고,
비교연산은 배열크기 - 라운드 횟수 번 수행한다.
출처: https://sfida.tistory.com/30 [Meezzi 미찌:티스토리]
코드 작성
import java.util.Arrays;
public class BubbleSort {
public static void main(String[] args) {
int[] arr = { 5, 2, 9, 4, 7, 1};
bubbleSort(arr);
}
private static void bubbleSort(int[] arr) {
// 회전 횟수
for (int i=0; i < arr.length-1; i++) {
// 비교연산
for (int j=1; j < arr.length - i; j++) {
if (arr[j] < arr[j - 1]) {
int temp = arr[j - 1];
arr[j - 1] = arr[j];
arr[j] = temp;
}
}
}
// arr = [1, 2, 4, 5, 7, 9]
System.out.println("arr = " + Arrays.toString(arr));
}
}
5. 힙 정렬(Heap Sort)
동작 방법
코드 작성
'프로그래밍 > 자료구조 && 알고리즘' 카테고리의 다른 글
[알고리즘] 피보나치 수열의 시간복잡도 (2) | 2024.07.24 |
---|---|
[알고리즘] 빅오(Big-O) 표기법 (0) | 2024.07.21 |
[탐색] DFS vs BFS - 간단 정리 (0) | 2023.08.13 |
[Java] 큐(Queue) (0) | 2023.07.20 |
[Python] 해시 테이블(Hast Table) (0) | 2022.09.30 |