Scribd
Upload
2 views4 pages

Sort Example

The document provides a detailed explanation of the Merge Sort and Shell Sort algorithms, including step-by-step examples of sorting an array. It illustrates the process of dividing and merging in Merge Sort, as well as the gap-based sorting method in Shell Sort. The final sorted arrays for both algorithms are presented, showcasing their effectiveness.

Uploaded by

pkalpanas1974
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
2 views4 pages

Sort Example

The document provides a detailed explanation of the Merge Sort and Shell Sort algorithms, including step-by-step examples of sorting an array. It illustrates the process of dividing and merging in Merge Sort, as well as the gap-based sorting method in Shell Sort. The final sorted arrays for both algorithms are presented, showcasing their effectiveness.

Uploaded by

pkalpanas1974
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

Merge Sort Example :Consider the array: [38, 27, 43, 3, 9, 82, 10]

Step 1: Divide the Array


[38, 27, 43, 3, 9, 82, 10]

/ \
[38, 27, 43] [3, 9, 82, 10]

/ \ / \
[38] [27,43] [3,9] [82,10]

/ \ / \ / \
[27] [43] [3] [9] [82] [10]
Step 2: Merge the Subarrays

Merge sorted pairs:

[27] + [43] → [27, 43]

[3] + [9] → [3, 9]

[82] + [10] → [10, 82]

Now: [38] + [27,43] → [27,38,43]

[3,9] + [10,82] → [3,9,10,82]


Step 3: Final Merge

Merge:

[27,38,43] + [3,9,10,82]

Comparison process:

3, 9, 10, 27, 38, 43, 82


Final Sorted Array
[3, 9, 10, 27, 38, 43, 82]

defmerge_sort(arr):
iflen(arr) > 1:
mid = len(arr) // 2

left = arr[:mid]
right = arr[mid:]

merge_sort(left)
merge_sort(right)

i=j=k=0
# Merge the two halves
whilei<len(left) and j <len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1

# Copy remaining elements of left half


whilei<len(left):
arr[k] = left[i]
i += 1
k += 1

# Copy remaining elements of right half


while j <len(right):
arr[k] = right[j]
j += 1
k += 1

# Main Program
arr = [38, 27, 43, 3, 9, 82, 10]

print("Original Array:", arr)

merge_sort(arr)

print("Sorted Array:", arr)


Output
Original Array: [38, 27, 43, 3, 9, 82, 10]
Sorted Array: [3, 9, 10, 27, 38, 43, 82]
#shell sort example program
defshell_sort(arr):
n = len(arr)
gap = n // 2

while gap > 0:


for i in range(gap, n):
temp = arr[i]
j=i

while j >= gap and arr[j - gap] > temp:


arr[j] = arr[j - gap]
j -= gap

arr[j] = temp

gap //= 2

# Input
arr = [64, 34, 25, 12, 22, 11, 90]

print("Original Array:", arr)

shell_sort(arr)

print("Sorted Array:", arr)

Original Array: [64, 34, 25, 12, 22, 11, 90]


Sorted Array: [11, 12, 22, 25, 34, 64, 90]

Example

Input:

[23, 12, 1, 8, 34, 54, 2, 3]

Pass 1 (Gap = 4):

[23, 12, 1, 3, 34, 54, 2, 8]

Pass 2 (Gap = 2):

[1, 3, 2, 8, 23, 12, 34, 54]

Pass 3 (Gap = 1):

[1, 2, 3, 8, 12, 23, 34, 54]

Final Output:[1, 2, 3, 8, 12, 23, 34, 54]

You might also like