We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Quicksort 2 - Sorting
- Discussions
Quicksort 2 - Sorting
Quicksort 2 - Sorting
+ 0 comments Python 3
I think is the most elegant solution
def quickSort(arr): if len(arr) < 2: return arr else: pivot = arr[0] less = [i for i in arr[1:] if i <= pivot] greater = [i for i in arr[1:] if i > pivot] return quickSort(less) + [pivot] + quickSort(greater)
+ 1 comment Anyone else's output not matching even though it is partitioning and sorting the way it suppposed to?
+ 1 comment **Java Solution: **
static void quickSort(int[] ar, int start, int end) { if (start < end) { int pi = partition(ar, start, end); quickSort(ar, start, pi - 1); quickSort(ar, pi + 1, end); printArray(ar, start, end); } } static int partition(int[] ar, int start, int end) { int pivot = ar[start]; int i = start + 1, j = end; while (i <= j) { if (ar[i] > pivot && ar[j] < pivot) { int temp = ar[i]; ar[i] = ar[j]; ar[j] = temp; } while (i <= end && ar[i] < pivot) i++; while (j > start && ar[j] > pivot) j--; } ar[start] = ar[j]; ar[j] = pivot; return j; }
+ 1 comment How's this Quicksort implmentation if we're not doing partition in-place?
This is my solution, it gives different result than what's expected for this question but this is much more optimal because we don't use any extra auxiliary space.
def quickSort(arr, start, end): if(start < end): pIndex = partition(arr, start, end) quickSort(arr, start, pIndex - 1) quickSort(arr, pIndex + 1, end) if(len(arr[start: end + 1]) > 1): print(" ".join(arr[start: end + 1])) def partition(arr, start, end): pivot = arr[start] pIndex = start + 1 for i in range(start + 1, end+1): if(arr[i] < pivot): arr[i], arr[pIndex] = arr[pIndex], arr[i] pIndex += 1 arr[start], arr[pIndex-1] = arr[pIndex-1], arr[start] return pIndex - 1 n = int(input()) arr = input().split() quickSort(arr, 0, n-1)
+ 0 comments Use the Quicksort algorithm to sort the entire array
def sorting(ar):
if len(ar) <= 1: return ar left, equal, right = partition(ar) merging_arr = sorting(left) + equal + sorting(right) print (' '.join(str(e) for e in merging_arr)) return merging_arr
def partition(ar):
left, equal, right=[],[ar[0]],[] for elem in ar[1:]: if elem < ar[0]: left.append(elem) elif elem == ar[0]: equal.append(elem) else: right.append(elem) return left, equal, right
if name == 'main':
n = input() ar = list(map(int,input().rstrip().split())) sorting(ar)
Load more conversations
Sort 187 Discussions, By:
Please Login in order to post a comment