Sortir Kerang

Dalam tutorial ini, Anda akan mempelajari cara kerja shell sort. Selain itu, Anda akan menemukan contoh kerja pengurutan shell di C, C ++, Java dan Python.

Sortir shell adalah algoritma yang pertama-tama mengurutkan elemen jauh satu sama lain dan secara berturut-turut mengurangi interval antara elemen yang akan diurutkan. Ini adalah versi umum dari semacam penyisipan.

Dalam sortir shell, elemen pada interval tertentu diurutkan. Interval antar elemen dikurangi secara bertahap berdasarkan urutan yang digunakan. Performa jenis shell bergantung pada jenis urutan yang digunakan untuk larik masukan yang diberikan.

Beberapa urutan optimal yang digunakan adalah:

  • Urutan asli Shell: N/2 , N/4 ,… , 1
  • Penambahan Knuth: 1, 4, 13,… , (3k - 1) / 2
  • Penambahan Sedgewick: 1, 8, 23, 77, 281, 1073, 4193, 16577… 4j+1+ 3·2j+ 1
  • Peningkatan Hibbard: 1, 3, 7, 15, 31, 63, 127, 255, 511…
  • Peningkatan 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 Shell Sort Bekerja?

  1. Misalkan, kita perlu mengurutkan array berikut. Array awal
  2. Kami menggunakan urutan asli shell (N/2, N/4,… 1) sebagai interval dalam algoritme kami.
    Dalam loop pertama, jika ukuran array N = 8kemudian, elemen yang terletak pada interval N/2 = 4akan dibandingkan dan ditukar jika tidak berurutan.
    1. Unsur ke-0 dibandingkan dengan unsur ke-4.
    2. Jika elemen ke-0 lebih besar dari yang ke-4, maka elemen ke-4 disimpan terlebih dahulu dalam tempvariabel dan 0thelemen (yaitu elemen yang lebih besar) disimpan di 4thposisi dan elemen yang disimpan tempdisimpan di 0thposisi. Susun ulang elemen pada interval n / 2
      Proses ini berlangsung untuk semua elemen yang tersisa. Susun ulang semua elemen pada interval n / 2
  3. Dalam loop kedua, interval N/4 = 8/4 = 2diambil dan elemen yang terletak pada interval ini diurutkan. Susun ulang elemen-elemen pada interval n / 4
    Anda mungkin bingung pada saat ini. Semua elemen dalam larik yang terletak pada interval saat ini akan dibandingkan.
    Elemen-elemen di 2ndposisi dan keempat dibandingkan. Elemen di 0thposisi ke-2 dan juga dibandingkan. Semua elemen dalam larik yang terletak pada interval saat ini akan dibandingkan.
  4. Proses yang sama berlangsung untuk elemen yang tersisa. Susun ulang semua elemen pada interval n / 4
  5. Akhirnya, ketika intervalnya N/8 = 8/8 =1maka elemen array yang terletak pada interval 1 diurutkan. Array sekarang sudah diurutkan sepenuhnya. Susun ulang elemen pada interval n / 8

Algoritma Penyortiran Shell

 shellSort (array, size) untuk interval i <- size / 2n turun menjadi 1 untuk setiap interval "i" dalam array sortir semua elemen pada interval "i" end shellSort

Contoh Python, Java dan C / C ++

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

Kompleksitas

Pengurutan shell adalah algoritma pengurutan yang tidak stabil karena algoritma ini tidak memeriksa elemen-elemen yang terletak di antara interval.

Kompleksitas Waktu

  • Kompleksitas Kasus Terburuk : kurang dari atau sama dengan Kompleksitas kasus terburuk untuk pengurutan shell selalu kurang dari atau sama dengan . Menurut Poonen Teorema, kompleksitas kasus terburuk untuk shell semacam ini atau atau atau sesuatu di antara.O(n2)
    O(n2)
    Θ(Nlog N)2/(log log N)2)Θ(Nlog N)2/log log N)Θ(N(log N)2)
  • Kompleksitas Kasus Terbaik : O(n*log n)
    Ketika array sudah diurutkan, jumlah total perbandingan untuk setiap interval (atau kenaikan) sama dengan ukuran array.
  • Kompleksitas Kasus Rata-rata : O(n*log n)
    Ada di sekitar .O(n1.25)

Kompleksitas bergantung pada interval yang dipilih. Kompleksitas di atas berbeda untuk urutan kenaikan berbeda yang dipilih. Urutan kenaikan terbaik tidak diketahui.

Kompleksitas Ruang:

Kompleksitas ruang untuk jenis shell adalah O(1).

Aplikasi Sortir Shell

Jenis shell digunakan ketika:

  • memanggil tumpukan adalah overhead. Perpustakaan uClibc menggunakan jenis ini.
  • rekursi melebihi batas. kompresor bzip2 menggunakannya.
  • Jenis penyisipan tidak bekerja dengan baik bila elemen penutup berjauhan. Jenis shell membantu dalam mengurangi jarak antara elemen dekat. Dengan demikian, jumlah swappings yang akan dilakukan akan lebih sedikit.

Artikel yang menarik...