[JAVA / 알고리즘] - 정렬

정렬

데이터를 원하는 기준으로 순서대로 배치하는 방법으로 구현

 

버블 정렬 (Bubble Sort)

인접한 데이터를 비교하면서 위치를 바꾸는 방식

알고리즘 복잡도 : O(n²)

 

삽입 정렬 (Insertion Sort)

앞의 데이터를 정렬하면서 삽입 위치를 찾아 정렬하는 방식

알고리즘 복잡도 : O(n²)

 

1번 인덱스부터 시작

앞쪽 데이터들이랑 비교해서 작으면 변경

 

선택 정렬 (Selection Sort)

최소 or 최대 값을 찾아서 가장 앞쪽이나 뒤쪽부터 정렬하는 방식

(최소값을 찾아서 가장 앞쪽부터 정렬 or 최대값을 찾아서 가장 뒤쪽부터 정렬)

알고리즘 복잡도 : O(n²)

 

합병 정렬 (Merge Sort)

배열을 계속해서 분할하여 길이가 1이 되도록 만들어주고, 인접한 부분끼리 정렬하면서 합병하는 방식

알고리즘 복잡도 : O(nlogn)

 

힙 정렬 (Heap Sort)

힙 자료구조 형태의 정렬 방식으로 기존 배열을 최대 힙 구조로 변경 후 정렬하는 방식

알고리즘 복잡도 : O(nlogn)

 

퀵 정렬 (Quick Sort)

임의의 기준 값을 정하고 그 값을 기준으로 좌우로 분할하며 정렬하는 방식

알고리즘 복잡도 : O(n²) (일반적으로는 처리 속도가 빠르나, 기준 값이 최소값이나 최대값으로 지정되는 경우 O(n²))

 

트리 정렬 (Tree Sort)

이진 탐색 트리 (BST)를 만들어 정렬하는 방식

알고리즘 복잡도 : 알고리즘 복잡도 : O(nlogn)

 

기수 정렬 (Radix Sort)

낮은 자리 수부터 정렬하는 방식으로 각 원소간의 비교연산을 하지 않기 때문에 처리 속도가 빠르지만, 기수 테이블을 위한 메모리가 필요하다.

알고리즘 복잡도 : O(dn) (d는 최대 자릿수)

 

계수 정렬 (Counting Sort)

숫자끼리 비교하지 않고 카운트를 세서 정렬하는 방식으로 카운팅을 위한 메모리가 필요하다.

알고리즘 복잡도 : O(n + k) (k는 정렬 대상 데이터 중 최대 값)

 

셸 정렬 (Shell Sort)

삽입 정렬의 약점을 보완한 정렬 방식으로 이전의 모든 데이터와 비교하지 않고 일정 간격을 둬서 비교하는 방식

알고리즘 복잡도 : O(n²) (간격 설정에 따라 다르지만 일반적으로 삽입 정렬보다 빠르다.)