Shell Sort

V tomto kurzu se dozvíte, jak funguje třídění prostředí. Také najdete pracovní příklady třídění prostředí v C, C ++, Java a Python.

Shell sort je algoritmus, který nejprve seřadí prvky daleko od sebe a postupně snižuje interval mezi prvky, které mají být tříděny. Jedná se o zobecněnou verzi řazení.

V prostředí shell jsou tříděny prvky v určitém intervalu. Interval mezi prvky se postupně snižuje na základě použité sekvence. Výkon třídění prostředí závisí na typu sekvence použité pro dané vstupní pole.

Některé z použitých optimálních sekvencí jsou:

• Původní sekvence Shell: N/2 , N/4 ,… , 1
• Knuthovy přírůstky: 1, 4, 13,… , (3k - 1) / 2
• Sedgewickovy přírůstky: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
• Hibbardovy přírůstky: 1, 3, 7, 15, 31, 63, 127, 255, 511…
• Přírůstek Papernova a Staseviče: 1, 3, 5, 9, 17, 33, 65,…
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Jak Shell Sort funguje?

1. Předpokládejme, že musíme seřadit následující pole. Počáteční pole
2. Původní sekvenci shellu používáme (N/2, N/4,… 1jako intervaly v našem algoritmu.
   V první smyčce, pokud je velikost pole N = 8pak, jsou prvky ležící v intervalu N/2 = 4porovnány a vyměněny, pokud nejsou v pořádku.
   1. 0. prvek je porovnáván se 4. prvkem.
   2. Pokud je 0. prvek větší než 4., pak je 4. prvek nejprve uložen do tempproměnné a 0thprvek (tj. Větší prvek) je uložen na 4thpozici a prvek uložený v tempje uložen na 0thpozici. Změna uspořádání prvků v intervalu n / 2
      Tento proces pokračuje u všech zbývajících prvků. Uspořádejte všechny prvky v intervalu n / 2
3. Ve druhé smyčce se provede interval N/4 = 8/4 = 2a znovu se roztřídí prvky ležící v těchto intervalech. Uspořádání prvků v intervalu n / 4
   V tomto okamžiku můžete být zmatení. Všechny prvky v poli ležící v aktuálním intervalu jsou porovnány. Porovnávají se
   prvky na 4. a 2ndpozici. Rovněž 0thjsou porovnány prvky na 2. a pozici. Všechny prvky v poli ležící v aktuálním intervalu jsou porovnány.
4. Stejný proces pokračuje pro zbývající prvky. Uspořádejte všechny prvky v intervalu n / 4
5. Nakonec, když je interval N/8 = 8/8 =1pak, jsou prvky pole ležící v intervalu 1 seřazeny. Pole je nyní zcela tříděno. Uspořádejte prvky v intervalu n / 8

Algoritmus třídění skořápky

 shellSort (pole, velikost) pro interval i <- velikost / 2n až 1 pro každý interval "i" v poli seřadit všechny prvky v intervalu "i" konec shellSort

Python, Java a C / C ++ příklady

Python Java C C ++

# Shell sort in python def shellSort(array, n): # Rearrange elements at each n/2, n/4, n/8,… intervals interval = n // 2 while interval> 0: for i in range(interval, n): temp = array(i) j = i while j>= interval and array(j - interval)> temp: array(j) = array(j - interval) j -= interval array(j) = temp interval //= 2 data = (9, 8, 3, 7, 5, 6, 4, 1) size = len(data) shellSort(data, size) print('Sorted Array in Ascending Order:') print(data)

// Shell sort in Java programming import java.util.Arrays; // Shell sort class ShellSort ( // Rearrange elements at each n/2, n/4, n/8,… intervals void shellSort(int array(), int n) ( for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Driver code public static void main(String args()) ( int() data = ( 9, 8, 3, 7, 5, 6, 4, 1 ); int size = data.length; ShellSort ss = new ShellSort(); ss.shellSort(data, size); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) ) 

// Shell Sort in C programming #include // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); printf("Sorted array: "); printArray(data, size); ) 

// Shell Sort in C++ programming #include using namespace std; // Shell sort void shellSort(int array(), int n) ( // Rearrange elements at each n/2, n/4, n/8,… intervals for (int interval = n / 2; interval> 0; interval /= 2) ( for (int i = interval; i  = interval && array(j - interval)> temp; j -= interval) ( array(j) = array(j - interval); ) array(j) = temp; ) ) ) // Print an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Driver code int main() ( int data() = (9, 8, 3, 7, 5, 6, 4, 1); int size = sizeof(data) / sizeof(data(0)); shellSort(data, size); cout << "Sorted array: "; printArray(data, size); ) 

Složitost

Shell sort je nestabilní třídicí algoritmus, protože tento algoritmus nezkoumá prvky ležící mezi intervaly.

Časová složitost

• Složitost nejhoršího případu : Složitost nejhoršího případu pro třídění shellu je vždy menší nebo rovna . Podle Poonen Věty, v nejhorším případě složitost pro shell druhu je nebo nebo nebo něco mezi tím.O(n2)
O(n2)
Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
• Složitost nejlepších případů : O(n*log n)
  Když je pole již tříděno, celkový počet srovnání pro každý interval (nebo přírůstek) se rovná velikosti pole.
• Průměrná složitost případu : O(n*log n)
  Je to kolem .O(n1.25)

Složitost závisí na zvoleném intervalu. Výše uvedené složitosti se liší pro různé zvolené přírůstkové sekvence. Nejlepší přírůstková sekvence není známa.

Složitost prostoru:

Složitost prostoru pro třídění mušlí je O(1).

Shell Sort Applications

Třídění prostředí se používá, když:

• volání zásobníku je režie. Knihovna uClibc používá tento druh.
• rekurze překračuje limit. bzip2 kompresor to používá.
• Třídění vložení nefunguje dobře, když jsou blízké prvky daleko od sebe. Třídění skořápky pomáhá snižovat vzdálenost mezi blízkými prvky. Bude tedy proveden menší počet swapů.