✅ 정렬 알고리즘
- 버블정렬 ( Bubble Sort )
- 선택정렬 ( Selection Sort )
- 삽입정렬 ( Insertion Sort )
- 합병정렬 ( Merge Sort )
- 퀵정렬 ( Quick Sort )
- 힙정렬 ( Heap Sort )
- 셸정렬 ( Shell Sort )
- 계수정렬 ( Counting Sort )
정렬 알고리즘은 시간복잡도에 따라 분류 할 수 있으며 가장 기본적인 정렬이 O(n^2)의 시간복잡도를 가지는
버블정렬, 선택정렬, 삽입정렬이다.
이 정렬방식들은 모두 중첩반복문을 통해 정렬된다는 공통점이 있고,
반복도중 정렬이 완성된다 하더라도 주어진 반복문을 끝까지 실행해야 종료되는 정렬방법이다.
다음은 위의 반복문보다 좀 더 빠르고 효율적인 O(n log n)의 시간복잡도는 가지는 알고리즘으로
병합정렬, 힙정렬, 퀵정렬 이 있으며 이들은 모두 트리의 개념이 들어간 알고리즘이다.
🚩 버블정렬( bubble sort )
버블정렬은 첫 번째 원소부터 붙어있는 원소끼리 자리교환 하며 가장 뒤의 인덱스부터 정렬되는 방식이다.
한인덱스씩 뒤로가며 붙어있는 인덱스를 서로 비교해 더 큰 인덱스의 원소를 뒤로 보내는 방식으로 진행된다.
데이터를 하나씩 비교할 수 있어 정밀하게 비교가 가능하지만, 비교횟수가 많아지므로 성능면에서는 좋지못하다.
🟢 장점 : 가장쉬운 알고리즘으로 구현이 간단하고, 데이터를 하나씩 비교하기에 정밀한 비교가 가능하다.
🔴 단점 : 시간복잡도가 좋지않아 잘 사용되지 않는다.
🚩 선택정렬( selection sort )
선택정렬도 마찬가지로 시간복잡도 O(n^2)로 버블정렬과 유사하지만 제일 앞쪽부터 정렬된다.주어진 배열리스트 중 최소값을 찾고 해당값을 제일 앞에 위치한 값과 위치를 바꾸며 진행하는 방식이다.데이터를 하나씩 정밀비교 하기 때문에 비교횟수는 많지만 버블정렬과 다르게 교환횟수는 적어교환이 많이 이루어져야하는 자료상태라면 효율적일 정렬방식이다.
🟢 장점 : 구현이 가능하고, 비교횟수에 비해 교환횟수가 적다.
🔴 단점 : 시간복잡도가 좋지않다, 이미 정렬된 상태에서 자료가 추가되어 재정렬할경우 효율이 매우 떨어진다.
🚩 삽입정렬( insertion sort )
버블정렬이 비효율적인 면에 있기때문에 비교횟수를 효율적으로 줄이기위해 고안된 방법이다.
자료배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열부분과 비교해 자신의 위치를 찾아 넣는 방식이다.
버블정렬은 비교대상이 정렬되어있음에도 비교연산을 하지만 삽입정렬은
정렬된 값에 대해서는 한번도 교환이 일어나지 않고 N-1의 비교만 수행한다.
🟢 장점 : 정렬된 값에대해서는 교환이 일어나지 않는다. 배열의 원소가 정렬되어있을수록 속도가빠르다.
🔴 단점 : 삽입을 구현해야하므로 속도가 자료구조의 영향을 많이받는다, 입력배열이 역순정렬일경우 성능이 매우떨어진다.
🚩 병합정렬( merge sort )
일반적으로 사용되는 정렬 알고리즘이며 시간복잡도는 O(n log n)을 보장한다.리스트의 길이가 0또는 1일경우 이미 정렬된것으로 보며, 그렇지 않은경우 정렬되지 않은 리스트를절반으로 잘라 비슷한크기의 두부분 리스트로 나눈다. 각 부분리스트를 재귀적으로 합병정렬을 이용해 정렬한다.즉, 작은 단위로 쪼개 작은 단위부터 정렬해 정렬된 단위들을 계속 병합하며 진행하는 방식이다.
안정성이 있어 상당히 좋은 성능을 보여주지만, 정렬을 위해 데이터 전체크기만한 메모리가 더 필요하다.
🟢 장점 : 안정적이며 좋은성능을 보여준다, 일정한 시간복잡도O(n log n)을 가진다.
🔴 단점 : 데이터 전체크기만한 메모리가 더 필요하다.
🚩 퀵 정렬( quick sort )
연속적인 분할에 의한 정렬방식으로 처음 하나의 축(pivot)을 정해 이 축의 값보다 작은 값은 왼쪽에큰값을 오른쪽에 위치시킨뒤 왼쪽과 오른쪽의 수를 다시 각각의 축으로 나누어 축의 값이 1이 될때까지 정렬한다일반적으로 좋은 효율을 보여주지만 최악의 경우 O(n^2)를 가져 보다많은 시간이 소요되므로 안정성이 떨어진다.
🟢 장점 : 일반적으로 O(n log n)으로 준수한 효율을 가진다.
🔴 단점 : 축(pivot) 을 어떻게 설정하는지에따라 성능의 차이가 심해 안정성이 좋지않다.
🚩 힙 정렬( heap sort )
최대 힙트리나, 최소 힙트리를 구성해 정렬하는 방식이다.heap이라는 자료구조는 완전이진트리의 일종으로우선순위 큐를 위해 만들어진 자료구조이다.여러 개의 값중 최대값, 최소값을 빠르게 찾기 위해 사용되며,최대힙트리는 부모노드의 키값이 자식노드의 키값보다 크거나 같은 완전 이진 트리이며최소힙트리는 부모노드의 키값이 자식노드의 키값보다 작거나 같은 완전 이진 트리이다.
🟢 장점 : 항상 같은 시간복잡도를 가져 성능이 준수하다. O(n log n)알고리즘들 중 부가적인 메모리가 필요없다.
🔴 단점 : 같은 시간복잡도는 가지는 다른 알고리즘들에 비해 느린편이다.
🚩 셸 정렬( shell sort )
삽입정렬의 개념을 확대해 일반화한 정렬방법으로 알고리즘이 간단해 프로그램으로 쉽게 구현할 수 있다.효율도 삽입정렬보다 우수하며 멀리있는 레코드들끼리 비교 및 교환될 수 있어, 어떤 데이터가 제위치에서멀리 떨어져 있다면 많은 교환이 발생하는 버블정렬의 단점을 해결할 수 있다.입력으로 들어온 배열을 간격(gap)이라고하는 일정한 기준에따라 분류해 이를 통해 연속적이지않은여러개의 부분배열을 생성한 뒤 각 배열을 삽입정렬로 정렬한다.모든 배열이 정렬되면 다시 전체 배열을 여러개의 부분 배열로 나누는데 이 때 간격을 전 단계보다더 작게 설정해 생성되는 부분 배열의 개수를 전 단계보다 적게만든다.그 후 부분 배열의 개수가 1이 될때까지 앞의 과정을 반복한다.
🟢 장점 : 삽입 정렬의 문제점을 해결함으로써 성능이 좋다.
🔴 단점 : 설정하는 간격(gap)에 따라 성능의 차이가 심하다.
🚩 계수 정렬( counting sort )
모든 데이터가 양의 정수인 상황에서 데이터의 개수가n, 데이터 중 최대값이 k일때 계수정렬은 최악의 경우에도 O(n+k)의 시간복잡도를 보장한다.빠르다고 평가되어 널리사용되는 O(n log n)의 시간복잡도는 가지는 퀵, 힙, 합병정렬에 비해서 엄청난 속도이다.
🟢 장점 : 특정 조건이 부합할 때 사용할 수 있는 매우 빠른 정렬방식이다.
🔴 단점 : 모든데이터가 단순 숫자이어야 한다. 즉, 특정타입에 한정되어있다.
https://www.toptal.com/developers/sorting-algorithms
| Insertion | Selection | Bubble | Shell | Merge | Heap | Quick | Quick3 | |
| Random |  |
 |
 |
 |
 |
 |
 |
 |
| Nearly Sorted |
 |
 |
 |
 |
 |
 |
 |
 |
| Reversed |  |
 |
 |
 |
 |
 |
 |
 |
| Few Unique |
 |
 |
 |
 |
 |
 |
 |
 |
-출처
https://coding-factory.tistory.com/615
https://jbhs7014.tistory.com/180
https://scshim.tistory.com/267
https://st-lab.tistory.com/104?category=892973
'Java' 카테고리의 다른 글
| JAVA - 선택정렬(Selection Sort) (0) | 2022.08.30 |
|---|---|
| JAVA - 거품정렬(Bubble Sort) (0) | 2022.08.27 |
| 시간복잡도 (0) | 2022.08.25 |
| JAVA - 재귀 ( recursion ) (0) | 2022.08.13 |
| JAVA - 반복문 ( while, do-while ) (0) | 2022.07.06 |