Chiqish natijasi:
Saralash uchun elementlar sonini kiriting: 5
Saralash uchun 5 elementni kiriting: 10 21 47 3 59
Saralangan qator
3 10 21 47 59
8.Shell Sort
Qisqichbaqasimon saralash - bu qo'shishni saralash texnikasining kengaytmasi. Indertion sort-da, biz faqat keyingi element bilan shug'ullanamiz, holbuki qobiq tartibida biz ota-onalar ro'yxatidan kichikroq ro'yxatlar yaratib, o'sish yoki bo'shliqni ta'minlaymiz. Ichki ro'yxatdagi elementlar bir-biriga zid bo'lmasligi kerak, aksincha ular bir-biridan farq qiladigan "gap_value" dir.
Qisqichbaqasimon qo'shilish tartibiga qaraganda tezroq bajariladi va qo'shilish turiga qaraganda kamroq harakatlarni talab qiladi.
Agar biz bo'shliqni ta'minlasak, unda har bir element 3 ta alohida bo'lgan quyidagi quyi ro'yxatlarga ega bo'lamiz.
Keyin ushbu uchta pastki ro'yxatni saralaymiz.
Tarkiblangan sub-massivlarni birlashtirgandan so'ng biz yuqoridagi qator deyarli tartiblangan. Endi biz massivni tartiblash uchun ushbu massivda joylashtirish tartibini amalga oshirishimiz mumkin.
Shunday qilib, biz tegishli kattalashtirish yordamida massivni pastki ro'yxatlarga ajratamiz va keyin ularni birlashtirsak, deyarli saralangan ro'yxatni olamiz. Ushbu ro'yxatdagi qo'shishni tartiblash usuli bajarilishi mumkin va qator asl qo'shib qo'yish turiga qaraganda kamroq harakatda tartiblangan.
Shell Sortning C ++ da bajarilishi quyida berilgan.
#include
using namespace std;
// shellsort implementation
int shellSort(int arr[], int N)
{
for (int gap = N/2; gap > 0; gap /= 2) {
for (int i = gap; i < N; i += 1) {
//sort sub lists created by applying gap
int temp = arr[i];
int j;
for (j = i; j >= gap && arr[j - gap] > temp; j -= gap)
arr[j] = arr[j - gap];
arr[j] = temp;
}
}
return 0;
}
int main()
{
int arr[] = {45,23,53,43,18};
//Calculate size of array
int N = sizeof(arr)/sizeof(arr[0]);
cout << "Array to be sorted: \n";
for (int i=0; icout << arr[i] << " ";
shellSort(arr, N);
cout << "\nArray after shell sort: \n";
for (int i=0; icout << arr[i] << " ";
return 0;
}
|
Do'stlaringiz bilan baham: |
