Gnome Sort
난쟁이 정렬은 Stable한 정렬로 1번째 인덱스부터 시적해 왼쪽의 값이 자신보다 크다면 스왑후 인덱스를 하나 낮춰서 비교를 반복한다
O(N^2)의 시간복잡도와 O(1)의 공간 복잡도를 가지게 되며 코드가 단순해 구현이 간단하다
동작원리
오름차순 정렬 기준
- 1번째 인덱스부터 시작한다
- 왼쪽 인덱스의 값이 자신보다 작을경우 스왑 후 인덱스를 하나 낮춰서 1번으로 돌아간다
- 자신보다 작지 않을경우 인덱스를 하나 증가시킨다
- N번째 인덱스까지 반복한다
구현
c++1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| #include <iostream>
#include <vector>
#include <algorithm>
#include <ctime>
#include <cstdlib>
#include <random>
#include <numeric>
using namespace std;
void GnomeSort(vector<int> &gnomeSortVec){
int Index = 0, MAXSIZE = gnomeSortVec.size();
while(Index != (MAXSIZE - 1)){
if(gnomeSortVec[Index] > gnomeSortVec[Index + 1]){
while(Index >= 0 && gnomeSortVec[Index] > gnomeSortVec[Index + 1]){
gnomeSortVec[Index] ^= gnomeSortVec[Index + 1] ^= gnomeSortVec[Index] ^= gnomeSortVec[Index + 1];
--Index;
}
++Index;
} else
++Index;
}
}
int main() {
std::srand ( unsigned ( std::time(0) ) );
vector<int> vec(1000);
iota(begin(vec),end(vec),1);
std::shuffle(std::begin(vec), std::end(vec), default_random_engine {});
cout<<"Before Gnome Sorting"<<endl;
for(auto it : vec)
cout<<it<<" ";
cout<<endl;
GnomeSort(vec);
cout<<"After Gnome Sorting"<<endl;
for(auto it : vec)
cout<<it<<" ";
return 0;
}
|
같이보기
