Question

In: Computer Science

Apply one round of partition function in Quicksort on the following sequence: 32 41 92 13...

Apply one round of partition function in Quicksort on the following sequence: 32 41 92 13 75 18 26 87 53 57

Solutions

Expert Solution

Pseudo code for partition()

/* This function takes last element as pivot, places
   the pivot element at its correct position in sorted
    array, and places all smaller (smaller than pivot)
   to left of pivot and all greater elements to right
   of pivot */
partition (arr[], low, high)
{
    // pivot (Element to be placed at right position)
    pivot = arr[high];  
 
    i = (low - 1)  // Index of smaller element

    for (j = low; j <= high- 1; j++)
    {
        // If current element is smaller than the pivot
        if (arr[j] < pivot)
        {
            i++;    // increment index of smaller element
            swap arr[i] and arr[j]
        }
    }
    swap arr[i + 1] and arr[high])
    return (i + 1)
}

Related Solutions

Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers,...
Following is the algorithm of Quicksort for sorting an array of integers in ascending order. Partition(numbers, lowIndex, highIndex) {    midpoint = lowIndex + (highIndex - lowIndex) / 2    pivot = numbers[midpoint]    done = false    while (!done) {       while (numbers[lowIndex] < pivot)          lowIndex++       while (pivot < numbers[highIndex])          highIndex--       if (lowIndex >= highIndex) {          done = true       }       else {          temp = numbers[lowIndex]          numbers[lowIndex] = numbers[highIndex]          numbers[highIndex] = temp                 lowIndex++          highIndex--       }    }    return highIndex } Quicksort(numbers, lowIndex, highIndex) {    if (lowIndex...
41 112 14 38 67 92 142 13 28 41 67 86 38 97 135 128...
41 112 14 38 67 92 142 13 28 41 67 86 38 97 135 128 13 33 20 78 35 58 135 46 29 24 77 84 36 49 143 38 75 41 39 38 40 29 106 56 33 30 105 23 72 121 38 111 19 41 A. Create frequency table (include  include class interval, frequency, relative frequency and cumulative relative frequency. ) B. Create Frequency Polygon
13-32 (Objectives 13-4, 13-6, 13-7) The following are parts of a typical audit for a company...
13-32 (Objectives 13-4, 13-6, 13-7) The following are parts of a typical audit for a company with a fiscal year-end of July 31. Understand internal control and assess control risk. Perform substantive analytical procedures for accounts payable. Confirm accounts payable. Perform tests of controls and substantive tests of transactions for the acquisition and payment and payroll and personnel cycles. Perform other tests of details of balances for accounts payable. Perform tests for review of subsequent events. Accept the client. Issue...
13. Which of the following statements does not apply to a vacation home that is rented...
13. Which of the following statements does not apply to a vacation home that is rented out for less than 15 days during the year? a. None of the rental income is reported b. Expenses must be divided between personal use and rental use c. Real estate taxes are treated as an itemized deduction d. Casualty losses are only deductible if the taxpayer itemizes deductions e. All of the above apply 14. A single taxpayer has $130,000 of AGI before...
13. Which of the following statements does not apply to a vacation home that is rented...
13. Which of the following statements does not apply to a vacation home that is rented out for less than 15 days during the year? a. None of the rental income is reported b. Expenses must be divided between personal use and rental use c. Real estate taxes are treated as an itemized deduction d. Casualty losses are only deductible if the taxpayer itemizes deductions e. All of the above apply 14. A single taxpayer has $130,000 of AGI before...
Write a function flipSwitches that accepts one argument, a sequence of upper or lower case letters...
Write a function flipSwitches that accepts one argument, a sequence of upper or lower case letters (the sequence can either be a str or a list, if you write your code correctly, it shouldn’t matter). This is a sequence of switches, uppercase means to turn a switch on, and lowercase to turn a switch off.   For example, ‘A’ means to turn the switch ‘A’ on, and ‘a’ means to turn the switch ‘A’ off.   (Turning an on switch on again,...
what sequence of numbers would be printed if the following function were executed with the value...
what sequence of numbers would be printed if the following function were executed with the value of N being 0? def xxx (N): print (N) if (N < 5): xxx (N + 2) print (N)   
During an infectious process, which of the following apply to the specific function of the membrane...
During an infectious process, which of the following apply to the specific function of the membrane attack complex (MAC, C5b-9) Induce vasodilation of blood vessels Opsonize the pathogen Induce of the release of interferon from mast cells Increase the rate of phagocytosis None of the above apply to the specific function of the MAC complex   The predominant protective maternal antibody found in breast milk and other secretions is IgM IgG IgD IgS IgE None of the answers are correct Hematopoiesis...
The following is based on the DNA sequence and one of the oligos from the previous...
The following is based on the DNA sequence and one of the oligos from the previous problem set, which are reproduced below: 5'...GGAGCTTCATGCTAGTTGCAATAGC..[1,150 bp]..CGTGGCACGTATAGCGCTATCATTA...3'       oligo-B: CATGCTAGTTGC      a) If oligo-B is used as a primer for (Sanger) DNA sequencing, which type of dideoxynucleotide would be found on the “first” (shortest) chain to terminate synthesis? b) If oligo-B is used a sequencing primer, what the total length (number of nucleotides) of the SHORTEST DNA chain that would have a dideoxy-G (ddG, 2',3'-dideoxyguanosine)...
Exactly one of the following statements is true. Which one? Select one: a. Every convergent sequence...
Exactly one of the following statements is true. Which one? Select one: a. Every convergent sequence is monotonic. b. Every Cauchy sequence is monotonic. c. Every Cauchy sequence is bounded. d. None of the other statements is true. e. Every monotonic sequence converges
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT