Scribd Logo
Upload

Welcome to Scribd!

  • 24 views

    Shell Sort: Louis Severino Romano CCS 613

    Uploaded by

    LOUIS SEVERINO ROMANO
    The document summarizes several sorting algorithms: 1) Shell Sort sorts by comparing elements that are a certain gap apart and decreasing the gap over multiple passes. 2) Merge Sort divides the array into halves, recursively sorts each half, and then merges the sorted halves. 3) Counting Sort uses an auxiliary array to count the occurrences of each value and uses this to place elements in the final array. 4) Quicksort chooses a pivot element and partitions the array into subarrays of smaller and larger elements, recursively sorting each subarray. 5) Heapsort transforms the array into a max-heap and removes elements from the root to build the sorted array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd

    Shell Sort: Louis Severino Romano CCS 613

    Uploaded by

    LOUIS SEVERINO ROMANO
    24 views5 pages
    The document summarizes several sorting algorithms: 1) Shell Sort sorts by comparing elements that are a certain gap apart and decreasing the gap over multiple passes. 2) Merge Sort divides the array into halves, recursively sorts each half, and then merges the sorted halves. 3) Counting Sort uses an auxiliary array to count the occurrences of each value and uses this to place elements in the final array. 4) Quicksort chooses a pivot element and partitions the array into subarrays of smaller and larger elements, recursively sorting each subarray. 5) Heapsort transforms the array into a max-heap and removes elements from the root to build the sorted array.

    Original Title

    Sorting

    Copyright

    © © All Rights Reserved

    Available Formats

    DOCX, PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    The document summarizes several sorting algorithms: 1) Shell Sort sorts by comparing elements that are a certain gap apart and decreasing the gap over multiple passes. 2) Merge Sort divides the array into halves, recursively sorts each half, and then merges the sorted halves. 3) Counting Sort uses an auxiliary array to count the occurrences of each value and uses this to place elements in the final array. 4) Quicksort chooses a pivot element and partitions the array into subarrays of smaller and larger elements, recursively sorting each subarray. 5) Heapsort transforms the array into a max-heap and removes elements from the root to build the sorted array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    24 views5 pages

    Shell Sort: Louis Severino Romano CCS 613

    Uploaded by

    LOUIS SEVERINO ROMANO
    The document summarizes several sorting algorithms: 1) Shell Sort sorts by comparing elements that are a certain gap apart and decreasing the gap over multiple passes. 2) Merge Sort divides the array into halves, recursively sorts each half, and then merges the sorted halves. 3) Counting Sort uses an auxiliary array to count the occurrences of each value and uses this to place elements in the final array. 4) Quicksort chooses a pivot element and partitions the array into subarrays of smaller and larger elements, recursively sorting each subarray. 5) Heapsort transforms the array into a max-heap and removes elements from the root to build the sorted array.

    Copyright:

    © All Rights Reserved
    Download as DOCX, PDF, TXT or read online from Scribd
    Download as docx, pdf, or txt
    of 5

    Louis Severino Romano

    CCS 613
    Shell Sort
    Orignal

    30 15 18 28 35 46 5 8

    Gap=3
    30 28 5 15 28 5
    15 35 8 18 35 8
    18 46 30 46
    After 3 sort

    15 28 5 18 35 8 30 46

    Gap=2
    15 35 5 8
    28 8 15 30
    5 30 18 35
    18 46 28 46
    After 2 sort

    5 8 15 30 18 35 28 46

    After 1 sort

    5 8 15 18 28 30 35 46

    Merge Sort

    30 15 18 28 35 46 5 8

    30 15 18 28 35 46 5 8

    30 15 18 28 35 46 5 8

    30 15 18 28 35 46 5 8

    15 30 18 28 35 46 5 8
    15 18 28 30 5 8 35 46

    5 8 15 18 28 30 35 46

    Counting Sort

    Array A[ ] stores the initial data to be sorted.

    2 5 8 7 5 5 4 3 8 7 1 2 1 2 3

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14

    Array C[ ] is used to count the occurrences of the data values

    2 3 2 1 3 2 2

    0 1 2 3 4 5 6 7 8

    C[i] – 1

    2,1,0 5,4,3,2 7,6,5 8,7 11,10,9,8 11 13,12,11 15,14,13

    0 1 2 3 4 5 6 7 8

    Array B[ ] is used to store the final, sorted, list.

    1 1 2 2 2 3 3 4 5 5 5 7 7 8 8

    0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

    Quick Sort
    Pivot =30

    30 15 18 28 35 46 5 8
    0 1 2 3 4 5 6 7

    Compare all values to the pivot


    If less than to the pivot place left partition if it is greater than to the right partition else if it is equal you insert
    either to the left or right partition.
    30

    30 15 18 28 35 46 5 8

    The shaded block is sorted.


    Pivot =15 in the left partition. Let us sort first the left partition

    15 18 28 5 8 30 46 35

    15

    15 18 28 5 8 30 46 35

    Pivot 28

    5 8 15 28 18 30 46 35

    pivot 46

    5 8 15 18 28 30 46 35

    5 8 15 18 28 30 35 46

    Heap Sort

    30 15 18 28 35 46 5 8

    30
    15 18

    28 35 46 5

    Heapify(Max Heap) 46

    35 30

    28 15 18 5

    8
    Remove the root: remove the rightmost leaf at the deepest level and use it for the new root then reheap

    35 30

    28 15 18 5

    46

    Final Output 5
    8 15

    18 28 30 35

    46

    5 8 15 18 28 30 35 46

    You might also like