Apvalkalo rūšiavimo metodas C ir Java: Visas vadovas

Informatec Digital » Algoritmai » Apvalkalo rūšiavimo metodas C ir Java: Visas vadovas

Programavimo pasaulyje labai svarbu turėti efektyvius rūšiavimo algoritmus, kurie leistų greitai ir tiksliai sutvarkyti didelius duomenų kiekius. Vienas iš šių algoritmų yra apvalkalo rūšiavimo metodas. Šiame straipsnyje mes išsamiai išnagrinėsime Shell rūšiavimo metodą C ir Java programavimo kalbomis. Išmoksime žingsnis po žingsnio įgyvendinti šį algoritmą, analizuosime jo sudėtingumą ir našumą, aptarsime jo naudojimo privalumus ir trūkumus. Pasiruoškite pasinerti į žavų apvalkalo rūšiavimo metodo pasaulį C ir Java kalbomis!

Kas yra apvalkalo rūšiavimo metodas?

Shell Sort Method, taip pat žinomas kaip Shell Sort, yra rūšiavimo algoritmas, kurį 1959 m. sukūrė Donaldas Shell. Šis algoritmas pagrįstas idėja padalyti pradinį sąrašą į mažesnius subsąraščius ir juos rūšiuoti atskirai. Tada sujunkite šiuos surūšiuotus posąraščius, kad gautumėte galutinį surūšiuotą sąrašą. „Shell Sort“ metodas yra tiesioginio įterpimo algoritmo patobulinimas, nes jis sumažina reikalingų palyginimų ir poslinkių skaičių.

Apvalkalo rūšiavimo metodo įgyvendinimas C

1 veiksmas: apibrėžkite funkciją shellSort().

Norėdami įdiegti apvalkalo rūšiavimo metodą C kalba, pirmiausia turime apibrėžti funkciją, vadinamą shellSort(). Ši funkcija kaip parametrą imsis elementų masyvo ir jų ilgio. Štai pradinis kodas:

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

2 veiksmas: apskaičiuokite tarpo dydį

Apvalkalo rūšiavimo metodas naudoja tarpą sąrašui padalyti į mažesnius posąraščius. Šuolio dydis apskaičiuojamas taip:

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

3 veiksmas: taikykite tiesioginio įterpimo algoritmą su šuolio dydžiu

Tada taikome tiesioginio įterpimo algoritmą, kad surūšiuotume posąraščius su šuolių dydžiu, nustatytu ankstesniame veiksme. Štai kodas:

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 veiksmas: išbandykite algoritmą

Galiausiai galime išbandyti savo algoritmą iškviesdami funkciją shellSort() su išdėstymo pavyzdžiu. Čia yra išsamus pavyzdys:

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

Sveikiname! Sėkmingai įdiegėte apvalkalo rūšiavimo metodą C kalba. Dabar pereikime prie „Java“ diegimo.

„Shell“ rūšiavimo metodo įgyvendinimas „Java“.

1 veiksmas: apibrėžkite shellSort() metodą

„Java“ programoje „Shell Sort Method“ įdiegsime kaip statinį klasės metodą. Štai pradinis kodas:

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

2 veiksmas: apskaičiuokite tarpo dydį

Kaip ir C įgyvendinime, turime apskaičiuoti tarpo dydį, kad padalytume sąrašą į mažesnius subsąraščius. Skaičiavimas yra tas pats:

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

3 veiksmas: taikykite tiesioginio įterpimo algoritmą su šuolio dydžiu

Tada taikome tiesioginio įterpimo algoritmą, kad surūšiuotume posąraščius su šuolių dydžiu, nustatytu ankstesniame veiksme. Štai kodas:

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 veiksmas: išbandykite algoritmą

Galiausiai galime išbandyti savo algoritmą iškviesdami metodą shellSort() su išdėstymo pavyzdžiu. Čia yra išsamus pavyzdys:

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

Sveikiname! „Java“ įdiegėte apvalkalo rūšiavimo metodą. Dabar pažvelkime į keletą dažniausiai užduodamų klausimų apie šį algoritmą.

Dažniausiai užduodami klausimai

1. Koks yra apvalkalo rūšiavimo metodo sudėtingumas?

Sudėtingumas priklauso nuo naudojamo šuolio dydžio. Blogiausiu atveju jo sudėtingumas yra O(n²), tačiau vidutiniškai jo sudėtingumas gali būti padidintas iki O(n log n), naudojant specifines šuolio sekas.

2. Kada turėtumėte naudoti apvalkalo rūšiavimo metodą, o ne kitus rūšiavimo algoritmus?

Tai ypač efektyvu vidutinio dydžio įrenginiuose. Jei turite didelį masyvą, kiti algoritmai, pvz., QuickSort arba MergeSort būk greitesnis. Tačiau šis metodas išlieka perspektyvus ir kai kuriais atvejais gali būti lengviau įgyvendinamas.

3. Ar apvalkalo rūšiavimo metodas yra stabilus?

Ne, apvalkalo rūšiavimo metodas nėra stabilus. Tai reiškia, kad elementai su ta pačia verte rūšiavimo proceso metu gali keisti santykinę tvarką.

4. Ar galiu naudoti Metodą kitomis programavimo kalbomis?

Taip, jį galima įgyvendinti praktiškai bet kuria programavimo kalba. Algoritmo logika nepriklauso nuo kalbos, todėl galite jį pritaikyti pagal savo poreikius.

5. Ar yra kokių nors apvalkalo rūšiavimo metodo variantų?

Taip, yra keletas variantų, pvz., Shell Sort su dalinio įterpimo rūšiavimu ir Shell Sort su pagreitintu dalinio įterpimo rūšiavimu. Šie variantai tam tikrais atvejais gali dar labiau pagerinti algoritmo veikimą.

6. Ar „Shell Sort Method“ tinka susietiems sąrašams rūšiuoti?

Metodas nėra labiausiai paplitęs pasirinkimas rūšiuojant susietus sąrašus, nes jis priklauso nuo atsitiktinės prieigos prie masyvo elementų. Tačiau galima pritaikyti algoritmą darbui su susietais sąrašais, jei laikomasi kruopštaus požiūrio.

Išvada

Trumpai tariant, apvalkalo rūšiavimo metodas yra a rūšiavimo algoritmas efektyvus, kuris suskaido pradinį sąrašą į mažesnius posąraščius ir surūšiuoja juos atskirai. Diegiant C ir Java programavimo kalbas, žingsnis po žingsnio ištyrėme, kaip pritaikyti šį algoritmą, aptarėme jo ypatybes, sudėtingumą ir taikomąsias programas. Jei ieškote greito ir paprasto būdo rūšiuoti vidutinio dydžio kompozicijas, apvalkalo rūšiavimo metodas gali būti puikus pasirinkimas.

Atminkite, kad praktika yra labai svarbi norint įsisavinti šį algoritmą, todėl drąsiai įgyvendinkite jį savo projektuose ir eksperimentuokite su skirtingais šuolio dydžiais ir variantais. Sėkmės!