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

Given a multidimensional array, return an array containing the sum of the diagonals
Given a multidimensional array, return an array containing the sum of the diagonals.
For example:
input: [ [1, 2, 3], [4, 5, 6], [7, 8, 9] ] output: [ 7, 12, 15, 8, 3 ]
function addDiagonals(matrix) { let sum = 0; let j = matrix[0].length  1; for (let i = 0; i < matrix.length; i++, j) { sum += matrix[i][j]; sum += matrix[i][i]; } return sum; } console.log(addDiagonals([ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]));
I am able to find the sum of the diagonals. But I need to know how to go about finding the sum of each diagonal.
But I need to complete this:
function diagonalSum(matrix) { let sum = 0; let res = []; for (let i = 0; i < matrix.length; i++) { let j = matrix.length  i  1; res[i] = matrix[i][j]; console.log(`i = ${i} and j = ${j};`) } return res; } console.log(diagonalSum([ [1, 2, 3], [4, 5, 6], [7, 8, 9] ]));

3sum Solution not passing test case (Java)
I'm trying to program a solution to the 3sum question on leetcode(link: https://leetcode.com/problems/3sum/).
This is what I've done so far:
public int binary_search(int [] nums, int start, int end, int target) { if (start > end) { return 1; } int mid = (start + end) / 2; if (nums[mid] == target) { return mid; } else { if (nums[mid] < target) { return binary_search(nums, mid + 1, end, target); } else { return binary_search(nums, start, mid  1, target); } } } public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); ArrayList<List<Integer>> solution_set = new ArrayList(); Set<List<Integer>> ordered_solutions = new HashSet(); for (int i = 0; i < nums.length; i++) { if (i + 1 == nums.length) { continue; } int number_1 = nums[i]; int number_2 = nums[i+1]; int target = (number_1 + number_2); int target_index = binary_search(nums, 0, nums.length  1, target); if (binary_search(nums, 0, nums.length  1, target) != 1 && target_index != i && target_index != i+1) { List<Integer> submission = new ArrayList(); submission.add(number_1); submission.add(number_2); submission.add(target); List<Integer> ordered_submission = submission; Collections.sort(ordered_submission); if (ordered_solutions.add(ordered_submission) == true) { solution_set.add(submission); } } } return solution_set; }
The program works as follows: input is given to function threeSum which is then sorted and two following objects are created; An ArrayList that will store all nonduplicate solutions and a Set that is used to test for said duplicate solutions.
Then, the for loop sifts through the array and does the following: it adds the i and i+1 element then negates them to find the number needed to sum all three numbers to zero. With this number acquired, a binary search is conducted on the array to see if this number can be found. If it is found, a few other conditions are tested to ensure that the target index is not actually the same as index i or i+1. After that, I create two objects, a submission that includes the elements in their original order and an ordered submission. If the ordered submission is inserted into the set and the set returns true, it means it's not a duplicate and i store it in the solution_set.
My problem is as follows: My program fails with the test case [0,0,0]. I believe the target is calculated as zero, but the binary search chooses the zero which is in i+1 so the solution is rejected. Does anyone have any suggestions on how this problem can be fixed?

Implementing sorting algorithms on a List<string>
I have created some sorting algorithms inside CustomDataList class:
public void SortStudents() //sorts students alphabetically { string temp; for (int i = 0; i < students.Count; i++) { for (int j = i + 1; j < students.Count; j++) { if (string.Compare(students[i], students[j]) > 0) { temp = students[j]; students[j] = students[i]; students[i] = temp; } } Console.WriteLine(students[i]); } } public string GetMaxElement() { string tempMax = null; foreach (string element in students) { if (tempMax == null  string.Compare(tempMax, element) > 0) { tempMax = element; } } return tempMax; } public string GetMinElement() { string tempMin = null; foreach (string element in students) { if (tempMin == null  string.Compare(tempMin, element) < 0) { tempMin = element; } } return tempMin; } }
And the following code inside the Main() method:
CustomDataList customDataList = new CustomDataList(); //Add(element) customDataList.AddStudent("Jenny"); customDataList.AddStudent("Loren"); customDataList.AddStudent("Martin"); customDataList.AddStudent("Hannah"); customDataList.AddStudent("Joules"); customDataList.AddStudent("Daniel"); customDataList.AddStudent("Andy"); customDataList.AddStudent("Emilio"); customDataList.AddStudent("Ariana"); customDataList.AddStudent("Nikkita");
This code works fine, but now I need to add other sorting algorithms (for example algorithms that sort the list based on the length of the name) similar to SortStudents() method (without using .Sort() method).
I would appreciate it if you could suggest other kind of sorting and some hints about how to create that sorting algorithm.

QuickSort implementation is unpredictable for ArrayList size less than 10000
Referring to the QuickSort algorithm from the Wikipedia Lomuto partition scheme,
I have implemented this algorithm on Java using ArrayList structure such that the programme can generate an array of random numbers before running the quick sort. I have made sure the recording of the time taken is started right before the execution of the quick sort. I.e.
long startTime = System.nanoTime(); quicksort.sort(arr, 0, arr.size()  1); long endTime = System.nanoTime(); long timeTaken = endTime  startTime;
When sorting the ArrayList of size 10 and size 20, the recorded list of time taken showed that the ArrayList of size 10 took longer time than the size 20. The following image is the example of the output. The output of the time taken [52906, 30293, 45653, 99413] does not reflect the time complexity of O(n log n) at all.
Image description: Output of the QuickSort. Time taken in nanoseconds for array size 10, 20, 30, 40: 52906, 30293, 45653, 99413. Output array is in sorted order.
From the question title, by unpredictable, I mean the output of the time taken is rather random. Only when I use ArrayList of size more than 10000 that the output showed a convincing O(n log n) time complexity.
My question is: Why did such phenomenon happen?

Counter for Quicksort algorithm
My professor asked us to choose the best sorting algorithm, we chose Quicksort. The task given to us was to create a program that sorts an array of integers using the chosen algorithm but only using 1 method and to create a counter that counts how many times a line of code runs in the program to determine the fastest and best memory wise algorithm.
I know that Quicksort is great for large sets of data which gives the reason why my counter count is high but I just wanted to check if the lines where I put the counter are correct. Any suggestions?
public class JavaProgram { @FunctionalInterface public interface Func { void call(int[] arr, int i, int j); } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int counter=0; counter++; System.out.println("Enter size of array: "); counter++; int x = sc.nextInt(); counter++; System.out.println("Enter numbers in array: "); counter++; int[] numbers = new int[x]; counter++; for(int i=0;i<numbers.length;i++) { numbers[i] = sc.nextInt(); counter++; } Func swap = (int[] arr, int i, int j) > { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; }; counter++; Stack<Integer> stack = new Stack<>(); counter++; stack.push(0); counter++; stack.push(numbers.length); counter++; while (!stack.isEmpty()) { counter++; int end = stack.pop(); counter++; int start = stack.pop(); counter++; if (end  start < 2) { counter++; continue; } counter++; // partitioning part int position = start + ((end  start) / 2); counter++; int low = start; counter++; int high = end  2; counter++; int piv = numbers[position]; counter++; swap.call(numbers, position, end  1); counter++; while (low < high) { counter++; if (numbers[low] < piv) { counter++; low++; counter++; } else if (numbers[high] >= piv) { counter++; high; counter++; } else { counter++; swap.call(numbers, low, high); counter++; } } position = high; counter++; if (numbers[high] < piv) { counter++; position++; counter++; } swap.call(numbers, end  1, position); counter++; stack.push(position + 1); counter++; stack.push(end); counter++; stack.push(start); counter++; stack.push(position); counter++; } System.out.println("Sorted array: " + Arrays.toString(numbers)); counter++; System.out.println("Counter: "+counter); } }

randomized quicksort probability
Trying to understand the analysis of randomized quicksort using this paper here. specifically section 3.4.2
the probability of each xij = 1 is:
why is that?