Susun Shell

Dalam tutorial ini, anda akan belajar bagaimana cara kerja shell. Anda juga akan dapati contoh shell yang berfungsi di C, C ++, Java dan Python.

Shell sort adalah algoritma yang terlebih dahulu menyusun unsur-unsur yang berjauhan antara satu sama lain dan berturut-turut mengurangkan selang antara elemen yang akan disusun. Ini adalah versi penyisipan versi umum.

Dalam bentuk shell, elemen pada selang masa tertentu disusun. Selang antara elemen secara beransur-ansur menurun berdasarkan urutan yang digunakan. Prestasi jenis shell bergantung pada jenis urutan yang digunakan untuk array input yang diberikan.

Beberapa urutan optimum yang digunakan adalah:

  • Urutan asal Shell: N/2 , N/4 ,… , 1
  • Kenaikan Knuth: 1, 4, 13,… , (3k - 1) / 2
  • Kenaikan Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Kenaikan Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Kenaikan Papernov & Stasevich: 1, 3, 5, 9, 17, 33, 65,…
  • Pratt: 1, 2, 3, 4, 6, 9, 8, 12, 18, 27, 16, 24, 36, 54, 81… .

Bagaimana Penyusun Shell Berfungsi?

  1. Katakan, kita perlu menyusun susunan berikut. Susunan awal
  2. Kami menggunakan urutan asal shell (N/2, N/4,… 1) sebagai selang dalam algoritma kami.
    Pada gelung pertama, jika ukuran susunan pada N = 8masa itu, unsur-unsur yang terletak pada selang N/2 = 4dibandingkan dan bertukar jika tidak mengikut urutan.
    1. Unsur ke-0 dibandingkan dengan elemen ke-4.
    2. Sekiranya elemen ke-0 lebih besar daripada yang ke-4 maka, elemen ke-4 terlebih dahulu disimpan dalam temppemboleh ubah dan 0thelemen (iaitu elemen yang lebih besar) disimpan dalam 4thkedudukan dan elemen yang tersimpan di tempdalam 0thkedudukannya. Susun semula elemen pada selang n / 2
      Proses ini diteruskan untuk semua elemen yang tinggal. Susun semula semua elemen pada selang n / 2
  3. Pada gelung kedua, selang N/4 = 8/4 = 2diambil dan sekali lagi unsur-unsur yang terletak pada selang ini disusun. Susun semula elemen pada selang waktu n / 4
    Anda mungkin akan keliru pada ketika ini. Semua elemen dalam susunan yang terletak pada selang semasa dibandingkan.
    Unsur-unsur pada 2ndkedudukan ke-4 dan kedudukan dibandingkan. Unsur pada 0thkedudukan ke-2 dan kedudukan juga dibandingkan. Semua elemen dalam susunan yang terletak pada selang semasa dibandingkan.
  4. Proses yang sama berlaku untuk elemen yang tinggal. Susun semula semua elemen pada selang waktu n / 4
  5. Akhirnya, apabila selang N/8 = 8/8 =1maka elemen array yang terletak pada selang 1 disusun. Susunan kini disusun sepenuhnya. Susun semula elemen pada selang n / 8

Algoritma Susun Shell

 shellSort (array, size) untuk selang i <- size / 2n hingga 1 untuk setiap selang "i" dalam array menyusun semua elemen pada selang "i" end shellSort

Contoh Python, Java dan C / C ++

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

Kerumitan

Shell sort adalah algoritma penyortiran yang tidak stabil kerana algoritma ini tidak mengkaji unsur-unsur yang terletak di antara selang masa.

Kerumitan Masa

  • Kerumitan Kes Terburuk : kurang daripada atau sama dengan Kerumitan kes terburuk untuk jenis shell selalu kurang daripada atau sama dengan . Menurut Teorema Poonen, kerumitan kes terburuk untuk jenis shell adalah atau atau atau sesuatu di antaranya.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Kerumitan Kes Terbaik : O(n*log n)
    Apabila array sudah disusun, jumlah perbandingan untuk setiap selang (atau kenaikan) sama dengan ukuran array.
  • Kerumitan Kes Rata-rata : O(n*log n)
    Sudah hampir .O(n1.25)

Kerumitan bergantung pada selang waktu yang dipilih. Kerumitan di atas berbeza untuk urutan kenaikan yang berbeza yang dipilih. Urutan kenaikan terbaik tidak diketahui.

Kerumitan Ruang:

Kerumitan ruang untuk jenis shell adalah O(1).

Aplikasi Susun Shell

Jenis shell digunakan apabila:

  • memanggil timbunan adalah overhead. Perpustakaan uClibc menggunakan jenis ini.
  • rekursi melebihi had. pemampat bzip2 menggunakannya.
  • Jenis penyisipan tidak berfungsi dengan baik apabila elemen dekat berjauhan. Jenis shell membantu mengurangkan jarak antara elemen dekat. Oleh itu, jumlah pertukaran yang lebih sedikit akan dilakukan.

Artikel menarik...