Scribd Logo
Upload

Welcome to Scribd!

  • 31 views

    Sorting

    Uploaded by

    PurwajTiwari
    1. The document describes the partition routine, which is a useful subroutine for problems like quicksort. 2. The partition routine takes an array and pivot element and rearranges the array elements into two parts - elements less than or equal to the pivot are placed in the left part, and elements greater than the pivot are placed in the right part. 3. The document provides pseudocode for an efficient O(n) partition algorithm and walks through an example to demonstrate how it works.

    Copyright:

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

    Sorting

    Uploaded by

    PurwajTiwari
    31 views34 pages
    1. The document describes the partition routine, which is a useful subroutine for problems like quicksort. 2. The partition routine takes an array and pivot element and rearranges the array elements into two parts - elements less than or equal to the pivot are placed in the left part, and elements greater than the pivot are placed in the right part. 3. The document provides pseudocode for an efficient O(n) partition algorithm and walks through an example to demonstrate how it works.

    Original Description:

    Lecture on sorting techniques.

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    1. The document describes the partition routine, which is a useful subroutine for problems like quicksort. 2. The partition routine takes an array and pivot element and rearranges the array elements into two parts - elements less than or equal to the pivot are placed in the left part, and elements greater than the pivot are placed in the right part. 3. The document provides pseudocode for an efficient O(n) partition algorithm and walks through an example to demonstrate how it works.

    Copyright:

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

    Sorting

    Uploaded by

    PurwajTiwari
    1. The document describes the partition routine, which is a useful subroutine for problems like quicksort. 2. The partition routine takes an array and pivot element and rearranges the array elements into two parts - elements less than or equal to the pivot are placed in the left part, and elements greater than the pivot are placed in the right part. 3. The document provides pseudocode for an efficient O(n) partition algorithm and walks through an example to demonstrate how it works.

    Copyright:

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

    ESC101: Introduction to Computing

    Sorting

    Around Easter 1961, a course on ALGOL 60 was offered It


    was there that I first learned about recursive procedures and
    saw how to program the sorting method which I had earlier
    found such difficulty in explaining.
    It was there that I wrote the procedure, immodestly named
    QUICKSORT, on which my career as a computer scientist is
    founded. Due credit must be paid to the genius of the
    designers of ALGOL 60 who included recursion in their
    language and enabled me to describe my invention so
    elegantly to the world.
    I have regarded it as the highest goal of programming
    language design to enable good ideas to be elegantly
    expressed.

    C. A. R. Hoare, ACM Turing Award Lecture, 1980


    2

    Selection Sort
    Select the largest element in your array and
    swap it with the first element of the array.
    Consider the sub-array from the second
    element to the last, as your current array and
    repeat Step 1.
    Stop when the array has only one element.

    Base case, trivially sorted

    Selection Sort: Pseudo code


    selection_sort(a[], start, end) {
    if (start == end) /* base case, one elt => sorted */
    return;
    idx_max = find_idx_of_max_elt(a, start, end);
    swap(a, idx_max, start);
    selection_sort(a, start+1, end);
    }
    swap(a[], i, j) {
    tmp = a[i];
    a[i] = a[j];
    a[j] = tmp;
    }

    main() {
    arr[] = { 5, 6, 2, 3, 1, 4 };
    selection_sort(arr, 0, 5);
    /* print arr */
    }
    4

    Selection Sort
    What is the estimated run time
    when input array has n elements

    Constant
    for swap
    for find_idx_of_max_elt
    ?
    for selection_sort

    Selection Sort: Time Estimate

    Merging Two Sorted Arrays

    Merging Two Sorted Arrays


    Input: Array A of size n & array B of size m.
    Create an empty array C of size n + m.
    Variables i , j and k

    array variables for the arrays A, B and C resp.

    At each iteration

    compare the ith element of A (say u) with the jth element of


    B (say v)
    if u is smaller, copy u to C; increment i and k,
    otherwise, copy v to C; increment j and k,

    Time Estimate

    Merge Sort

    Recursive calls.
    Base case?
    n <= 1

    10

    /*Sort ar[start, , start+n-1] in place */


    void merge_sort(int ar[], int start, int n) {
    if (n>1) {
    int half = n/2;
    merge_sort(ar, start, half);
    merge_sort(ar, start+half, n-half);
    merge(ar, start, n);
    }
    int main() {
    }
    int arr[]={2,5,4,8,6,9,8,6,1,4,7};
    merge_sort(arr,0,11);
    /* print array */
    return 0;

    }
    11

    void merge(int ar[], int start, int n) {


    int temp[MAX_SZ], k, i=start, j=start+n/2;
    int lim_i = start+n/2, lim_j = start+n;
    for(k=0; k<n; k++) {
    if ((i < lim_i) && (j < lim_j)) {// both active
    if (ar[i] <= ar[j]) { temp[k] = ar[i]; i++; }
    else { temp[k] = ar[j]; j++; }
    } else if (i == lim_i) // 1st half done
    { temp[k] = ar[j]; j++; } // copy 2nd half
    else // 2nd half done
    { temp[k] = ar[i]; i++; } // copy 1st half
    }
    for (k=0; k<n; k++)
    ar[start+k]=temp[k]; // in-place
    }

    Time Estimate
    void merge_sort(int a[], int s, int n) {
    if (n>1) {
    int h = n/2;
    merge_sort(a, s, h);
    merge_sort(a, s+h, n-h);
    merge(a, s, n);
    }
    }

    Time Estimates
    Why worry
    about O(n) vs
    O(n2) vs O()
    algorithm?

    http://xkcd.com/612/

    14

    SelectionSort

    MergeSort

    Simple Search

    BinSearch
    Source: http://science.slc.edu/~jmarshall/courses/2002/spring/cs50/BigO/

    Time Estimates

    15

    Around Easter 1961, a course on ALGOL 60 was offered It


    was there that I first learned about recursive procedures and
    saw how to program the sorting method which I had earlier
    found such difficulty in explaining.
    It was there that I wrote the procedure, immodestly named
    QUICKSORT, on which my career as a computer scientist is
    founded. Due credit must be paid to the genius of the
    designers of ALGOL 60 who included recursion in their
    language and enabled me to describe my invention so
    elegantly to the world.
    I have regarded it as the highest goal of programming
    language design to enable good ideas to be elegantly
    expressed.

    C. A. R. Hoare, ACM Turing Award Lecture, 1980


    16

    QuickSort - Partition Routine


    A useful sub-routine (function) for many problems,
    including quicksort, one of the popular sorting
    methods.
    1. Partition takes an array a[] of size n and a value called the
    pivot.
    2. The pivot is an element in the array, for instance, a[0].
    3. Partition re-arranges the array elements into two parts:
    a) the left part has all elements <= pivot.
    b) the right part has all elements >= pivot.
    4. Partition returns the index of the beginning of the right part.
    Let us see an example.
    17

    1. Partition takes an array a[] of size n and a value called the


    pivot.
    2. The pivot is an element in the array, for instance, a[0].
    3. Partition re-arranges the array elements into two parts:
    a) all elements in the left part are <= pivot
    b) all elements in the right part are >= pivot
    Input Array a[], size is n : 11
    31

    10

    35

    59

    31

    25

    35

    11

    31

    59

    35

    35

    31

    Pivot element is assumed to be a[0]: 31


    0

    10

    11

    left partition

    25

    right partition
    18

    Observations

    Multiple partitions of an array are possible, even for the same


    pivot. They all would satisfy the above specification.
    Note: Partition DOES NOT sort the array. It is weaker than
    sorting. But it is useful step towards sorting (useful for other
    problems also).

    19

    1. partition(int a[], int start, int end), pivot is a[0].


    2. Partition re-arranges the array elements into two parts:
    a) the left part has all elements <= pivot
    b) the right part has all elements >= pivot
    3. Partition can return either the first index of the right part or the
    last index of the left part. (Both answers would be acceptable).
    Designing partition: Goal is to have linear time complexity,
    meaning that the number of comparisons and exchanges of items
    must be linear in the size.
    Also, we will do partition in place that is, without using extra
    arrays.

    20

    a
    31

    Designing Partition
    4

    10

    35

    59

    31

    31

    25

    35

    11

    10

    pivot
    r
    l
    1. Keep two integer variables denoting indices: l starts at the left
    end and r starts at the right end.
    2. pivot is a[0] which is 31.
    3. Value of pivot will not change during partition.
    Basic Step in Partition Loop:
    As long as a[l] < pivot, increment l by 1.
    As long as a[r] > pivot, decrease r by 1.
    If l < r, Exchange a[l] with a[r].
    advance l by 1; decrement r by 1
    21

    a
    31

    Designing Partition
    4

    10

    35

    59

    31

    31

    10

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    25

    35

    11

    Let us run this step on the


    above array
    1. First loop terminates, with l as 0.
    2. Second loop terminates
    immediately, with r as 10.

    Now we swap a[0] with a[10]

    22

    a
    0

    Designing Partition
    4

    10

    35

    59

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    25

    35

    11

    31

    Let us run this step on the


    above array

    Swap and Advance


    1. swap a[0] with a[10]
    2. Advance l to 1
    3. Decrement r to 9

    23

    a
    0

    Designing Partition
    4

    10

    35

    59

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    25

    35

    11

    31

    Let us run this step on the


    above array
    Invariant
    1. a[0]a[l-1] are all <= pivot.
    2. a[r+1]a[n-1] are all >= pivot.

    24

    a
    0

    Designing Partition
    4

    10

    11

    59

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    25

    35

    35

    31

    Let us run this step on the


    above array
    Invariant
    1. a[0]a[l-1] are all <= pivot.
    2. a[r+1]a[n-1] are all >= pivot.

    25

    a
    0

    Designing Partition
    4

    10

    11

    59

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    25

    35

    35

    31

    Let us run this step on the


    above array
    Invariant
    1. a[0]a[l-1] are all <= pivot.
    2. a[r+1]a[n-1] are all >= pivot.

    26

    a
    0

    Designing Partition
    4

    10

    11

    25

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    59

    35

    35

    31

    Let us run this step on the


    above array
    Invariant
    1. a[0]a[l-1] are all <= pivot.
    2. a[r+1]a[n-1] are all >= pivot.

    27

    a
    0

    Designing Partition
    4

    10

    11

    25

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    59

    35

    35

    31

    Let us run this step on the


    above array
    Invariant
    1. a[0]a[l-1] are all <= pivot.
    2. a[r+1]a[n-1] are all >= pivot.

    28

    a
    0

    Designing Partition
    4

    10

    11

    25

    31

    31

    pivot

    Basic Step in Partition Loop:


    As long as a[l] < pivot, increment
    l by 1.
    As long as a[r] > pivot, decrease
    r by 1.
    If l < r, Swap a[l] with a[r].
    advance l by 1; decrement r by 1

    59

    35

    35

    31

    Let us run this step on the


    above array
    Invariant
    1. a[0]a[l-1] are all <= pivot.
    2. a[r+1]a[n-1] are all >= pivot.

    29

    int partition(int a[], int start, int end) {


    int l = start, r = end, pivot = a[l];
    while (l <=end && r>=start) {
    while (a[l] < pivot && l <end) { l=l+1; }
    while (a[r] > pivot && r>start) { r=r-1; }
    if(l>=r) return r;
    else {
    swap(a, l, r);
    l = l+1; r = r-1;
    }
    }
    }

    30

    The Partition function


    We designed a function int partition(int a[], int start, int end)
    that returns an index pindex of the array a[] such that the
    following are true.
    1. all items in a[start, , pindex] are <= pivot,
    2. all items in a[pindex+1,,end] are >= pivot,
    3. Number of operations required by partition is O(n), that is
    bounded by c n for some constant c. Required only a single
    pass over the array: each element is touched once.

    Pivoting choices
    Pivot may be chosen to be any value of a[]. Some choices are
    1. Pivot is a[0]: simple choice.
    2. Pivot is some random member of a[]: randomized pivot
    choice.
    3. Pivot is the median element of a[]. This gives the most
    equal sized partitions, but is much more complicated.

    Sorting
    After the call pindex = partition(a,start,end)
    1. each element of a[start,,pindex] <= pivot.
    2. each element of a[pindex+1,,end] >= pivot.
    Suppose we wish to sort the array a[].
    To sort a[], we can sort the left partition and the right partition
    independently.

    1. sort the array a[0,,pindex], and,


    2. sort the array a[pindex+1,,n-1].
    How should we do the sorting?
    Any way we wish, but how about choosing the same
    algorithm, that is, run partition on each half again (and then
    again on smaller partsthis is recursion)

    QuickSort
    void qsort(int a[], int start, int end) {
    int pindex;
    if (start >=end) return; /* nothing to sort */
    else {
    pindex = partition(a, start, end);
    qsort(a, start, pindex);
    qsort(a, pindex+1, end);
    }
    }

    You might also like