- Pinapabuti ng Shell Sort ang pagpasok sa pamamagitan ng paggamit ng mga gaps para pagbukud-bukurin ang mga sublist, binabawasan ang mga paghahambing at traversal.
- Ang pagganap ay nakasalalay sa pagkakasunud-sunod ng mga puwang; ang average ay maaaring lumapit sa O(n log n), pinakamasamang kaso O(n²).
- Hindi ito stable: maaaring baguhin ng pantay na mga elemento ang kanilang relatibong pagkakasunud-sunod sa panahon ng pag-uuri.
- Tamang-tama para sa medium-sized na kaayusan; para sa napakalaking set, ang QuickSort o MergeSort ay inirerekomenda para sa higit na kahusayan.
Sa mundo ng programming, mahalagang magkaroon ng mahusay na mga algorithm sa pag-uuri na nagbibigay-daan sa amin na ayusin ang malalaking volume ng data nang mabilis at tumpak. Isa sa mga algorithm na ito ay ang Shell Sort Method. Sa artikulong ito, susuriin natin ang Shell Sort Method sa C at Java programming language nang malalim. Matututuhan natin kung paano ipatupad ang algorithm na ito nang sunud-sunod, pag-aralan ang pagiging kumplikado at pagganap nito, at talakayin ang mga pakinabang at disadvantage ng paggamit nito. Humanda sa pagsisid sa kamangha-manghang mundo ng Shell Sort Method sa C at Java!
Ano ang Paraan ng Pag-uuri ng Shell?
Ang Shell Sort Method, na kilala rin bilang Shell Sort, ay isang sorting algorithm na binuo ni Donald Shell noong 1959. Ang algorithm na ito ay nakabatay sa ideya ng paghahati sa orihinal na listahan sa mas maliliit na sublist at pag-uuri ng mga ito nang hiwalay. Pagkatapos, pagsamahin ang mga pinagsunod-sunod na sublist na ito upang makakuha ng panghuling pinagsunod-sunod na listahan. Ang paraan ng Shell Sort ay isang pagpapabuti sa direktang insertion algorithm dahil binabawasan nito ang bilang ng mga paghahambing at pagbabago na kinakailangan.
Pagpapatupad ng Shell Sort Method sa C
Hakbang 1: Tukuyin ang shellSort() function
Para ipatupad ang Shell Sort Method sa wika C, kailangan muna nating tukuyin ang isang function na tinatawag shellSort(). Ang function na ito ay kukuha bilang isang parameter ng isang hanay ng mga elemento at ang kanilang haba. Narito ang paunang code:
void shellSort(int arr[], int n) {
// Implementación del Método Shell Sort
}
Hakbang 2: Kalkulahin ang laki ng gap
Gumagamit ang Shell Sort Method ng gap para hatiin ang listahan sa mas maliliit na sublist. Ang laki ng pagtalon ay kinakalkula tulad ng sumusunod:
int gap = 1;
while (gap < n / 3) {
gap = 3 * gap + 1;
}
Hakbang 3: Ilapat ang direktang insertion algorithm na may laki ng pagtalon
Pagkatapos ay inilapat namin ang direktang insertion algorithm upang pag-uri-uriin ang mga sublist na may sukat ng pagtalon na tinutukoy sa nakaraang hakbang. Narito ang code:
while (gap > 0) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = (gap - 1) / 3;
}
Hakbang 4: Subukan ang algorithm
Sa wakas, maaari naming subukan ang aming algorithm sa pamamagitan ng pagtawag sa function shellSort() na may halimbawang kaayusan. Narito ang isang kumpletong halimbawa:
#include <stdio.h>
void shellSort(int arr[], int n) {
// Implementación del Método Shell Sort
}
int main() {
int arr[] = {9, 5, 1, 3, 7, 4, 6, 2, 8};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Arreglo original:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
shellSort(arr, n);
printf("\nArreglo ordenado:\n");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Binabati kita! Matagumpay mong naipatupad ang Shell Sort method sa wikang C. Ngayon, dumako naman tayo sa implementasyon ng Java.
Pagpapatupad ng Shell Sort Method sa Java
Hakbang 1: Tukuyin ang paraan ng shellSort().
Sa Java, ipapatupad namin ang Shell Sort Method bilang isang static na paraan ng isang klase. Narito ang paunang code:
public class ShellSort {
public static void shellSort(int[] arr) {
// Implementación del Método Shell Sort
}
}
Hakbang 2: Kalkulahin ang laki ng gap
Tulad ng sa pagpapatupad ng C, dapat nating kalkulahin ang laki ng gap upang hatiin ang listahan sa mas maliliit na sublist. Ang pagkalkula ay pareho:
int gap = 1;
while (gap < arr.length / 3) {
gap = 3 * gap + 1;
}
Hakbang 3: Ilapat ang direktang insertion algorithm na may laki ng pagtalon
Pagkatapos ay inilapat namin ang direktang insertion algorithm upang pag-uri-uriin ang mga sublist na may sukat ng pagtalon na tinutukoy sa nakaraang hakbang. Narito ang code:
while (gap > 0) {
for (int i = gap; i < arr.length; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
gap = (gap - 1) / 3;
}
Hakbang 4: Subukan ang algorithm
Sa wakas, maaari naming subukan ang aming algorithm sa pamamagitan ng pagtawag sa pamamaraan shellSort() na may halimbawang kaayusan. Narito ang isang kumpletong halimbawa:
public class Main {
public static void main(String[] args) {
int[] arr = {9, 5, 1, 3, 7, 4, 6, 2, 8};
System.out.println("Arreglo original:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
ShellSort.shellSort(arr);
System.out.println("\nArreglo ordenado:");
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
}
Binabati kita! Naipatupad mo ang Shell Sort Method sa Java. Ngayon tingnan natin ang ilang mga madalas itanong tungkol sa algorithm na ito.
Mga madalas itanong
1. Ano ang pagiging kumplikado ng Shell Sort Method?
Ang pagiging kumplikado ay depende sa laki ng pagtalon na ginamit. Sa pinakamasamang kaso, ang pagiging kumplikado nito ay O(n²), ngunit sa karaniwan, ang pagiging kumplikado nito ay maaaring mapabuti sa O(n log n) sa pamamagitan ng paggamit ng mga partikular na pagkakasunud-sunod ng pagtalon.
2. Kailan mo dapat gamitin ang Shell Sort Method sa halip na iba pang mga algorithm ng pag-uuri?
Ito ay lalong mabisa sa mga array na katamtaman ang laki. Kung mayroon kang malaking array, maaaring mas mabilis ang iba pang mga algorithm tulad ng QuickSort o MergeSort . Gayunpaman, ang pamamaraang ito ay nananatiling isang mabisang opsyon at maaaring mas madaling ipatupad sa ilang mga kaso.
3. Stable ba ang Shell Sort Method?
Hindi, hindi stable ang Shell Sort Method. Nangangahulugan ito na ang mga elemento na may parehong halaga ay maaaring magbago ng kanilang pagkakasunud-sunod sa panahon ng proseso ng pag-uuri.
4. Maaari ko bang gamitin ang Paraan sa ibang mga programming language?
Oo, maaari itong ipatupad sa halos anumang programming language. Ang lohika ng algorithm ay independiyente sa wika, kaya maaari mo itong iakma sa iyong mga pangangailangan.
5. Mayroon bang anumang mga variation ng Shell Sort Method?
Oo, may ilang variant, gaya ng Shell Sort na may partial insertion sort at Shell Sort na may accelerated partial insertion sort. Ang mga variant na ito ay maaaring higit pang mapabuti ang pagganap ng algorithm sa ilang mga kaso.
6. Angkop ba ang Shell Sort Method para sa pag-uuri ng mga naka-link na listahan?
Ang Paraan ay hindi ang pinakakaraniwang pagpipilian para sa pag-uuri ng mga naka-link na listahan, dahil umaasa ito sa random na pag-access sa mga elemento ng array. Gayunpaman, posibleng iakma ang algorithm upang gumana sa mga naka-link na listahan kung gagawin ang isang maingat na diskarte.
Konklusyon
Sa buod, ang Shell Sort ay isang mahusay na algorithm sa pag-uuri na naghahati sa orihinal na listahan sa mas maliliit na sublist at inaayos ang mga ito nang nakapag-iisa. Sa pamamagitan ng mga implementasyon sa mga wikang programming ng C at Java, sinuri namin nang sunud-sunod kung paano ilapat ang algorithm na ito at tinalakay ang mga katangian, pagiging kumplikado, at mga aplikasyon nito. Kung naghahanap ka ng mabilis at madaling paraan upang pag-uri-uriin ang mga medium-sized na array, ang Shell Sort ay maaaring maging isang mahusay na pagpipilian.
Tandaan na ang pagsasanay ay susi sa pag-master ng algorithm na ito, kaya huwag mag-atubiling ipatupad ito sa sarili mong mga proyekto at mag-eksperimento sa iba't ibang laki at variant ng pagtalon. Good luck!