알고리즘/Java_정렬_알고리즘
자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘
자바로 구현한 카운팅 정렬(Counting Sort/계수 정렬) 알고리즘
2023.03.02카운팅 정렬은 많은 알고리즘 중에 O(n)에 시간복잡도를 가지는 엄청난 성능을 가진 정렬 방식입니다. 보통 퀵 정렬(Quick Sort), 힙 정렬(Heap Sort), 합병 정렬(Merge Sort)이 빠르다는 정렬이지만 데이터끼리 직접 비교를 하기 때문에 O(NlogN)의 시간 복잡도를 가지는것이 한계입니다. 그렇다면 카운팅 정렬은 어떻게 속도의 한계를 극복할 수 있었을까요? 그리고 이렇게 빠른 속도임에도 불구하고 O(NlogN)의 시간 복잡도를 가지는 알고리즘을 사용하는 것일까요? 카운팅 정렬은 말 그대로 해당 숫자가 얼마나 출연했는지 카운팅 하면서 정렬하는 방식입니다. 1. 정렬 해야하는 원소의 범위만큼의 배열을 만든다. 2. 만든 배열 인덱스에 해당하는 수가 정렬해야 하는 배열에 있는 만큼 값을..
자바로 구현한 셀 정렬(Shell Sort) 알고리즘
자바로 구현한 셀 정렬(Shell Sort) 알고리즘
2023.02.23셀 정렬은 삽입 정렬을 기반으로 단점은 최소화하고 장점은 최대화 한 정렬 방식입니다. 만약에 삽입 정렬에 대해 모르신다면 삽입 정렬글을 읽고 오시는 것을 추천드립니다. https://kkungchan.tistory.com/287 자바로 구현한 삽입 정렬 알고리즘 삽입 정렬은 Target 인덱스를 정해서 올바른 인덱스에 삽입해 주는 정렬 방식입니다. 삽입 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다. 1. 비교 정렬 : 서로 kkungchan.tistory.com 삽입 정렬의 단점은 역순으로 정렬되어 있다면 교환이 너무 많이 생겨 시간이 최악의 경우 O(N2)의 시간 복잡도를 가진다는 것입니다. 반대로 삽입 정렬의 장점은 정렬이 어느 정도 되어 있다면 O(N)으로..
자바로 구현한 버블 정렬(거품 정렬) 알고리즘
자바로 구현한 버블 정렬(거품 정렬) 알고리즘
2023.02.22버블 정렬은 두개의 인접한 원소를 비교하는 형식의 정렬방식입니다. 버블 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 버블정렬 과정을 요약하면 다음과 같습니다. 1. 처음 원소부터 차례대로 인접한 원소를 비교하고 교환한다. 2. 마지막 원소를 1번을 반복하면서 저장한다. 3. 모든 원소가 저장되거나 교환이 없다면 정렬이 종료된다. 그림으로 보겠습니다. 그림으로 보면 크게 어려움 없이 알고리즘 이해가 될것입니다. 그럼 자바로 구현해보겠습니다. 전체코드 ..
자바로 구현한 삽입 정렬 알고리즘
자바로 구현한 삽입 정렬 알고리즘
2023.02.20삽입 정렬은 Target 인덱스를 정해서 올바른 인덱스에 삽입해 주는 정렬 방식입니다. 삽입 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 안정 정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 선택정렬의 정렬 과정을 요약하면 다음과 같습니다. 1. 첫 인덱스와 이미 정렬된 인덱스를 제외한 가장 작은 인덱스를 타깃으로 결정합니다. 2. 타겟과 타깃보다 작은 인덱스의 값들을 비교하여 정렬합니다. 3. 모든 인덱스가 정렬될 때까지 1,2번 과정을 반복합니다. 그림으로 보겠습니다. 그림으로 보시게 되면 큰 어려..
자바로 구현한 선택 정렬 알고리즘
자바로 구현한 선택 정렬 알고리즘
2023.02.20선택 정렬알고리즘은 O(N2)의 시간 복잡도를 가지는 정렬 알고리즘 중에 하나입니다. 선택 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬입니다. 3. 불안정 정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 선택정렬은 이름에서와 같이 최솟값을 찾아 선택하여 선수대로 교환하는 정렬방식입니다. 정렬 과정을 요약하면 다음과 같습니다. 1. 해당 리스트의 최솟값을 찾는다. 2. 리스트의 맨 처음 인덱스와 교환한다. 3. 교환한 인덱스를 제외한 리스트에서 최솟값을 찾고 정렬된 인덱스를 제외한 맨 앞 인덱스와 교환한다. 알고리즘..
자바로 구현한 합병 정렬(병합 정렬) 알고리즘 - 분할 정복
자바로 구현한 합병 정렬(병합 정렬) 알고리즘 - 분할 정복
2023.01.18목차 더보기 1. 합병 정렬에 관하여 2. 분할 정복 알고리즘에 관하여 3. 병합 정렬 알고리즘 로직과 질문 4. 병합 정렬 알고리즘 자바 구현 - [TOP-DOWN] - [BOTTOM-UP] 5. 병합 정렬 알고리즘 장단점 1. 합병 정렬에 관하여 합병 정렬 알고리즘은 정렬 알고리즘의 하나로 분할 정복을 사용한 알고리즘입니다. 합병 정렬의 특징으로는 1. 비교 정렬입니다. 2. 제자리 정렬이 아닙니다. 3. 안정정렬입니다. 1. 비교 정렬 : 서로 값을 비교하여 정렬하는 알고리즘입니다. 2. 제자리 정렬 : 해당 배열 외에 또 다른 배열의 저장 공간이 필요가 없습니다. 3. 안정정렬 : 같은 값일 경우 해당 정렬이 변경되지 않습니다. 2. 분할 정복 알고리즘에 관하여 그럼 분할 정복이 무엇인지 알아보겠..