자 이쯤에서 슬슬 앞의 정렬을 까먹은분을 위해 짧막 상식
우리가 배웠던 정렬의 방식을 짧게 설명하고자 한다
1. Counting Sort (계수 정렬) - O(n)
= 배열을 생성해서 그 안에 숫자를 받는다 그리고 같은 숫자가 있다면 카운트하여 인덱스로 저장해두었다가 정렬할때 한개씩 나열하며 정렬한다.
2. Selection Sort (선택 정렬) - O(n2)
= 무작위로 받은 숫자를 쭈욱 나열하고 인덱스에 위치해야하는 수를 직접 찾아 해당 인덱스로 보내고 거기있던 수와 바꿔치기 한다.
3. Insertion Sort (삽입 정렬) - O(n2)
= 무작위로 받은 숫자를 나열하고 첫번째 인덱스와 두번째 인덱스를 비교한다. 그리고 이 정렬은 인덱스가 커지더라도 계속해서 앞의 숫자와 비교하며 수를 정렬한다.
4. Bubble Sort(거품 정렬) - O(n2)
= 무작위로 받은 숫자를 나열하고 한 라운드에 (배열 크기 - 라운드 횟수)만큼 비교한다. 총 (배열 크기 - 1) 만큼 비교한다.
셀은 기본적으로 삽입정렬을 기반으로 정의 한다.
우리가 공부했던 삽입 정렬은 배열이 순서대로면 O(n) 역순이면 O(n2) 이라는 특징이 있다
이 단점을 극복하고자 만들어진것이 바로 셸 정렬이다.
그렇다면 어떻게 하면 그 단점을 극복 할 수 있을까
말로하면 생각보다 간단하다 모든 수를 비교할 필요가 없다.
무슨말이냐면 모든것을 비교하는것이 아니라 주기를 주어서 띄엄띄엄 비교를 하는것이다.
그럼 수가 완전 반대편에 있어도 정렬 횟 수는 줄어들게 될것이다.
과정
1. 간격을 정한다 (gap)
2. 각 간격별로 분류 된 서브(부분) 리스트에 대해 삽입정렬을 한다.
3. 각 서브(부분) 리스트의 정렬이 끝나면 간격을 줄인다.
4. 간격이 1이 될 때까지 2번 과정으로 되돌아가며 반복한다.
그렇다면 간격(gap)을 정하는 기준이 뭘까?
답부터 말하자면 "없다" 적게 잡으면 간격이 너무 좁고 크면 오버헤드가 발생한다.
그래서 사람들은 관습적인 간격을 내놓았는데 그것이 gap sequences라고 하는것이다.
그렇다면 사람들이 관습적으로 정해놓았다는 Gap Sequences는 몇일까
1, 4, 10, 23, 57, 132, 301, 701 이다 물론 뒤에 더있는데 확정이 아니니 대략 저기서 부터 2.25씩 곱한다.
라고 생각해주면 될 것이다.
※ 자바의 배열은 21억을 못넘어서 그 전까지만 고려해서 Gap Sequences 를 만든다.
한 눈에 봐도 완전히 달라진 정렬방법이 보일것이다.
이렇게 일정 간격 만큼 패스 하면서 '거의 정렬 된 상태'로 만들고 최종적으로 마지막에 gap이 1인 삽입정렬을 시도하면 성능이 기존 삽입 정렬보다 우수해지는 것이다.
코드[ JAVA ]
구현은 나의 깃허브에 해놓았다 시간이 된다면 보는것을 적극 추천한다
https://github.com/ProblemSolveStudy/Tae_sik/tree/master/Sorts
GitHub - ProblemSolveStudy/Tae_sik
Contribute to ProblemSolveStudy/Tae_sik development by creating an account on GitHub.
github.com
셸 정렬의 장단점
◐ 장점
= 멀리 있는 원소들끼리 비교하고 교환한다.
= 삽입, 버블정렬보다 정렬속도가 빠르다
◑ 단점
= 일반적인 삽입 정렬에 비해 구현이 복잡하다.
= 적당한 sequence를 선택해야한다.(나는 ciura Squence 를 사용했다.)
= 일정한 간격을 두고 주기적으로 비교하고 교환하기 때문에 "비교 정렬"이다.
정리
셸 정렬은 삽입 정렬의 확장판으로써 셸 정렬 자체가 안정정렬은 아니지만 빠르다.
즉, 안정정렬이 필요없는 primitive type 은 셸을 사용해도 원소가 무작위라면 쓸 만 하다.
역시 정렬은 시간복잡도 이야기가 빠질수 없다 단점에서도 봤듯이 Sequence에 따라 달라진다.
내가 알아서 시퀀스를 사용한다던가 복잡한 수식으로 구해낸 시퀀스의 겨우 분석이 까다로워진다.
그래도 어떻게든 시간 복잡도를 구한다면
이진 탐색처럼 N/2, N/4, N/8 이렇게 증가하기 때문에 logN의 시간에서
그 수들을 배열하면서 N이 추가된다.
★ O(NlogN) 시간 복잡도가 되는것이다.
이것또한 최선이고 최악인 경우
gap을 1로 설정 , 가장 낮은 수가 가장 마지막에 있는 역순의 배열인 경우
★ O(N2)의 시간복잡도를 가지게 된다.
이것은 어떻게든 구한 식이고 위에 말했다시피 gap Sequence가 복잡해지면 구하기가 어렵다
| 최악 | 최선 | 평균 | |
| Counting Sort(계수 정렬) | O(n) | ||
| Selection Sort(선택 정렬) | O(n2) | O(n2) | O(n2) |
| Insertion Sort(삽입 정렬) | O(n2) | O(n) | O(n2) |
| Bubble Sort(버블 정렬) | O(n2) | O(n) | O(n2) |
| Shell Sort(셸 정렬) | O(nlogn) | O(n2) | none |
'CS > 👫🏼 정렬' 카테고리의 다른 글
| 2. 선택 정렬(Selection Sort) - O(n2) (0) | 2023.02.23 |
|---|---|
| 우선순위 큐(Priority Queue)와 힙 정렬(Heap Sort)의 차이 (0) | 2023.02.21 |
| 1. 카운팅 정렬 (Counting sort) - O(n) (2) | 2023.02.21 |
| 이진 삽입 정렬(Binary Insertion Sort) (0) | 2023.02.15 |
| 3. 삽입 정렬(Insertion Sort) - O(n2) (0) | 2023.02.15 |
