- Quicksort 2 - Sorting
- Discussions

# Quicksort 2 - Sorting

# Quicksort 2 - Sorting

itsadok + 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.

dunhor + 3 comments 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 + 0 comments 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 + 0 comments 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 + 0 comments 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 + 0 comments [deleted]smallet + 0 comments 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 + 0 comments Agreed . Even i m getting confuse . It seems like the question is about the merge sort. and namd as quick sort

511narender + 0 comments 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 + 0 comments Yes,your right.

alexv2 + 0 comments @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 + 0 comments 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 + 1 comment 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 + 1 comment 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 + 1 comment 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 + 1 comment that is in java. what about C?

Tuxdude + 1 comment 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 + 2 comments 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 + 0 comments Not for dynamically allocated memory. sizeof is evaluated at compile time.

zhenyakornev + 0 comments 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.

ektong + 11 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;`

}

shalini24 + 0 comments thanx for sharing:)

davefife + 0 comments 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 + 0 comments [deleted]ankit0905 + 2 comments can you explain that what does return do here

if(size<2) return

folcotandiono + 0 comments [deleted]vignesh_coder + 0 comments to stop the algorithm

jaisreenivasan + 0 comments what is the need of this statement arr[index++] = leftArray[l]; ?

himanshujhamb222 + 1 comment 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 + 0 comments I also don't get the same :/

kartikey21 + 0 comments awesome code really helped me in understanding quicksort :)

mitsy_24 + 0 comments its not giving output. :'(

im_mohsin + 0 comments 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 + 0 comments 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 + 0 comments Thank you! I understand

jonmcclung + 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))`

neverloseks + 0 comments I think this is a one of good approach.

jmxdbx + 2 comments 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 + 0 comments 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 + 0 comments 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 + 0 comments 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 + 0 comments @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_ + 0 comments What is '*' here?

abhinav_0293 + 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?tkg97 + 1 comment 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 + 0 comments stabilizing the quicksort..i.e., don't change the order of quick sort

AjoyBhatia + 1 comment 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 + 0 comments 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 + 0 comments Same issue here. The previous Quick Sort question accounted for different partitioning functions. So should this one.

ankur_sharma + 3 comments Solution in JAVA :- public class Solution {

`static int partition(int ar[], int minpos, int maxpos) { int p = ar[minpos]; ArrayList<Integer> leftlist = new ArrayList<Integer>(); ArrayList<Integer> rightlist = new ArrayList<Integer>(); for(int i = minpos+1 ; i <= maxpos; i++) { if(ar[i] > p) rightlist.add(ar[i]); else leftlist.add(ar[i]); } copy(leftlist,ar,minpos); int ppos = leftlist.size()+minpos; ar[ppos] = p; copy(rightlist,ar,ppos+1); return minpos + leftlist.size(); } static void copy(ArrayList<Integer> list, int ar[], int startIdx) { for(int num : list) { ar[startIdx++] = num; } } static void quickSort(int ar[], int minpos, int maxpos) { if(minpos >= maxpos) return; int pos = partition (ar,minpos,maxpos); quickSort(ar,minpos,pos-1); quickSort(ar,pos+1,maxpos); printArray(ar,minpos, maxpos); } static void quickSort(int[] ar) { quickSort(ar,0,ar.length-1); }`

static void printArray(int[] ar,int start, int end) { for(int i = start; i <= end;i++) { System.out.print(ar[i]+" "); } System.out.println(""); }

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] ar = new int[n]; for(int i=0;i<n;i++){ ar[i]=in.nextInt(); } quickSort(ar); }`

}

arvindtheace + 1 comment Thank you for such an elegant solution :)

ankur_sharma + 3 comments thanks, pls share your code also which can help others .

arvindtheace + 0 comments I think your solution is the best. cheers!

DineshChv + 0 comments [deleted]DineshChv + 0 comments Thank You Man. I don't know how to do quick sort, I learnt it from your code. Instead of creating number of methods, u can write it in one method itself. Best part in ur code is the print array statement. I'm a bit confused to print the answer. Modifing the same code of urs as:

`public class Solution { static void quickSort(int ar[], int minpos, int maxpos){ if(minpos >= maxpos) return; int p = ar[minpos]; ArrayList<Integer> leftlist = new ArrayList<Integer>(); ArrayList<Integer> rightlist = new ArrayList<Integer>(); for(int i = minpos+1 ; i <= maxpos; i++) { if(ar[i] > p) rightlist.add(ar[i]); else leftlist.add(ar[i]); } int ppos=minpos; for(int num : leftlist) ar[ppos++] = num; ar[ppos++] = p; for(int num : rightlist) ar[ppos++] = num; quickSort(ar,minpos,minpos + leftlist.size()-1); quickSort(ar,minpos + leftlist.size()+1,maxpos); printArray(ar,minpos, maxpos); } static void printArray(int[] ar,int start, int end) { for(int i = start; i <= end;i++) System.out.print(ar[i]+" "); System.out.println(""); } public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[] ar = new int[n]; for(int i=0;i<n;i++){ ar[i]=in.nextInt(); } quickSort(ar,0,n-1);`

}

}

brc1988 + 0 comments Thanks for the solution. I was scratching my head on how to print the array.

achuthakrishnan + 0 comments Is this solution optimal? Will it not call multiple times to sort numbers?

ashwanitanwar + 0 comments I used JAVA.

import java.util.*; public class Solution {

static ArrayList quickSort(Integer[] ar) {`int p=ar[0]; ArrayList<Integer> left=new ArrayList<>(); ArrayList<Integer> right=new ArrayList<>(); ArrayList<Integer> equal=new ArrayList<>(); for(int num:ar) { if(num==p) equal.add(num); else if(num>p) right.add(num); else left.add(num); } if(left.size()>1) left=quickSort(left.toArray(new Integer[left.size()])); if(right.size()>1) right=quickSort(right.toArray(new Integer[right.size()])); left.addAll(equal); left.addAll(right); Integer array[]=left.toArray(new Integer[left.size()]); printArray(array); return left; }`

static void printArray(Integer[] ar) { for(int n: ar){ System.out.print(n+" "); } System.out.println(""); }

`public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); Integer[] ar = new Integer[n]; for(int i=0;i<n;i++){ ar[i]=in.nextInt(); } quickSort(ar); }`

}

Yuusuf + 0 comments C++;

//Quicksort 2 - Sorting #include <iostream> using namespace std; int subFunc_quickSort_partition(int *arr, int startIndex, int endIndex){ int pivot = arr[startIndex]; int pivotIndex = startIndex; for(int i=startIndex+1 ; i<=endIndex ; i++){ if(arr[i]<pivot){ int tempNum = arr[i]; for(int j=i ; j>pivotIndex ; j--) arr[j] = arr[j-1]; arr[pivotIndex] = tempNum; pivotIndex++; } } return pivotIndex; } void func_quickSort(int *arr, int startIndex, int endIndex){ if(startIndex>=endIndex) return; int pivotindex = subFunc_quickSort_partition(arr,startIndex,endIndex); func_quickSort(arr,startIndex,pivotindex-1); func_quickSort(arr,pivotindex+1,endIndex); for(int a=startIndex ; a<=endIndex ; a++) cout << arr[a] << " "; cout<<endl; } int main (){ int arraySize = 0; cin >> arraySize; int *arr = new int[arraySize]; for(int a=0 ; a<arraySize ; a++) cin >> arr[a]; func_quickSort(arr,0,arraySize-1); }

vandana_1212 + 0 comments I have sorted the array however, I am a bit confused regarding the output. I didn't quite understand the meaning of the subarrays

tanuj011 + 0 comments I realised going through the discussions for this problem that my approach is a bit different to that being suggested by the others.

This being my first attempt at Quick Sort would appreciate constructive comments

import java.util.Iterator; import java.util.List; import java.util.Scanner; import java.util.Vector;

public class QuickSort2_Sorting {

`static List<Integer> QuickSort(List<Integer> arr) { int n=arr.size(); List<Integer> left = new Vector<Integer>(); List<Integer> right = new Vector<Integer>(); int pivot=0; if(n<2) return arr; else { pivot = arr.get(0); Iterator<Integer> i = arr.iterator(); int x =0; while(i.hasNext()){ x = i.next(); if(x > pivot) { right.add(x); } else if( x < pivot) { left.add(x); } } } left = QuickSort(left); right = QuickSort(right); left.add(pivot); left.addAll(right); printArray(left); return left; } static void printArray(List<Integer> ar) { for(int n: ar){ System.out.print(n+" "); } System.out.println(""); } public static void main(String args[]) { Scanner scan = new Scanner(System.in); int n = scan.nextInt(); List<Integer> arr = new Vector<Integer>(); for(int i=0;i<n;i++) { arr.add(scan.nextInt()); } scan.close(); QuickSort(arr); }`

}

Sort 157 Discussions, By:

Please Login in order to post a comment