A message from our CEO about the future of Stack Overflow and Stack Exchange. Read now.

# Questions tagged [sorting]

the algorithmic problem of ordering a set of elements with respect to some ordering relation.

645 questions
Filter by
Sorted by
Tagged with
16 views

### What is an $O(n \log(n))$ binary sorting algorithm with a guaranteed low scaling constant on the run-time?

Let $O_c(f(n))$ denote that $c$ is the scaling constant for the run-time (e.g. $\text{run time} \leq c\cdot f(n) + B$ if $n$ is large enough) The absolute lower limit on the run-time for a binary ...
28 views

### If I walk through list and delete every out-of-order element I come across, on average how many elements will be left?

I have a uniformly randomly permuted list of length $n$. I walk through the list element-by-element, and delete an element if it's out-of-order (compared to the previous in-order elements of the list)....
16 views

### Whats the name of the library for dynamically choosing a sorting algorithm?

I got tired of googling for it, IIRC Facebook or Google created a library that explored the data before deciding which algorithm to use, I thought it was called F15 or something. it made some insights ...
32 views

### Hypothetical Situation for sorting in $O(n)$ using median finding machine that works in $O(\sqrt{n})$

In a hypothetical world, we have a machine that can find median of $n$ numbers in $O(\sqrt{n})$. (Of course this machine is not real). Can we use this machine to sort an array in $O(n)$? I don'...
30 views

### Selection Sort vs Merge Sort

I recently wrote a written test for the recruitment of Scientists/Engineers in ISRO(Indian Space Research Organization) few days back and the following question appeared in the test. Of the following ...
69 views

### Sorting algorithm

I want to know from this picture which one is bubble sort, insertion sort and selection sort? My answer is: bubble sort algorithm, insertion sort algorithm, selection sort algorithm. Is it this ...
40 views

### Algorithm for sorting pairs of items

I have a real world problem where I have a list of nodes. Each ones contains a name and the name of the node before it in order. I am trying to devise an algorithm to sort these in order. The problem ...
381 views

### Minimum number of swaps in sorting sequence

Given an array of N integer elements (not necessarily distinct), what is the minimum number of swaps (not necessarily adjacent) needed to sort the array? I've been struggling with this problem for a ...
94 views

### Given n sorted arrays with size k select one element from every array such that the sum of the elements is minimum and the sum of their indices is k+1

So if $k = 3$ and $n = 2$ and we select the element $a_1$ of the first array then we have to select $a_2$ from the second array. If we select the element $a_1$ then also $a_2$ must be ...
168 views

### Complexity of cyclic sort

I have this algorithm ("cyclic sort") to sort an array which contains unique numbers from 1 to $n$: ...
257 views

### Sorting a large list of test scores

You have a large list (say N > 10000) of test scores which you would like to sort. The test scores are between 1 and 100. What is quickest way to sort the list? First thought. We have a O(N log N) ...
68 views

### Formal definition of stable sorting algorithm

Suppose $a$ is an array and $cmp$ is a "compare function" that is a function which outputs $true / false$ values. I say that an algorithm $A$ which takes in input $a$ and $cmp$ is a stable sorting ...
28 views

...
26 views

### Given an unsorted list of $n$ items, how many random comparisons are needed on average to be able to sort the list?

There is an unsorted list of $n$ items $x_1, \ldots, x_n$. Until you can sort the list, you are given one of the ${n \choose 2}$ possible binary comparisons uniformly at random (with replacement). On ...
66 views

### Which sort algorithm to choose given two specific arrays?

Interview question: Given array A which contains only odd numbers and array B which contains only even numbers, explain which sort algorithm would you choose. I said merge sort. I thought that ...
90 views

38 views

### Is it possible to determine if 2 arrays contain the same elements (ignoring duplicates) in faster than O(n log n) time?

So given 2 arrays of equal length, is it possible to determine whether the 2 arrays contain the same elements (ignoring duplicates and where those elements have a total order relation) with time ...
18 views

### Is SelectionSort faster than QuickSort in the worst case scenario?

Is SelectionSort faster than QuickSort in the worst-case scenario? QuickSort, in the worst case, allegedly does $n^2$ comparisons. And SelectionSort, if I am not mistaken, always does $n^2/2$ ...
49 views

### Improve algorithmic complexity

We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do: ...
12 views

### Sorting using k stacks with operation poppush(original stack, adjacent other stack)

I've been trying to read about sorting algorithms on stacks optimizing the amount of push and pops. One of a number of related probems I'm interested in can be formalized like that: There is a set of ...
86 views

### Perfect Halver Construction?

A sorting network is a circuit-based approach to sorting, built out of CompareExchange gates, which compute the function: $$\mathsf{CompareExchange}(x,y) = (\min(x,y), \max(x,y))$$ The input to the ...
76 views

9 views

### How to define the stability (or convergence) of a ordering of a list of node

I have a problem which requires ordering nodes in a graph based on some given statistics. However, the given statistics of each node may be very hard to compute. Thus, I will use some sampling ...