Ở đây chúng ta sẽ xem cách sắp xếp gnome hoạt động. Đây là một thuật toán sắp xếp khác. Trong cách tiếp cận này nếu danh sách đã được sắp xếp thì sẽ mất O (n) thời gian. Vì vậy, độ phức tạp thời gian trường hợp tốt nhất là O (n). Nhưng độ phức tạp của trường hợp trung bình và trường hợp xấu nhất là O (n ^ 2). Bây giờ chúng ta hãy xem thuật toán để có ý tưởng về kỹ thuật sắp xếp này.
Thuật toán
gnomeSort (arr, n)
begin index := 0 while index < n, do if index is 0, then index := index + 1 end if if arr[index] >= arr[index -1], then index := index + 1 else exchange arr[index] and arr[index - 1] index := index - 1 end if done end
Ví dụ
#include<iostream>
using namespace std;
void gnomeSort(int arr[], int n){
int index = 0;
while(index < n){
if(index == 0) index++;
if(arr[index] >= arr[index - 1]){ //if the element is greater than previous one
index++;
} else {
swap(arr[index], arr[index - 1]);
index--;
}
}
}
main() {
int data[] = {54, 74, 98, 154, 98, 32, 20, 13, 35, 40};
int n = sizeof(data)/sizeof(data[0]);
cout << "Sorted Sequence ";
gnomeSort(data, n);
for(int i = 0; i <n;i++){
cout << data[i] << " ";
}
} Đầu ra
Sorted Sequence 13 20 32 35 40 54 74 98 98 154