Scribd Logo
Upload

Welcome to Scribd!

  • 3 views

    4. Sorting

    Uploaded by

    vaunarora589
    Sorting algorithm

    Copyright:

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

    4. Sorting

    Uploaded by

    vaunarora589
    3 views28 pages
    Sorting algorithm

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Sorting algorithm

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    3 views28 pages

    4. Sorting

    Uploaded by

    vaunarora589
    Sorting algorithm

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 28

    Sorting Algorithms

    The Sorting Problem

    • Input:

    – A sequence of n numbers a1, a2, . . . , an

    • Output:

    – A permutation (reordering) a1’, a2’, . . . , an’ of the input

    sequence such that a1’ ≤ a2’ ≤ · · · ≤ an’

    2
    Selection Sort
    • Idea:
    – Find the smallest element in the array
    – Exchange it with the element in the first position
    – Find the second smallest element and exchange it with
    the element in the second position
    – Continue until the array is sorted
    • Disadvantage:
    – Running time depends only slightly on the amount of
    order in the file

    3
    Example
    8 4 6 9 2 3 1 1 2 3 4 9 6 8

    1 4 6 9 2 3 8 1 2 3 4 6 9 8

    1 2 6 9 4 3 8 1 2 3 4 6 8 9

    1 2 3 9 4 6 8 1 2 3 4 6 8 9

    4
    Selection Sort Algorithm

    5
    Analysis of Selection Sort

    6
    Bubble Sort
    • Idea:
    – Repeatedly pass through the array
    – Swaps adjacent elements that are out of order

    i
    1 2 3 n

    8 4 6 9 2 3 1
    j

    • Easier to implement, but slower than Insertion


    sort

    7
    "Bubbling Up" the Largest Element
    • Traverse a collection of elements
    – Move from the front to the end
    – “Bubble” the largest value to the end using pair-
    wise comparisons and swapping

    1 2 3 4 5 6

    77 42 35 12 101 5
    "Bubbling Up" the Largest Element
    • Traverse a collection of elements
    – Move from the front to the end
    – “Bubble” the largest value to the end using pair-
    wise comparisons and swapping

    1 2 3 4 5 6
    42Swap
    77 77
    42 35 12 101 5
    "Bubbling Up" the Largest Element
    • Traverse a collection of elements
    – Move from the front to the end
    – “Bubble” the largest value to the end using pair-
    wise comparisons and swapping

    1 2 3 4 5 6

    42 35Swap35
    77 77 12 101 5
    "Bubbling Up" the Largest Element
    • Traverse a collection of elements
    – Move from the front to the end
    – “Bubble” the largest value to the end using pair-
    wise comparisons and swapping

    1 2 3 4 5 6

    42 35 12Swap12
    77 77 101 5
    "Bubbling Up" the Largest Element
    • Traverse a collection of elements
    – Move from the front to the end
    – “Bubble” the largest value to the end using pair-
    wise comparisons and swapping

    1 2 3 4 5 6

    42 35 12 77 101 5

    No need to swap
    "Bubbling Up" the Largest Element
    • Traverse a collection of elements
    – Move from the front to the end
    – “Bubble” the largest value to the end using pair-
    wise comparisons and swapping

    1 2 3 4 5 6

    42 35 12 77 5 Swap101
    101 5
    “Bubbling” All the Elements

    1 2 3 4 5 6
    42 35 12 77 5 101
    1 2 3 4 5 6
    35 12 42 5 77 101
    1 2 3 4 5 6
    N-1

    12 35 5 42 77 101
    1 2 3 4 5 6
    12 5 35 42 77 101
    1 2 3 4 5 6
    5 12 35 42 77 101
    Bubble Sort Algorithm

    15
    Analysis of Bubble Sort

    16
    Improvement in Bubble Sort

    17
    Improvement in Bubble Sort

    18
    Insertion Sort
    • Idea: like sorting a hand of playing cards
    – Start with an empty left hand and the cards facing
    down on the table.
    – Remove one card at a time from the table, and insert
    it into the correct position in the left hand
    • compare it with each of the cards already in the hand, from
    right to left
    – The cards held in the left hand are sorted
    • these cards were originally the top cards of the pile on the
    table

    19
    Insertion Sort

    To insert 12, we need to


    make room for it by moving
    first 36 and then 24.

    20
    Insertion Sort

    21
    Insertion Sort

    22
    Insertion Sort

    input array

    5 2 4 6 1 3

    at each iteration, the array is divided in two sub-arrays:

    left sub-array right sub-array

    sorted unsorted

    23
    Insertion Sort

    24
    INSERTION-SORT

    0 1 2 3 4

    2 4 5 3 1

    25
    Analysis of INSERTION-SORT

    26
    Program of Selection Sort

    27
    Bubble Sort

    28

    You might also like