Scribd Logo
Upload

Welcome to Scribd!

  • 135 views

    Quick Sort: Algorithms and Data Structures

    Uploaded by

    Haris Muhibic
    Quicksort is one of the most widely used sorting algorithms. It works by recursively partitioning the array around pivot points and sorting the subarrays. It has average case performance of O(n log n) but worst case of O(n^2). Variations include choosing better pivot points like the median to improve performance. Quicksort is used in many applications due to its simplicity, speed, and ability to sort in-place without extra memory.

    Copyright:

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

    Quick Sort: Algorithms and Data Structures

    Uploaded by

    Haris Muhibic
    135 views25 pages
    Quicksort is one of the most widely used sorting algorithms. It works by recursively partitioning the array around pivot points and sorting the subarrays. It has average case performance of O(n log n) but worst case of O(n^2). Variations include choosing better pivot points like the median to improve performance. Quicksort is used in many applications due to its simplicity, speed, and ability to sort in-place without extra memory.

    Original Description:

    aaadsads

    Original Title

    8.Quick Sort

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Quicksort is one of the most widely used sorting algorithms. It works by recursively partitioning the array around pivot points and sorting the subarrays. It has average case performance of O(n log n) but worst case of O(n^2). Variations include choosing better pivot points like the median to improve performance. Quicksort is used in many applications due to its simplicity, speed, and ability to sort in-place without extra memory.

    Copyright:

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

    Quick Sort: Algorithms and Data Structures

    Uploaded by

    Haris Muhibic
    Quicksort is one of the most widely used sorting algorithms. It works by recursively partitioning the array around pivot points and sorting the subarrays. It has average case performance of O(n log n) but worst case of O(n^2). Variations include choosing better pivot points like the median to improve performance. Quicksort is used in many applications due to its simplicity, speed, and ability to sort in-place without extra memory.

    Copyright:

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

    Quick Sort

    Algorithms and Data Structures

    Dino KECO
    Agenda
     quick sort
     selection
     duplicate keys
     system sorts
    Two classic sorting algorithms:
    merge sort and quick sort
    Critical components in the world’s computational infrastructure.
     Full scientific understanding of their properties has enabled us to
    develop them into practical system sorts.
     Quick sort honored as one of top 10 algorithms of 20th century in
    science and engineering.
    Quick Sort
    Basic plan.
     Shuffle the array.
     Partition so that, for some j
     entry a[j] is in place

     no larger entry to the left of j

     no smaller entry to the right of j

     Sort each subarray recursively.


    Quick Sort – important people
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].
    Quick Sort partitioning
    Repeat until i and j pointers cross.
     Scan i from left to right so long as (a[i] < a[lo]).
     Scan j from right to left so long as (a[j] > a[lo]).
     Exchange a[i] with a[j].

    When pointers cross.


     Exchange a[lo] with a[j].

    This was Sadgewick 2-way partitioning, there are other strategies like
     Dijkstra 3-way partitioning
     Bentley-McIlroy 3-way partitioning
     dual-pivot partitioning
    Quick Sort: Java code for
    partitioning
    Quick Sort: Java implementation
    Quick Sort: implementation details

     Partitioning in-place. Using an extra array makes


    partitioning easier, but is not worth the cost.
     Terminating the loop. Testing whether the
    pointers cross is trickier than it might seem.
     Equal keys. When duplicates are present, it is
    (counter-intuitively) better to stop scans on keys
    equal to the partitioning item's key.
     Preserving randomness. Shuffling is needed for
    performance guarantee.
     Equivalent alternative. Pick a random
    partitioning item in each subarray.
    Quick Sort analysis

     Best case.
    Number of compares is ~ N log N.

     Worst case.
    Number of compares is ~ ½ N2 .
    Quick Sort: practical
    improvements
    Insertion sort small subarrays.
     Even quick sort has too much overhead for tiny
    subarrays.
     Cutoff to insertion sort for ≈ 10 items

    Median of sample.
     Best choice of pivot item = median.
     Estimate true median by taking median of
    sample.
     Median-of-3 (random) items
    Selection
    Goal. Given an array of N items, find the k th smallest item.
    Ex. Min (k = 0), max (k = N - 1), median (k = N/ 2).

    Applications.
     Order statistics.

     Find the "top k."

    Use theory as a guide.


     Easy N log N upper bound. How?

     Easy N upper bound for k = 1, 2, 3. How?

     Easy N lower bound. Why?

    Which is true?
     N log N lower bound?

     N upper bound?
    Duplicate keys

     Often, purpose of sort is to bring items with equal


    keys together.
     Sort population by age.
     Remove duplicates from mailing list.
     Sort job applicants by college attended.

     Typical characteristics of such applications.


     Huge array.
     Small number of key values
    Duplicate keys
     What is the result of partitioning the following
    array (skip over equal keys)?
    Duplicate keys: partitioning
    strategies
     Bad. Don't stop scans on equal keys.
    [ ~ ½ N2 compares when all keys equal ]

     Good. Stop scans on equal keys.


    [ ~ N lg N compares when all keys equal ]

     Better. Put all equal keys in place. How?


     [ ~ N compares when all keys equal ]
     Dijkstra 3-way partitioning
    Sorting applications
    Sorting algorithms are essential in a broad variety of applications:
     Sort a list of names.

     Organize an MP3 library.


     Display Google PageRank results.
     List RSS feed in reverse chronological order.

     Find the median.


     Identify statistical outliers.
     Binary search in a database.
     Find duplicates in a mailing list.

     Data compression.
     Computer graphics.
     Computational biology.
     Load balancing on a parallel computer.
    ...
    Questions?

    You might also like