<문제 소개>
<소스 코드>
#include <iostream>
#include <string>
#include <vector>
#include <sstream>
#include <map>
#include <cmath>
#include <stack>
#include <queue>
#include <algorithm>
#include <cstdlib>
using namespace std;
void SkipInsertionSort(vector<int>& v, int start, int skipNum)
{
// 숫자를 건너뛰는 삽입정렬
for (int i = start + skipNum; i < v.size(); i += skipNum)
{
int originNum = v[i];
int originIndex = i;
for (int j = i - skipNum; j >= 0; j -= skipNum)
{
if (v[j] > originNum)
{
// 앞의 숫자가 더 큰 경우
v[j + skipNum] = v[j];
originIndex -= skipNum;
}
else
{
// 현재 숫자가 더 큰 경우
break;
}
// 원래 숫자의 자리를 찾아서 저장
v[originIndex] = originNum;
}
}
}
void ShellSort(vector<int>& v)
{
for (int skipNum = v.size() / 2; skipNum > 0; skipNum /= 2)
{
// 건너뛸 숫자가 짝수인 경우 홀수로 바꿔주어야함
// -> 간격이 홀수일 경우가 시간복잡도가 더 좋아지기 때문
if (skipNum % 2 == 0) skipNum++;
// 쪼개진 벡터의 원소 수만큼 반복
for (int i = 0; i < skipNum; i++)
{
SkipInsertionSort(v, i, skipNum);
}
}
// 간격을 n/3+1로 한 경우
//for (int skipNum = v.size() / 3 + 1; skipNum >= 1; skipNum = skipNum / 3 + 1)
//{
// // 건너뛸 숫자가 짝수인 경우 홀수로 바꿔주어야함
// // 쪼개진 벡터의 원소 수만큼 반복
// for (int i = 0; i < skipNum; i++)
// {
// SkipInsertionSort(v, i, skipNum);
// }
// if (skipNum == 1) break; // 1일 경우 반복 끝냄
//}
}
int main()
{
int N;
cin >> N;
vector<int> v;
// 원소 입력
while (N > 0)
{
int x;
cin >> x;
v.push_back(x);
N--;
}
// 7. 쉘 정렬
// - 삽입정렬 상위호환버전이라고 생각하면 될듯?
// 1. 배열을 반으로 쪼개고 앞과 뒤의 같은 인덱스를 하나의 배열로 보고 삽입정렬을 해줌
// 2. 그 다음엔 반의 반으로 배열을 쪼개고 같은 과정 반복
// 3. 위의 과정을 1개씩 쪼개지는 삽입정렬과 같을때까지 반복
ShellSort(v);
// 원소 출력
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << endl;
}
return 0;
}<풀이과정>
1. ShellSort()
1-1. 쉘 정렬은 건너뛰는 숫자를 감소시키면서 점점 작게 분해해가면서 하는 정렬이다.
1-2. skipNum이라는 건너뛰는 숫자를 for문을 이용해 벡터의 크기의 반(v.size()/2)부터 시작해서 계속해서 1/2씩 감소시키면서 반복한다.
1-3. 이때 알고리즘상 건너뛰는 숫자 skipNum이 홀수일때가 짝수일 때보다 더 효율적이기에 짝수라면 +1을 해주어 홀수로 만들어 준다.(짝수 -> 홀수 -> n/3 +1 순으로 시간이 빨라짐 -> 백준에서 시간체크 결과는 홀수보다 n/3+1이 더 느렸는데 왜그런지는 잘 모르겠당,,,ㅋㅋ)
1-4. 그런 다음 0번인덱스부터 skipNum-1번 인덱스까지 반복하며 SkipInsertionSort()를 진행한다.
2. SkipInsertionSort()
2-1. 이 함수는 skipNum으로 건너뛰어지는 원소들로만 이루어진 배열이 있다고 했을 때 해당 배열을 InsertionSort해주는 함수이다.(ex. skipNum이 3인 경우 : { 0 -> 3 -> 6 -> 9 }, { 1 -> 4 -> 7 -> 10 }, { 2 -> 5 -> 8 -> 11 })
2-2. 그렇기에 총 skipNum개의 배열이 만들어지고, 해당 배열들을 각각 삽입 정렬 해주면 된다.
2-3. 이 함수의 인자로는 벡터 v와 시작 인덱스 start 그리고 건너뛸 숫자 skipNum을 받는다.
2-4. InsertionSort에서는 두번째 인덱스인 1번인덱스부터 시작했다면 SkipInsertionSort에서는 두번째 인덱스가 시작 인덱스에 건너뛸 숫자만큼 더한 번호 start+skipNum 이다.
2-5. 해당 숫자부터 시작해서 인덱스를 skipNum씩 건너뛰면서 진행하고 벡터의 사이즈가 넘어가면 반복을 끝낸다.
2-6. 반복문 내부도 삽입 정렬과 같이 현재 자리를 찾을 원소와 해당 인덱스를 저장해 놓고, 앞과 비교를 하며 자신보다 작은 수가 나올때까지 자신보다 큰 수들을 한칸씩 뒤로 당겨준다.(이때의 한 칸은 skipNum칸 을 의미한다.)
2-7. 자신보다 작은 수가 나오면 해당자리에 원소를 위치시킨다.
3. 위의 과정을 반복하면 결국 1칸씩 반복되는 InsertionSort와 같은 과정도 진행되지만 그 전에 간격을 넓게해서 정렬을 진행할 때 이미 대부분 정렬되어 있으므로 적어도 삽입정렬 만큼의 시간이 걸리게 된다.
<코멘트>
이번엔 일곱번째 방법인 쉘 정렬로 풀어보았다!
삽입 정렬이랑 비슷해서 어떤 방식인지 이해하니깐 코드 짜는거는 어렵진 않았던 것 같다!
- 쉘 정렬 -
장점
- 삽입 정렬의 단점을 보완해서 만든 정렬법이어서 삽입 정렬보다 더 뛰어난 성능을 갖는다.
- 알고리즘이 간단하여 쉽게 구현할 수 있다.
단점
- 일정한 간격에 따라서 배열을 바라봐야함. 즉, 간격을 잘못 설정하면 성능이 안 좋아질 수 있음.
특징
1. 시간복잡도
- 최악 : O(n^2)
- 평균 : O(n^1.5) -> 평균적으로 삽입정렬보다 빠름
- 최선 : O(n)
2. 공간복잡도 O(n)
3. in-place정렬
4. not-stable정렬
<cf>
1. stable vs not-stable
- stable 정렬은 중복된 키 값이 있을 때 이를 순서대로 정렬하는 알고리즘을 뜻함.
- 즉 , 정렬했을 때 중복된 키 값이 원래 순서대로 정렬되어있으면 stable 아니면 not-stable이다.
2. in-place vs not in-place
- in- place 정렬은 원소들의 개수에 비해 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘을 뜻함.
- not in-place 정렬은 원소들의 개수에 비례하여 저장 공간을 더 사용하는 정렬 알고리즘을 뜻함.
<제출 결과>
<쉘 정렬>
<병합 정렬> - 준수한 시간대
<삽입 정렬> - 버블/선택 정렬보다 빠른 시간대, 밑의 결과는 매번 swap했을 경우
<힙 정렬> - 퀵 정렬보다 느린 시간대
<퀵 정렬> - 준수한 시간대
<선택정렬> - 버블정렬에 비해 조금 더 빠르다는 것을 알 수 있음
<버블정렬>
