Korpusa kārtošanas metode C un Java: pilnīga rokasgrāmata

Informatec Digital » Algoritmi » Korpusa kārtošanas metode C un Java: pilnīga rokasgrāmata

Programmēšanas pasaulē ir svarīgi, lai būtu efektīvi šķirošanas algoritmi, kas ļauj ātri un precīzi organizēt lielu datu apjomu. Viens no šiem algoritmiem ir čaulas kārtošanas metode. Šajā rakstā mēs padziļināti izpētīsim Shell šķirošanas metodi C un Java programmēšanas valodās. Mēs iemācīsimies soli pa solim ieviest šo algoritmu, analizēsim tā sarežģītību un veiktspēju, kā arī apspriedīsim tā izmantošanas priekšrocības un trūkumus. Sagatavojieties ienirt aizraujošajā Shell šķirošanas metodes pasaulē C un Java valodā!

Kas ir čaulas kārtošanas metode?

Shell Sort Method, kas pazīstams arī kā Shell Sort, ir kārtošanas algoritms, ko 1959. gadā izstrādāja Donalds Šells. Šī algoritma pamatā ir ideja sadalīt sākotnējo sarakstu mazākos apakšsarakstos un kārtot tos neatkarīgi. Pēc tam apvienojiet šos sakārtotos apakšsarakstus, lai iegūtu galīgo sakārtoto sarakstu. Shell Sort metode ir tiešās ievietošanas algoritma uzlabojums, jo tā samazina nepieciešamo salīdzinājumu un maiņu skaitu.

Shell šķirošanas metodes ieviešana programmā C

1. darbība: definējiet funkciju shellSort().

Lai ieviestu čaulas kārtošanas metodi valoda C, vispirms jādefinē funkcija, ko sauc shellSort(). Šī funkcija kā parametru izmantos elementu masīvu un to garumu. Šeit ir sākotnējais kods:

void shellSort(int arr[], int n) {
   // Implementación del Método Shell Sort
}

2. darbība: aprēķiniet atstarpes lielumu

Apvalka kārtošanas metode izmanto atstarpi, lai sadalītu sarakstu mazākos apakšsarakstā. Lēciena lielumu aprēķina šādi:

int gap = 1;
while (gap < n / 3) {
   gap = 3 * gap + 1;
}

3. darbība: izmantojiet tiešās ievietošanas algoritmu ar lēciena lielumu

Pēc tam mēs izmantojam tiešās ievietošanas algoritmu, lai kārtotu apakšsarakstus ar lēciena lielumu, kas noteikts iepriekšējā darbībā. Šeit ir kods:

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;
}

4. darbība: pārbaudiet algoritmu

Visbeidzot, mēs varam pārbaudīt savu algoritmu, izsaucot funkciju shellSort() ar izkārtojuma piemēru. Šeit ir pilns piemērs:

#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;
}

Apsveicam! Jūs esat veiksmīgi ieviesis Shell Sort metodi C valodā . Tagad pāriesim pie ieviešanas Java valodā.

Shell šķirošanas metodes ieviešana Java

1. darbība: definējiet shellSort() metodi

Java mēs ieviesīsim Shell šķirošanas metodi kā klases statisku metodi. Šeit ir sākotnējais kods:

public class ShellSort {
   public static void shellSort(int[] arr) {
      // Implementación del Método Shell Sort
   }
}

2. darbība: aprēķiniet atstarpes lielumu

Tāpat kā C ieviešanā, mums ir jāaprēķina atstarpes lielums, lai sadalītu sarakstu mazākos apakšsarakstos. Aprēķins ir tāds pats:

int gap = 1;
while (gap < arr.length / 3) {
   gap = 3 * gap + 1;
}

3. darbība: izmantojiet tiešās ievietošanas algoritmu ar lēciena lielumu

Pēc tam mēs izmantojam tiešās ievietošanas algoritmu, lai kārtotu apakšsarakstus ar lēciena lielumu, kas noteikts iepriekšējā darbībā. Šeit ir kods:

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;
}

4. darbība: pārbaudiet algoritmu

Visbeidzot, mēs varam pārbaudīt savu algoritmu, izsaucot metodi shellSort() ar izkārtojuma piemēru. Šeit ir pilns piemērs:

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] + " ");
      }
   }
}

Apsveicam! Jūs esat ieviesis čaulas kārtošanas metodi Java. Tagad apskatīsim dažus bieži uzdotos jautājumus par šo algoritmu.

Bieži uzdotie jautājumi

1. Kāda ir čaulas kārtošanas metodes sarežģītība?

Sarežģītība ir atkarīga no izmantotā lēciena lieluma. Sliktākajā gadījumā tā sarežģītība ir O(n²), bet vidēji tā sarežģītību var uzlabot līdz O(n log n), izmantojot specifiskas lēcienu secības.

2. Kad vajadzētu izmantot čaulas kārtošanas metodi, nevis citus kārtošanas algoritmus?

Tas ir īpaši efektīvs ar vidēja lieluma masīviem. Ja jums ir liels masīvs, citi algoritmi, piemēram, QuickSort vai MergeSort, varētu būt ātrāki. Tomēr šī metode joprojām ir dzīvotspējīga iespēja un dažos gadījumos to var būt vieglāk ieviest.

3. Vai Shell šķirošanas metode ir stabila?

Nē, čaulas kārtošanas metode nav stabila. Tas nozīmē, ka elementi ar vienādu vērtību šķirošanas procesa laikā var mainīt savu relatīvo secību.

4. Vai es varu izmantot metodi citās programmēšanas valodās?

Jā, to var ieviest praktiski jebkurā programmēšanas valodā. Algoritma loģika ir neatkarīga no valodas, tāpēc varat to pielāgot savām vajadzībām.

5. Vai ir kādas čaulas kārtošanas metodes variācijas?

Jā, ir daži varianti, piemēram, Shell Sort ar daļēju ievietošanas kārtošanu un Shell Sort ar paātrinātu daļēju ievietošanu. Šie varianti noteiktos gadījumos var vēl vairāk uzlabot algoritma veiktspēju.

6. Vai Shell šķirošanas metode ir piemērota saistīto sarakstu kārtošanai?

Metode nav visizplatītākā izvēle saistīto sarakstu kārtošanai, jo tā balstās uz nejaušu piekļuvi masīva elementiem. Tomēr ir iespējams pielāgot algoritmu darbam ar saistītajiem sarakstiem, ja tiek izmantota rūpīga pieeja.

Secinājums

Rezumējot, Shell Sort ir efektīvs kārtošanas algoritms , kas sadala sākotnējo sarakstu mazākos apakšsarakstos un kārto tos neatkarīgi. Izmantojot ieviešanu C un Java programmēšanas valodās, mēs esam soli pa solim izpētījuši, kā pielietot šo algoritmu, un apsprieduši tā īpašības, sarežģītību un pielietojumu. Ja meklējat ātru un vienkāršu veidu, kā kārtot vidēja lieluma masīvus, Shell Sort var būt lieliska izvēle.

Atcerieties, ka šī algoritma apguvei ir svarīga prakse, tāpēc droši ieviesiet to savos projektos un eksperimentējiet ar dažādiem lēcienu izmēriem un variantiem. Lai veicas!