- Quicksort 2 - Sorting
- Discussions

# Quicksort 2 - Sorting

# Quicksort 2 - Sorting

+ 8 comments 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.

+ 3 comments 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?

+ 12 comments 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;`

}

+ 5 comments 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))`

+ 3 comments 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?

Sort 176 Discussions, By:

Please Login in order to post a comment