itsadok This question is misleading and poorly specified. In quicksort the partition method does not get called recursively and the sorting is done in-place. What is described here is a version of merge sort, taking additional O(n) storage space. There's no way to pass this question with actual quicksort, because the order of the items in the sub-arrays does not get preserved.
Read a bit on quicksort on Wikipedia.
Additionally, the fact that the first item is selected as the pivot should be specified in the question, not expected to be inferred from the example.
dunhor This question is closer to being a version of quicksort than it is to being a version of merge sort. That being said, I do agree that the question is very poor as there is no reason that the partitions need to maintain their relative ordering. Doing so does NOT require additional space as OP states, but it does make it less efficient by a factor of a constant (you can keep the first half sorted, but have to reverse the second half).
actondong First, quick sort is a divide and conquer approach, so it definitely could be solved by recursion.
Second, the purpose of keeping origin order, i think is to exactly follow the process of quick sort. The order is not mainted in current level, but by recursing down and then fi x the order bottom up.
So, i guess the purpose of this problem is to have a fundamental understanding of the process of quick sort.
jaelim I think the problem is definitely describing the mergesort algorithm with one difference being that the pivot is not at the mid instead at the beginning of an array.
liutenghou Having to declare new arrays to keep ordering does seem like it would take up O(n) additional space. From what I understand, the in-place reordering of Quicksort is one of the advantages it has over Mergesort. How would you solve this version of Quicksort without additional space while keeping the ordering?
aslgomes [deleted]
smallet The link you provided clearly specifies a recursive example of quicksort. Also it says that "Quicksort can operate in-place" which implies that it does not have to be in-place.
gauravprasad Agreed . Even i m getting confuse . It seems like the question is about the merge sort. and namd as quick sort
511narender Yes, I did in-place sorting and it doesn't preserve the order. To preserve the order we need to add few more extra conditions, which is not really needed for quick sort approach.
ravi500 Yes,your right.
alexv2 @itsadok writes that the PARTITION phase does not get called recursively, not that quicksort is not recursive.
Indeed the question asks for output that will not lend itself naturally to the recursive tree quicksort generates.
Quicksort's first partition operates on the entire array and only then on its respective left and right subarrays. The expected output mplies that recursion will start with the leftmost subarray first and bubble up from there which is more how mergesort operates, not quicksort.
GokayH I totally agree that the problem is very poorly specified. However, I do not agree with your "the partition method does not get called recursively" statement. In fact, the entire quicksort algorithm is so much easier to code recursively, when you use array indices on the partition method.
nedu1M Another well thought out challenge. I must say that QuickSort is rather a difficult topic. However, the explanations, the expected output and the exercise before this made it look easy. Again, an easy solution could be achieved by first tackling the previous exercise and following the instructions in this exercise carefully. The diagram on the expected output guides the logic behind the recursion.
The sort method - takes in an array and returns an array
- If the array length < 2, do nothing it's already sorted.
- If the array length = 2; check if first element is greater than the second element and swap.
- If the array length > 2, i. partition the array into two ii. call sort method passing the left array iii. call sort method passing the right array iv. merger the left array with the partition and the right array in this other. iv. print the resulting sub array before every return v. return the sub array.
I must say that this is the most clearer instruction of all the challenges I have tackled so far. Could it be because quick sort is rather a problematic exercise?
mnjkl12 when passing array, size also should be passed in the function call right? How do I do that? at 3-iii and 3-ii pts?
nedu1M You do not need to pass the size. Instead you can call the length property of the array to get the size
int[] mArray = new int[5]; //declaraion
int aSize = mArray.length; //this assigns the size of the array to the variable aSize.
mnjkl12 that is in java. what about C?
Tuxdude Yes for C or C++ arrays you need to pass the size parameter as well to functions/methods. The exception is if you're coding in C++, and you make use of a container data type such as vector, you can use the vectorObject.size() method to get the size.
Fistbeard I'm a bit late to the party - in C can't you pass the array, call sizeof(int), then divide sizeof(array) by sizeof(int) to get the size of the array in cells?
JohnFinn7 Not for dynamically allocated memory. sizeof is evaluated at compile time.
zhenyakornev No, you cant! in C when you pass the arr[] (arr*) it is passed by reference that is just the pointer to the beigning of array. So it doesnt give you any clue how big the array is.
blakehschwartz Your pseudo-code breakdown helped me break through some major mental hurdles caused by the way this problem was worded/examples. As others have pointed out, I think this question needs some significant overhaul to make it more useful rather than just further confusing an already confusing subject for those of us that don't come from a traditional CS background.
Thanks for your post it really helped me out!
ektong When the problem gives the function declaration already, I tend to stick with it and not change it. You can solve this problem with the given vector parameter. Notice arr is passed in as a reference, so there is no need to return back another vector. The exit case can just be detected if size < 2, don't need to swap when size == 2. I tested with a swap, but it just gave me the same answer. Hope this helps anyone stuck on this problem.
[C++]
void quickSort(vector &arr) {
// Complete this function int size = arr.size(); if (size < 2) { return; } vector <int> leftArray; vector <int> rightArray; int pivot = arr[0]; for (int i = 1; i < size; ++i) { if (arr[i] <= pivot) { leftArray.push_back(arr[i]); } else { rightArray.push_back(arr[i]); } } quickSort(leftArray); quickSort(rightArray); int index = 0; // Copy left array back into the original array for (unsigned int l = 0; l < leftArray.size(); ++l) { arr[index++] = leftArray[l]; cout << leftArray[l] << " "; } // Copy the pivot between left & right arrays arr[index++] = pivot; cout << pivot << " "; // Copy right array back into the original array for (unsigned int r = 0; r < rightArray.size(); ++r) { arr[index++] = rightArray[r]; cout << rightArray[r] << " "; } cout << endl;}
shalini24 thanx for sharing:)
davefife thanks, I was trying to make a start and end parameter as a book pseudocode shows. it sorted the array but i was having trouble outputting in the way the challenge wanted. I'm studying this way, I appreciate it.
edit an hour later, So I learned from this thanks again
folcotandiono [deleted]
ankit0905 can you explain that what does return do here
if(size<2) return
folcotandiono [deleted]
vignesh_coder to stop the algorithm
jaisreenivasan what is the need of this statement arr[index++] = leftArray[l]; ?
himanshujhamb222 Why we need to copy left array back into the original array? Why can't we just print the left array ,pivot and then left array.
I_am_Nobody I also don't get the same :/
kartikey21 awesome code really helped me in understanding quicksort :)
mitsy_24 its not giving output. :'(
im_mohsin Hey, while i ibderstood your code clearly. one thing that struck me was why didid you again copy the array into original array? Can you pls explain?
mrtako Thanks for posting your code! I'm not very strong at recursion, so I was wondering how the sorted subarrays get printed as in the test case: 2 3 1 2 3 7 8 9
VeusX Thank you! I understand
jonmcclung Is this the right way to solve this challenge in Python, or can someone improve it?
def quick_sort(*ar): p, *a = ar first, last = [], [] for i in a: if i < p: first.append(i) else: last.append(i) if len(first) > 1: first = quick_sort(*first) print(*first) if len(last) > 1: last = quick_sort(*last) print(*last) return first + [p] + last n = int(input()) p, *a = map(int, input().split()) print(*quick_sort(p, *a))neverloseks I think this is a one of good approach.
jmxdbx I did it like this, with a third list for equals, in case there were integers repeated. The solutions in python all look so much cleaner than the C++/C/Java.
def quicksort(ar): if len(ar) < 2: return ar lt, eq, rt = [], [], [] for item in ar: if item < ar[0]: lt.append(item) elif item > ar[0]: rt.append(item) else: eq.append(item) sub = quicksort(lt) + eq + quicksort(rt) print(' '.join([str(x) for x in sub])) return(sub) n = input().strip().split() ar = [int(x) for x in input().strip().split()] quicksort(ar)wattersmt Thank you. I was on the right track using code from the previous exercise but I couldn't figure out how to make it recursive.
snikketysnake I like this because it follows from the previous lesson of just craeting the partition function. Mine is the exactly the same but I literally used the partition function as a building block. It actually makes it really readable doing this for learning purposes:
#!/bin/python def quick_sort(ar): if len(ar) <= 1: return ar left, equal, right = partition(ar) newarr = quick_sort(left) + equal + quick_sort(right) print ' '.join(str(e) for e in newarr) return newarr def partition(ar): left=[] equal=[ar[0]] right=[] for elem in ar[1:]: if elem == ar[0]: equal.append(elem) elif elem < ar[0]: left.append(elem) else: right.append(elem) return left, equal, right m = input() ar = [int(i) for i in raw_input().strip().split()] quick_sort(ar)
Ardillo you don't need the '*' in the arguments of quick_sort. Also it would be great if you consider the non unique cases (even if it is said there wont be) and you can make use of built-in functions such as filter. Take a look on my Python3 solution:
def quick_sort(pivot, arr): lists = [[], [pivot], []] [(lists[0] if n<pivot else lists[2] if n>pivot else lists[1]).append(n) for n in arr] for i in filter(lambda x: len(lists[x]) > 1, [0, 2]): lists[i] = quick_sort(lists[i].pop(0), lists[i]) print(*lists[i]) return sum(lists, []) __ = input() pivot, *arr = [int(n) for n in input().split()] print(*quick_sort(pivot, arr))
BigJin @jonmcclung Thanks for your code sharing. I learned alot. I tried to improve your code as following:
def quick_sort(ar): p, *a = ar first, last = [], [] for i in a: if i < p: first.append(i) else: last.append(i) if len(first) > 1: first = quick_sort(first) if len(last) > 1: last = quick_sort(last) kth_sorted = first + [p] + last print(*kth_sorted) return kth_sorted def main(): input() arr = list(map(int, input().strip().split())) quick_sort(arr) main()
Inuyasha_ What is '*' here?
abhinav_0293 I used a different partition function than the one you guys are using i think my output for first test case is
1 2 1 2 3 8 9 7 8 9 1 2 3 5 7 8 9. Just like Quicksort1-Partition which checks for variations in partition shouldn't this do the same?
tkg97 My output is also same 1 2 1 2 3 8 9 7 8 9 1 2 3 5 7 8 9 and i think its fundamentally correct; what here has been done is wrong. As when we will first apply algo we will get 3 2 1 5 7 9 8 whereas in this diagram they are showing it differently
Rakesh882 stabilizing the quicksort..i.e., don't change the order of quick sort
AjoyBhatia I get the same order, too. I am not going to try getting the solution maintaining whatever order the checker is expecting. In the previous exercise, the checker was not strict about the order. Why here? My solution is more efficient, so just moving to some other problem.
VanitaW I understand what you are saying. I have written Quicksort before in a course but not the way this problem statement wants it. I will just come back to this one later.
rorua Same issue here. The previous Quick Sort question accounted for different partitioning functions. So should this one.
Sort 163 Discussions, By:
Please Login in order to post a comment