Example for Negative set of numbers not shown

#1

Hi !
I was trying a quick sort program:
import random

length = int(input())

string_input = input()
num_list = [int(num) for num in string_input.split(" ") ]

print(num_list)

def partitionRandom(arr, low, high):
if low == high:
return

randomPivot = random.randrange(low, high)

arr[low], arr[randomPivot] = arr[randomPivot], arr[low]
return partition(arr, low, high)

def partition(arr, low, high):
if low == high:
return

pivot = low
i = (low + 1)
for j in range(low+1, high+1):
    if arr[j] <= arr[pivot]:
        arr[i], arr[j] = arr[j], arr[i]
        i += 1
arr[pivot], arr[i-1] = arr[i-1], arr[pivot]
return (i-1)

def quick_sort(arr, low, high):
if low < high:
pivotIndex = partitionRandom(arr, low, high)

    quick_sort(arr, low, pivotIndex-1)
    quick_sort(arr, pivotIndex+1, high)

quick_sort(num_list, 0, length-1)

for num in num_list:
print(num, end=" ")

But this one fails in the negative test case, which is unknown, when submitting, it shows to check for negative numbers, my code works locally, I am unable to check where it fails.

Please have a look once…

#2

Hey @manmeetkaur0175, I would be happy to check your code. Just do me a favour by uploading your .ipynb file or .py file on google drive and sharing the link over here. It’s difficult to understand python code from the text editor without indentation.

Thanks ! :slightly_smiling_face:

#3
#4

Hey @manmeetkaur0175, your first test case is giving run error right ?..I checked your code. You have implemented Lomuto partition technique or you say random pivoting. But if you get a very large input and you use random partitioning , it can create problems while sorting the array. I would strongly recommend you to implement normal quick sort without random pivoting and then see the results.

Your both test cases will pass for sure. This question test cases does not contain any negative numbers, so leave them for the time being.

I hope this clears your doubt ! :+1:
Please mark the doubt as resolved in your doubts section :slightly_smiling_face:
Happy Learning ! :slight_smile:

#5

I tried using the simple quick sort algorithm again, but still, it shows run Error, any insights as on what does this exactly mean…

#6

I believe simple quick sort works for both test cases, atleast for me. Can you share your code once again for me to check ?

Happy Learning ! :slight_smile:

#7
#8

Hey @manmeetkaur0175, so I checked your code thoroughly. The only problem I was able to debug was in this line :

num_list = [int(num) for num in temp_list.split(" ")]

Please replace this line by

num_list = [int(num) for num in temp_list.split()]

This would help you solve this issue.
I hope this clears your doubt ! :+1:
Please mark the doubt as resolved in your doubts section ! :slightly_smiling_face:
Happy Learning ! :slight_smile:

#9

Hey @manmeetkaur0175, so your random partitioning code should also work now on both test cases. It was the input format which was creating problem.

Thank you for sharing both the codes.
Keep Learning ! :slightly_smiling_face:

#10

Thanks a lot, the issue was in that line only :slight_smile: