Solution Library

Quicksort Algorithm to Complete given Trace-Multiple Choice Question

Question

Consider the following quicksort algorithm

Quicksort(first, last)

{IF (first < last) // There is more than one item

splitVal = data[first];

splitPoint = Split(splitVal);

left = first + 1;

right = last;

WHILE (left <= right)

{Increment left until data[left] > splitVal OR left > right;

Decrement right until data[right] < splitVal OR left > right;

IF(left < right)

Swap data[left] and data[right]

}

splitPoint = right;

Swap data[first] and data[splitPoint];

Quicksort(first, splitPoint - 1);

Quicksort(splitPoint + 1, last)

}

Each recursive call to the Quicksort function acts on a portion of the array to be sorted. Illustrate how the algorithm works on the data by completing the trace below. For each call of Quicksort give the index values for first and last as well as the value (splitVal) used as a pivot value. Also show the state of the array being sorted after the evaluation of all the Quicksort functions applied to the array.

You may not need to complete all the tables below.

 

 

Download Full Solution

Comments

  • HWA
    Rasha

    this is a very good website

  • HWA
    maani

    I have 50 questions for the same test your page is showing only 28

  • HWA
    joeanne

    hi can you please help or guide me to answer my assignments. thanks

  • HWA
    joeanne

    hi can anyone help or guide me to my assignments. thanks

  • HWA
    Monik


  • HWA
    Cristina

    This solution is perfect ...thanks

  • HWA
    Janete

    Hello Allison,I love the 2nd image that you did! I also, had never heard of SumoPaint, is something that I will have to exolpre a bit! I understand completely the 52 (or so) youtube videos that you probably watched. Sometimes they have what you want, sometimes they don't! However, it is always satisfying when you are able to produce something that you have taught yourself. Great job!Debra 0 likes

  • HWA
    Sandeep

    Perfect bank of solution. 

  • HWA
    Oxana

    great !

  • HWA
    Paul Brandon-Fritzius

    thanks for the quick response. the solution looks good. :)

  • HWA
    tina Johnson

    thnx for the answer. it was perfect. just the way i wanted it. 

  • HWA
    Giuseppe

    works fine.