Shell Sort
The Shell Sort’s main component is referred to as a clever division of the array data into numerous subarrays. Shell sort is defined as the “Diminishing Increment Sort.” The important component is that the items that are further apart are compared first, then the ones that are closer together, and lastly the contiguous elements are compared in the final run.
- Shell sort is initially focusing the first two data of the array, which are data with the index of “0” and data with the index “1”.
- If the data order is not appropriate then a kind of swapping will occur.
- It will consider the third element with index value 2, if this value is lesser than the first one then the element will shift.
Decision tree for Shell Sort:
In the below decision tree “Y” indicates “yes”, “N” indicates “No” and “IMP” indicates “Impossible”.
Explanation: The above figure is implemented by applying the shell sort to make a decision tree.
- Decision trees are carrying label with “Y” and “N” which indicates “yes” and “no” respectively.
- The shell sort technique is used in each separation of the decision tree, which is ordering all the values by the index values.
- Leaves are the final value at the end of the tree which is notified with “[]” square brackets.
- The above decision tree contains “24” leaves, which can be calculated by “n!” number of elements determined is “4”. Find the factorial value of four. This contains 24 leaves.
Hence, this is the implementation decision tree by applying the shell sort:
C++
// C++ code for the above approach: #include <iostream> using namespace std; // Function to shell sort void shellSort( int arr[], int n) { for ( int i = 1; i < n; i++) { int curr = arr[i]; int prev = i - 1; // Finding out the correct position to insert while (prev >= 0 && arr[prev] > curr) { arr[prev + 1] = arr[prev]; prev--; } // Insertion arr[prev + 1] = curr; } } // Function to print the array elements void printArr( int arr[], int n) { for ( int i = 0; i < n; i++) { cout << arr[i] << " " ; } cout << endl; } // Driver code int main() { int arr[] = { 5, 4, 1, 3, 2 }; int n = sizeof (arr) / sizeof (arr[0]); // Function call shellSort(arr, n); // print the final array printArr(arr, n); return 0; } |
Java
// Java code for the above approach: import java.util.*; public class BasicSorting { public static void shellSort( int arr[]) { for ( int i = 1 ; i < arr.length; i++) { int curr = arr[i]; int prev = i - 1 ; // Finding out the correct // position to insert while (prev >= 0 && arr[prev] > curr) { arr[prev + 1 ] = arr[prev]; prev--; } // Insertion arr[prev + 1 ] = curr; } } public static void printArr( int arr[]) { for ( int i = 0 ; i < arr.length; i++) { System.out.print(arr[i] + " " ); } System.out.println(); } // Drivers code public static void main(String args[]) { int arr[] = { 5 , 4 , 1 , 3 , 2 }; shellSort(arr); printArr(arr); } } |
Python3
def shellSort(arr): for i in range ( 1 , len (arr)): curr = arr[i] prev = i - 1 # Finding out the correct position to insert while prev > = 0 and arr[prev] > curr: arr[prev + 1 ] = arr[prev] prev - = 1 # Insertion arr[prev + 1 ] = curr def printArr(arr): for i in range ( len (arr)): print (arr[i], end = " " ) print () # Drivers code arr = [ 5 , 4 , 1 , 3 , 2 ] shellSort(arr) printArr(arr) |
C#
using System; public class Program { // Function to shell sort static void ShellSort( int [] arr, int n) { for ( int i = 1; i < n; i++) { int curr = arr[i]; int prev = i - 1; // Finding out the correct position to insert while (prev >= 0 && arr[prev] > curr) { arr[prev + 1] = arr[prev]; prev--; } // Insertion arr[prev + 1] = curr; } } // Function to print the array elements static void PrintArr( int [] arr, int n) { for ( int i = 0; i < n; i++) { Console.Write(arr[i] + " " ); } Console.WriteLine(); } // Driver code static void Main( string [] args) { int [] arr = { 5, 4, 1, 3, 2 }; int n = arr.Length; // Function call ShellSort(arr, n); // Print the final array PrintArr(arr, n); } } |
Javascript
// JavaScript code for the above approach: function shellSort(arr) { for (let i = 1; i < arr.length; i++) { let curr = arr[i]; let prev = i - 1; // Finding out the correct position to insert while (prev >= 0 && arr[prev] > curr) { arr[prev + 1] = arr[prev]; prev--; } // Insertion arr[prev + 1] = curr; } } function printArr(arr) { for (let i = 0; i < arr.length; i++) { console.log(arr[i] + " " ); } console.log(); } // Drivers code let arr = [5, 4, 1, 3, 2]; shellSort(arr); printArr(arr); |
Output
1 2 3 4 5
Contact Us