Shell Sort Algorithm

Shell saralash (Shell Sort) — bu qo'shish orqali saralash (Insertion Sort) algoritmining umumlashtirilgan va ancha tezlashtirilgan variantidir. Dastlab bir-biridan uzoqda joylashgan elementlar saralanadi, so'ngra qadam-baqadam elementlar orasidagi interval (oraliq masofa) qisqartirib boriladi.

Oraliq masofani qisqartirish uchun turli ketma-ketliklardan foydalaniladi. Shell saralashida ishlatiladigan mashhur oraliq ketma-ketliklari:

• Shell'ning asl ketma-ketligi: N/2, N/4, ..., 1
• Knuth qadamlari: 1, 4, 13, ..., (3^k - 1) / 2
• Sedgewick qadamlari: 1, 8, 23, 77, 281, 1073, ...
• Hibbard qadamlari: 1, 3, 7, 15, 31, 63, 127, 255, 511, ...
• Papernov & Stasevich qadamlari: 1, 3, 5, 9, 17, 33, 65, ...
• Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, ...

[!NOTE] Shell saralashining amaliy samaradorligi va tezligi tanlangan oraliq ketma-ketligiga bevosita bog'liqdir.

Shell saralash qanday ishlaydi?

Keling, quyidagi massivni Shell'ning asl ketma-ketligi (N/2, N/4, ..., 1) orqali saralashni tahlil qilamiz:

1. Dastlabki massiv:

Dastlabki massiv (Initial array)

2. Massiv hajmi N = 8. Birinchi qadamda interval = N / 2 = 4 oraliqda joylashgan elementlar o'zaro taqqoslanadi va agar ular noto'g'ri tartibda bo'lsa, o'rinlari almashtiriladi:
   • 0-indeksdagi element 4-indeksdagi bilan taqqoslanadi.
   • Agar 0-element kattaroq bo'lsa, ularning o'rni almashtiriladi.

n/2 (4) oraliqdagi elementlarni qayta tartiblash

Bu jarayon 4 oraliqdagi barcha qolgan elementlar uchun takrorlanadi:

n/2 oraliqdagi barcha elementlar tartiblandi

3. Ikkinchi siklda interval N / 4 = 8 / 4 = 2 ga teng bo'ladi va 2 ta qadam masofadagi elementlar saralanadi:

n/4 (2) oraliqdagi elementlarni qayta tartiblash

Bu yerda 4- va 2-o'rindagi elementlar, shuningdek 2- va 0-o'rindagi elementlar taqqoslanadi. Hozirgi intervalda turgan barcha elementlar zanjir bo'ylab tekshiriladi:

Joriy oraliqda joylashgan barcha elementlar taqqoslanadi

Jarayon qolgan elementlar bo'yicha ham davom ettiriladi:

n/4 oraliqdagi barcha elementlar qayta tartiblandi

4. Nihoyat, interval N / 8 = 8 / 8 = 1 bo'lganda, oddiy Insertion Sort kabi qo'shni elementlar saralanadi. Lekin avvalgi qadamlar tufayli massiv deyarli saralangan holatga kelib qolganligi sababli, oxirgi bosqich juda oz sonli almashtirishlar bilan bir zumda yakunlanadi:

n/8 (1) oraliqda yakuniy tartiblash va to'liq saralangan massiv

Shell saralash algoritmining soxta kodi

shellSort(array, size)
  for interval i <- size / 2 down to 1 (har qadamda i /= 2)
    for each interval "i" in array
      sort all elements at interval "i" using insertion sort
end shellSort

Dasturiy namunalar

// Go tilida Shell Sort algoritmi
package main

import "fmt"

func shellSort(arr []int) {
	n := len(arr)

	// n/2, n/4, n/8, ... 1 oraliqlar bo'yicha qisqartirib boramiz
	for interval := n / 2; interval > 0; interval /= 2 {
		for i := interval; i < n; i++ {
			temp := arr[i]
			j := i

			// interval masofadagi elementlarni o'rniga suramiz
			for j >= interval && arr[j-interval] > temp {
				arr[j] = arr[j-interval]
				j -= interval
			}
			arr[j] = temp
		}
	}
}

func main() {
	data := []int{9, 8, 3, 7, 5, 6, 4, 1}
	fmt.Println("Dastlabki massiv:", data)

	shellSort(data)

	fmt.Println("Saralangan massiv:", data)
}

Shell saralashning murakkabligi

Shell saralashining murakkabligi tanlangan oraliqlar ketma-ketligiga qarab sezilarli farq qilishi mumkin. Masalan, Pratt ketma-ketligida eng yomon holat murakkabligi O(n * (log n)^2) gacha pasayadi.

Shell saralashning qo'llanilishi

• Rekursiyadan foydalanish qimmat bo'lgan va chaqiruvlar steki cheklangan o'rnatilgan tizimlarda (embedded systems).
• O'rta hajmdagi massivlarni qo'shimcha xotira sarflamasdan (O(1) xotirada) tezkor saralashda.