[알고리즘] 선택정렬(Selection Sort) - Java(자바)
선택정렬(Selection Sort) 원소를 넣을 위치를 이미 정하고, 그 위치에 최솟값을 찾아서 넣는 정렬 방법이다. 첫번째 위치에는 배열의 모든 원소를 비교한 뒤, 최솟값을 그자리에 넣는다. 두번째 위치에는 첫번째 자리를 제외한 모든 원소를 비교한 뒤, 최솟값을 그자리에 넣는다. 이과정을 반복하며 정렬한다. 시간복잡도는 O(n²)이 걸리며 효율적이지 않다. 정렬할 때마다 남은 모든 원소를 봐야한다. -> n개라면 첫번째자리 n-1번, 두번째 자리는 n-2번이 반복된다. 제자리 정렬(=입력받은 배열외에 다른 메모리가 필요하지 않은 정렬) 불안정 정렬(=동일한 값에 대해서도 순서가 변경된다.) 구현 방법은 단순해서 쉬운 편이다. 배열 [6,3,4,1,5,2]이 있을 때, 선택정렬로 정렬하는 과정 [구현 ..
2023. 1. 24.
[알고리즘] 카운팅 정렬(Counting Sort) - JAVA(자바)
백준 2108번 통계학, 10989번 수 정렬하기3를 풀 때, 카운팅 정렬을 사용했었다. 카운팅 정렬에 대해 정리해두고자 글을 작성한다. 카운팅 정렬(Counting Sort) 계수 정렬이라고도 한다. 데이터의 크기 비교가 아닌 등장횟수를 통해 정렬하는 방법 시간복잡도가 O(n)으로 성능이 매우 좋은 알고리즘이다. (빠른 정렬 알고리즘은 대부분 O(nlogn)으로 카운팅 정렬이 훨씬 빠름) 최대 범위가 작을 때 유리하다. (정렬할 배열의 최댓값+1 길이의 배열 생성 필수 -> 최대 범위가 커지면 메모리 사용량증가) 먼저 정렬할 배열, 카운팅 배열, 정렬 후 배열을 생성한다. int[] arr = {1,1,1,5,5,2,2,2,7,8,4,4,4,4,9}; //정렬할 배열 int[] counting_arr ..
2023. 1. 16.
