You are to submit minimum three page paper describing the sorts you implemented

Question

You are to submit minimum three page paper describing the sorts you implemented and your results. Your paper should be double-spaced with margins and font according to the APA standards. Please site any references using APA. Grading Scale for Final Paper: Paper conforms to APA standards 100 points Paper less than 3 pages -20 points Paper contains grammatical errors, spelling, etc. -10 points for each infraction No references cited -10 points

This is my sorts

def partition(arr,low,high):

    i = ( low-1 )         # index of smaller element

    pivot = arr[high]     # pivot

    for j in range(low , high):

        # If current element is smaller than or

        # equal to pivot

        if   arr[j] <= pivot:

            # increment index of smaller element

            i = i+1

            arr[i],arr[j] = arr[j],arr[i]

    arr[i+1],arr[high] = arr[high],arr[i+1]

    return ( i+1 )

def quickSort(arr,low,high):

    if low < high:

        # pi is partitioning index, arr[p] is now

        # at right place

        pi = partition(arr,low,high)

        # Separately sort elements before

        # partition and after partition

        quickSort(arr, low, pi-1)

        quickSort(arr, pi+1, high)

Explanation / Answer

The algorithmic paradigm, Divide-and-Conquer, is a process of breaking the problem into subproblems that are similar to the original problem,
recursively solve the subproblems, and finally combine the solutions of the subproblems to solve the original problem.
Because divide-and-conquer solves subproblems recursively, each subproblem must be smaller than the original problem,
and there must be a base case for subproblems.

Divide-and-Conquer algorithm as having three parts:

- Divide the problem into a number of subproblems that are smaller instances of the same problem.
- Conquer the subproblems by solving them recursively. If they are small enough, solve the subproblems as base cases.
- Combine the solutions to the subproblems into the solution for the original problem.

The quicksort uses Divide-and-Conquer approach to sort the input.

In quicksort, all the real work happens in the divide step, and nothing actually happens in combine step.

Let array[0..n-1] be the array to be sorted using quicksort.
And, array[p..r] be the subarray of array[0..n-1] to be sorted.

Step 1:
   Divide by choosing any element in the subarray array[p..r]. Call this element the pivot. Rearrange the elements in array[p..r]
   so that all other elements in array[p..r] that are less than or equal to the pivot are to its left and all elements in array[p..r]
   are to the pivot's right. This procedure is called partitioning. At this point, it doesn't matter what order the elements to the left
   of the pivot are in relative to each other, and the same holds for the elements to the right of the pivot. We just care that each element
   is somewhere on the correct side of the pivot.
  
   Generally, we'll always choose the rightmost element in the subarray, array[r], as the pivot.
  
   So, for example, if the subarray consists of [9, 7, 5, 11, 12, 2, 14, 3, 10, 6], then we choose 6 as the pivot.
   After partitioning, the subarray might look like [5, 2, 3, 6, 12, 7, 14, 9, 10, 11].
   Let q be the index of where the pivot ends up.
  
   Here, since 6 is the pivot, we end up with two subarrays - namely [5, 2, 3] and [12, 7, 14, 9, 10, 11].
  
Step 2:
   Conquer by recursively sorting the subarrays array[p..q-1] (all elements to the left of the pivot, which must be less than or equal to the pivot)
   and array[q+1..r] (all elements to the right of the pivot, which must be greater than the pivot).
  
   We have 2 subarrays - [5, 2, 3] and [12, 7, 14, 9, 10, 11].
  
   To sort the subarray [5, 2, 3], we choose 3 as the pivot. After partitioning, we have [2, 3, 5]. The subarray [2], to the left of the pivot,
   is a base case when we recurse, as is the subarray [5], to the right of the pivot.
  
   To sort the subarray [12, 7, 14, 9, 10, 11], we choose 11 as the pivot, resulting in [7, 9, 10] to the left of the pivot and [14, 12]
   to the right. After these subarrays are sorted, we have [7, 9, 10], followed by 11, followed by [12, 14].
  
Step 3:
   Once the conquer step recursively sorts, all elements to the left of the pivot, in array[p..q-1], are less than or equal to the pivot
   and are sorted, and all elements to the right of the pivot, in array[q+1..r], are greater than the pivot and are sorted.
  
   After recursively sorting the subarrays to the left and right of the pivot, the subarray to the left of the pivot is [2, 3, 5],
   and the subarray to the right of the pivot is [7, 9, 10, 11, 12, 14].
   So the subarray has [2, 3, 5], followed by 6, followed by [7, 9, 10, 11, 12, 14]. The subarray is sorted.
  
  
Quicksort works in place. And its worst-case running time is as bad as selection sort's and insertion sort's: (n2).
But its average-case running time is as good as merge sort's: (nlgn).

So why think about quicksort when merge sort is at least as good?
That's because the constant factor hidden in the big- notation for quicksort is quite good.
In practice, quicksort outperforms merge sort, and it significantly outperforms selection sort and insertion sort.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.