To store what quicksort requires, O (logn) additional memory
I mean I know Wiki says it used for call stack. But what exactly stores there? For what data of algorithm of sorting in a stack the memory is required?
2 answers

i think you might find your answer here
this might not be it, but i believe the stack is used for function calls, and as the algorithm is recursive you would have lots of calls and you need the stack to save the state at each function call.
hope this helps. 
In the most of usual implementations stack stores starting and ending indexes for range that should be sorted later.
Recursive version:
int i = partition(a, l, r) here l,i => quicksort(a, l, i) and here i + 1, r => quicksort(a, i + 1, r)
Version with explicit stack (ifcondition to provide lesser stack depth):
int i = partition(a, l, r) if (i  1 > r  i) s.push(l, i  1) s.push(i + 1, r) else s.push(i + 1, r) s.push(l, i  1)
See also questions close to this topic

Getting unique combinations, in order, from a list with nonuniques
I have an issue that I just can't wrap my head around and I'm hoping someone can help me out.
Imagine the following situation:
There is a list of people which all have a name. So each person is an object with the "name" property. From that list, a random number of people is selected (so not all people are always in the selection) in random order, And each person is selected no more than once. However, names are potentially not unique: There might be more than one person in the list with the name "Smith". For this example, Let's imagine that each name is just one letter of the alphabet. So I might receive the following selection:
[V, C, R, C, F, X, R, C]
And the next time the selection might be completely different. Each element in that selection is a different person, But some of the names occur more than once.
Let's add numbers to clarify:
[V, C1, R1, C2, F, X, R2, C3]
Now I need all possible combinations of people where each name occurs only once, But respecting the sequence in which they were listed in the selection. Every unique name in the selection should be in the combination.
For instance, in this case I need:[V, C1, R1, F, X], [V, R1, C2, F, X], [V, R1, F, X, C3], [V, C1, F, X, R2], [V, C2, F, X, R2] ...
And so on. People's positions should not be changed (i.e. [C1, V, ...] would not be ok because "V" should not come after "C1").
I'm assuming I will need recursivity and some way to keep track of the names, but that's where my brain starts to melt. ;) I have found scripts to get all possible permutations in any order, but nothing like this.
Could anyone help me out?
Thanks!

Optimize bruteforce solution of searching nearest point
I have non empty Set of points scattered on plane, they are given by their coordinates. Problem is to quickly reply such queries:
Give me the point from your set which is nearest to the point A(x, y)
My current solution pseudocode
query( given_point ) { nearest_point = any point from Set for each point in Set if dist(point, query_point) < dist(nearest_point, given_point) nearest_point = point return nearest_point }
But this algorithm is very slow with complexity is
O(N)
.The question is, is there any data structure or tricky algorithms with precalculations which will dramatically reduce time complexity? I need at least
O(log N)
Update
By distance I mean Euclidean distance

Fewer line to count max int in array on Kotlin and faster than O(nlogn)?
I wonder if there a better way or idiomatic way to count the max int in an array with Kotlin and faster than O(nlogn)?
This code gives O(n) but I feel like it too long
fun countMax(n: Int, ar: Array<Int>): Int { val max = ar.max(); var countMax = 0 for(i in ar) if(i==max) countMax++ return countMax } fun main(args: Array<String>) { val scan = Scanner(System.`in`) val n = scan.nextLine().trim().toInt() val ar = scan.nextLine().split(" ").map{ it.trim().toInt() }.toTypedArray() val result = birthdayCakeCandles(n, ar) println(result) }
Sorting then counting got nlogn
val input: Scanner = if (inputFile.exists()) Scanner(inputFile) else Scanner(System.
in
)fun main(args: Array<String>) { input.nextLine() val nums = input.nextLine().split(' ').map { it.toLong() }.sorted() val s = nums.takeLastWhile { it == nums.last() }.size print(s) }
I wonder there is a shorter code and perform faster than O(nlogn)

Trying to draw each quicksort iteration on canvas
I'd like to see live quicksort iterations on a canvas.
Here is the small project I'm working on.
The problem I'm having is that it draws the initial shuffled state and the sorted state without the steps in between.
quickSort(initArray, metaLeft, metaRight) { if (initArray.length <= 1) { return initArray; } else { var left = []; var right = []; var newArray = []; var pivot = initArray.pop(); var length = initArray.length; for (var i = 0; i < length; i++) { if (initArray[i] <= pivot) { left.push(initArray[i]); } else { right.push(initArray[i]); } } // console.log([].concat(metaLeft, left, pivot, right, metaRight)); this.wait(); this.draw([].concat(metaLeft, left, pivot, right, metaRight)); var sortedLeft = this.quickSort(left, metaLeft, [pivot].concat(right, metaRight)) var sortedRight = this.quickSort(right, metaLeft.concat(sortedLeft, pivot), metaRight) return newArray.concat(sortedLeft, pivot, sortedRight); } }
I believe it is because of quicksort being recursive but I don't know why and how I could make this work.
The console.log right before the wait / draw functions apparently shows the correct steps I need to draw.

Quicksort performance (much slower than insertion??) Java
I'm new at this. I have implemented a Quicksort algorithm and I am measuring the time. It turns out WAY slower than a regular insertion sort, no matter how big the problem. I have tried to change quite a lot to try to figure out what makes it so slow but so far I can't see what the problem is. Could someone please help or give a clue?
I have one Quicksort class and one Partition class.
My code:
public class Quicksort { Partition partition = new Partition(); public void sort(int[] myList) { if (myList.length <= 1){ return; } else { quickSort(myList, 0, myList.length  1); } } public void quickSort(int[] myList, int start, int end) { int pivot = myList[(start+end)/2]; int pivotindex = partition.partitioning(myList, start, end, pivot); if (start < pivotindex1){ quickSort(myList, start, pivotindex1); } if (pivotindex < end) { quickSort(myList, pivotindex, end); } } }
My Partition class:
public class Partition { public int partitioning(int[] myList, int start, int end, int pivot){ int temp; while (start <= end){ while (myList[start] < pivot){ start++; } while (myList[end] > pivot){ end; } if (start <= end){ temp = myList[start]; myList[start] = myList[end]; myList[end] = temp; start++; end; } } return start; } }

QuickSort  trouble implementing quick sort in my SET ADT
I am trying to implement QuickSort on my set ADT and am running into an issue where I cannot figure out how to implement the quickSort function in my main
I ran gcc w after my seg. fault and am getting the following error:
table.c:232:24: error: invalid operands to binary / (have ‘int’ and ‘void *’) int n = sp>length / sp>data[0];
I also am getting the following error when I run GDB:
(.text+0x20): undefined reference to `main' collect2: error: ld returned 1 exit status
I think that the errors are coming from how I have referenced the SET *sp in the functions: partition, *quickSort, *getElements, printArray, and main
Any help is appreciated. Thank you for your time!
Code:
#include <stdlib.h> #include <assert.h> #include <stdio.h> #include <stdbool.h> #define EMPTY 0 #define FILLED 1 #define DELETED 2 struct set { int count; /*number of elements*/ int length; /*length of array */ void **data; /*array of strings */ char* flags; /*array of flags */ int (*compare)(); /* a compare function in the set */ unsigned(*hash)(); /* equivalent of strhash stored in the set */ }; typedef struct set SET; static int search(SET *sp, void *elt, bool *found); /* prototyping the search function */
. . .
// simple pointer swap function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // Big O: int partition (SET *sp, int low, int high) { int j; int pivot = sp>data[high]; // pivot position int i = (low  1); // Index of smaller element char **arr = sp>data; for (j = low; j <= high 1; j++) { // current element <= pivot if (arr[j] <= pivot) { i++; swap(&arr[i], &arr[j]); } } swap(&arr[i + 1], &arr[high]); return (i + 1); } // implements QuickSort // arr[] > Array to be sorted, // low > Starting index, // high > Ending index void *quickSort(SET *sp, int low, int high) { if (low < high) { // pi = partitioning index, arr[p] is now at right place int pi = partition(sp, low, high); // sort before and after partition quickSort(sp, low, pi  1); quickSort(sp, pi + 1, high); } } // Runtime: O(n) void *getElements(SET *sp) { assert(sp!=NULL); char **arr; int i; int lastIndex = 0; int n = sizeof(arr)/sizeof(arr[0]); arr = malloc(sizeof(void*)*sp>count); // declare array and allocate memory to be size of the number of elements for (i = 0; i < sp>length; i++) { if (sp>flags[i] == FILLED) // we only want an array of elements and not the entire thing so check if FILLED { arr[lastIndex]=sp>data[i]; // copy the data lastIndex++; } } quickSort(sp, 0, n1); } /* Function to print an array */ void printArray(SET *sp) { int i; for (i=0; i < sp>length; i++) printf("%d \n", sp>data); printf("n"); } // Driver program to test above functions int main(SET *sp) { char arr = sp>data; int n = sp>length / sp>data[0]; quickSort(sp, 0, n1); printf("Sorted array: n"); printArray(sp); return 0; }