Question

Answer in python 3 and can you please include a screenshot of the code and the output

Problem 4 (Quicksort)

For this problem you must implement the recursive quicksort algorithm covered in lecture to sort points based on their distance from the point (0, 0). Crete a Python file called quicksort.py and implement a function called quicksort(list) that does the following: COMP 1005/1405A – S19 – A5 Due Saturday, June 15th at 11:59 PM

3

1. Takes a 2D list argument that contains information representing x/y points in 2D space. Each element in the list will be a list with 2 items – an x and a y coordinate. For example, the list could be [ [0, 1], [2, 1], [3, 3], [1, 1], … ]

2. Performs an in-place sort (i.e., does not create a new list, but modifies the original) using the quicksort algorithm. This must sort the 2D list such that points with lower Euclidean distance to the origin (0, 0) appear earlier in the list. In this case, you are comparing distances instead of directly comparing list values – it may be useful to implement and use a distance calculation function. Note – the Euclidean distance of a point (x, y) from the origin (0, 0) can be calculated with the following equation:

distance(x,y) = √

Next > < Previous

Sort answers by oldest

• Votes
• Oldest
• Newest

Homework Answers

Answer #1

CODE:

# 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
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 )

# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort
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)

# Driver code to test above
arr = []
m = int(input("How many points you would want to input: "))
print("Enter the points: ")
for _ in range(m):
arr.append(list(map(int, input().split())))
n = len(arr)
print("List before sorting:", end=" ")
print(arr)
quickSort(arr,0,n-1)
print("List after sorting:", end=" ")
print(arr)

OUTPUT:

Windows PowerShell PS F:\Python> python . \prac15.py How many points you would want to input: 6 Enter the points: 5 4 2 3 1 3 1 1 2 2 List before sorting: [[5, 4], [2, 3], [1, 3], [1, 1], [0, 0], [2, 2]] List after sorting: [[0, 0], [1, 1], [1, 3], [2, 2], [2, 3], [5, 4]] PS F:\Python>

PLEASE MAKE SURE TO LIKE THE ANSWER. THANKS SO MUCH IN ADVANCE :)

Know the answer?

Add Answer to:

Answer in python 3 and can you please include a screenshot of the code and the...

Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Log In

Sign Up

Post as anonymous

Post Your Answer

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.

Similar Homework Help Questions

• please help with python Write a well-documented, Python program, hmwk305.py that implements the Selection-Sort algorithm. Selection...

  please help with python Write a well-documented, Python program, hmwk305.py that implements the Selection-Sort algorithm. Selection Sort segments the list into sorted and unsorted elements. The algorithm continues to remove the smallest element of the unsorted list and adds it to the sorted segment. Implement the algorithm that accepts an unsorted list and returns a sorted one - in ascending order. 5 3 8 4 6 Initial List Minimum Swaps Position: Sorted List Length 1 Minimum Swaps Position: Sorted List...

• Here is the code given for this problem: **And please do this in Python** def mergesort(mlist): if len(mlist)<2: ret...

  Here is the code given for this problem: **And please do this in Python** def mergesort(mlist): if len(mlist)<2: return mlist else: mid=len(mlist)//2 return merge(mergesort(mlist[:mid]),mergesort(mlist[mid:])) Problem 1 (30 points) stable merge sort Consider the following unsorted list of integers containing duplicates where the relative position of each duplicated integer in the unsorted list is noted as a subscript. For example, 1, is at a smaller index than 12. The subscript is ignored when comparing two values since it would not actually...

• Language C++ (Please include a short description & Screenshot of output) Implement a Priority...

  Language C++ (Please include a short description & Screenshot of output) Implement a Priority queue using a SORTED list. Use Quick sort after adding a new node. Example of quick sort below. Adopt to your program the code below. #include <iostream> void quickSort(int a[ ], int first, int last); int pivot(int a[], int first, int last); void swap(int& a, int& b); void swapNoTemp(int& a, int& b); void print(int array[], const int& N); using namespace std; int main() { int test[]...

• Pleass write Java Program with comments. For this peoblem it supposed to create ur own list of po...

  Pleass write Java Program with comments. For this peoblem it supposed to create ur own list of points, then use that list to find the closest point. A list of points and the points have x and y values such as [(1,2),(3,5),(6,7),....] that’s just example. Implement the algorithm to meet the following requirements Define a class named Pair with data fields pl and p2 to represent two points and a method named getDistance) that returns the distance between the two...

• Can you please explain when you pick the correct answer of these questions, briefly as to...

  Can you please explain when you pick the correct answer of these questions, briefly as to why the answer was picked. Thankyou. Language used here is python 3 1-3 2 points) Which graphical object will be shown in foreground on the canvas? rec = Rectangle (150, canvas.add (rec) sqr = square (100) canvas.add (sqr) rec.setDepth (50) sqr.setDepth (50) 75) (1) Rectangle (2) Square (3) Canvas (4) Circle (2 points) 1-4 (2 points) What happens if you don't call the close0...

• please use python thanks will rate!! x + Run C Code Validate Implement the function step_random_walk_20(x_coords,...

  please use python thanks will rate!! x + Run C Code Validate Implement the function step_random_walk_20(x_coords, Y_coords) below, which should take two arrays of equal length containing the x-andy- coordinates for some number of particles. We'll use a very simple random walk algorithm • For each particle, choose a random angle between 0 and 2 • The particle moves by 1 unit of distance in the direction given by d.o. It is displaced by (Ax, Ay) (cos, sino). We'll do...

• CAN YOU PLEASE DO ONLY NUMBER 4.......PLEASE AND THANK YOU University of Windsor School of Computer...

  CAN YOU PLEASE DO ONLY NUMBER 4.......PLEASE AND THANK YOU University of Windsor School of Computer Science - Summer 2020 COMP-2650-91: Computer Architecture I: Digital Design Lab-3 Posted: June 17, 2020 05:30 PM Due: June 24, 2020 05:30 PM You must show your work for every question! 1. Simplify the lollowing Boolean expressions to a minimum number of literals: (2x3 = 6 points) (a) a'be + ab + abc + abc (b) (a' +(a ++) 2. Draw logic diagrams of...

• Implement these in Python 3 preferably. Task: Implement the following algorithms to solve the Stock Span...

  Implement these in Python 3 preferably. Task: Implement the following algorithms to solve the Stock Span Problem using the ADT for a Stack in ython. The implementation of the ADT of a Stack (10 points) Implementation of computeSpans1 (20 points) Implementation of computeSpan2 (30 points) Provide the derived computational complexity of both computeSpans1 and computeSpans2 (40 points) Algorithm computeSpans1 (P) Input: an n-element list P of numbers such that P[i] is the prices of the stock on day I Output:...

• Python. Just work in the def sierpinski. No output needed. Will give thumbs up for any attempt beginning this code. Your task is to implement this algorithm in Python, returning a random collection of...

  Python. Just work in the def sierpinski. No output needed. Will give thumbs up for any attempt beginning this code. Your task is to implement this algorithm in Python, returning a random collection of inum-100, 000 points. You should then plot the points to see the structure. Please complete the following function: def sierpinski (po, v, f, inum) The four arguments are ·po the initial point. You may assume this is the origin, i.e., po = [0, 0] . v:...

Answer 1

CODE:

# 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
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 )

# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort
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)

# Driver code to test above
arr = []
m = int(input("How many points you would want to input: "))
print("Enter the points: ")
for _ in range(m):
arr.append(list(map(int, input().split())))
n = len(arr)
print("List before sorting:", end=" ")
print(arr)
quickSort(arr,0,n-1)
print("List after sorting:", end=" ")
print(arr)

OUTPUT:

Windows PowerShell PS F:\Python> python . \prac15.py How many points you would want to input: 6 Enter the points: 5 4 2 3 1 3 1 1 2 2 List before sorting: [[5, 4], [2, 3], [1, 3], [1, 1], [0, 0], [2, 2]] List after sorting: [[0, 0], [1, 1], [1, 3], [2, 2], [2, 3], [5, 4]] PS F:\Python>

PLEASE MAKE SURE TO LIKE THE ANSWER. THANKS SO MUCH IN ADVANCE :)