Questions tagged [sorting]

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

Filter by
Sorted by
Tagged with
-3
votes
0answers
25 views

How do I sort this sequence of numbers 3, j, j, 4, 3, 4, 2, 4, 4, j using the counting sort method? [closed]

How do I sort this sequence of numbers 3, j, j, 4, 3, 4, 2, 4, 4, j by the counting sort method?
1
vote
0answers
32 views

Maximize the sum of weights of covered intervals

Suppose we are given $n$ open intervals $(a_1, b_1), \dots, (a_n, b_n)$, with interval $i$ being assigned a weight $w_i$ for all $i$. We are given an integer $k<n$, and we are allowed to choose $k$ ...
0
votes
1answer
31 views

Sorting N dimensional data

What would be a good choice for a key to sort a complex number $(a+ib)$ or any $n$-dimensional data for that matter. Is using the magnitude of that vector a good choice rather than using any one of ...
2
votes
1answer
43 views

Finding the smallest amount of function operations to sort an array

Let's say we have a function shift(array[], int s) which swaps the position of array[s] to array[0] and shifts all other elements to the right. For example: array = {1,2,3,4,5,6} --> shift(array, 3)...
1
vote
1answer
42 views

Examples of comparison-based algorithms that are not a sort or a search over lists

Can you share examples of comparison-based algorithms used in practice that are not a sort or a search over lists? Heapify is an example of a comparison-based algorithm that is neither a sort nor a ...
1
vote
3answers
99 views

Best-case time: comparison-based sorting on a list of size n must make n-1 comparisons (reference to proof)

I am looking for a reference to a proof that for every list of size $n$ comparison-based sorting cannot make less than $n-1$ comparisons. Do you have a reference of a book that covers it (with page ...
0
votes
2answers
24 views

Searching for sorting algorithm taking into account all possible solution of similar numbers

I need a reference for sorting algorithm where all possible orders are considered. example: if we have four values of n, and we do know there values n1(3) n2(5) n3(5) n4(10) and want to order them in ...
0
votes
0answers
34 views

Is there a difference between Heapify and Bottom-Up/Top-Down heap construction, when using array representation of binary tree?

Won't both the methods ultimately give a max/min heap? So if I am given a binary tree, as an array, and am asked to convert it to a max heap, can I just use the bottom up construction of the heap? ...
1
vote
0answers
16 views

(Branchless) Bitonic Sorting Network for a Set of Floating Point Numbers

In the past I've implemented a branchless Bitonic Sorting Network on a gpu using CUDA, for integers. I am facing a related problem: In my Order Independent Transparency implementation, I would like to ...
1
vote
1answer
31 views

How can vector angle comparison between lattice points be done without using floating-points? (Convex Hull)

Let's say I have a point $(x_0, y_0)$, and some other points $(x_1, y_1), (x_2, y_2) ... (x_n, y_n)$, such that all of them are lattice points; all have integer coordinates. Let's further assume that ...
0
votes
1answer
56 views

Quicksort with insertion sort

Okay so I have implemented quicksort with insertion, where K is a value until which the recursion occurs and then rest of the array is sorted using insertion sort. Now I am comaparing 3 different ...
0
votes
0answers
38 views

Prove the worst case runtime of the cocktail shaker sort is $\theta(n^2)$

Question: Prove the worst-case running time of the cocktail shaker sort is $θ(n^2)$ by demonstrating that the sort is $O(n^2)$ and $\Omega(n^2)$ in the worst case My attempt: I believe I am supposed ...
2
votes
1answer
57 views

List of algorithms that depend on sorting / ranking / argsorting

I am looking for a list of algorithms that depends on sorting / relative ranking / argsorting, not for a list of sorting algorithms. I want to study and illustrate the importance of fast sorting in ...
2
votes
3answers
53 views

Number of comparisons for mergesort

In their book An introduction to the Analysis of Algorithms, Flajolet and Sedgewick analyze the number of compares performed by Mergesort along the following lines. They denote by $C_N$ the number of ...
1
vote
3answers
253 views

What could be the most efficient algorithm to compare two unsorted arrays?

I have two arrays A and B of the same length n. I am looking to swap such that all the elements of array A are less than each element of B. Elements in A and B can be unsorted. Example Inputs: ...
0
votes
1answer
27 views

Average number of comparison for 3 items

What is the average number of comparisons performed when sorting 3 items? The question is based on the above picture.
0
votes
0answers
15 views

change an algo to obtain optimal run time

I have an algorithm that does the reverse of partition ...
0
votes
1answer
18 views

Proof the recurrence relation of order statistics using induction

I read order statistics from the book The Design and Analysis of Computer Algorithms", by Aho, Hopcroft, Ullman, Addison-Wesley As per the algorithm the recurrence relation given T(n)<= cn for ...
1
vote
1answer
111 views

Lower bound on comparison-based sorting of $k$-sorted arrays

In $k$-sorting array algorithms, every element is supposed to be $k$ positions from its correct positions. So with that in mind, if we used a randomized QuickSort, we will have $O(n\log{n})$. Now to ...
0
votes
1answer
29 views

Bubble sort on an already sorted collection

When I look at the following algorithm, I believe I understand how bubble sort works. ...
4
votes
2answers
558 views

Stability of QuickSort Algorithm

Def: the stability of algorithm is defined in case of the algorithm preserves same value elements while sorting as the following shows: So for this QuickSort algorithm: ...
0
votes
2answers
116 views

Complexity of sorting $k$-sorted array using QuickSort and HeapSort

Given a $k$-sorted array where each element in the array is $k$ positions from its correct position, we want to sort such array using quick sort. Generally speaking, I understand that running time is ...
0
votes
1answer
66 views

Sorting by boolean algebra (hardware) instead of algorithm (software)

Consider there's an 5 elements list that foreach element are 2-bits. Forexample [01,00,10,00,11], if the list is sorted, we hope the output like this [00,00,01,10,11] Maybe that case seems complicated,...
1
vote
2answers
120 views

Find neighbour objects in a 3d grid

I have points in a 3d world where their position is defined by 3 integers: X, Y, Z. I'm searching for an algorithm / data structure to store these points in a way I can quickly find (e.g.: O(log(N)) ...
2
votes
1answer
52 views

Why is this greedy strategy always correct for this problem?

I'm trying to solve the following problem: https://cses.fi/problemset/task/1084/ My first idea to solve this was to sort the applicants and apartments in increasing order. Then, I iterate through all ...
0
votes
1answer
37 views

Comparison sort algorithm

Consider the following algorithm: The given items are inserted one by one into a list by performing comparisons like a binary search for the right position. Example: Imagine six elements are already ...
0
votes
1answer
53 views

I made bubble_sort() function following the algorithm. But it is not working. where is my error? [closed]

This was the algorithm for bubble sort in textbook. I tried the with WHILE loop, then I tried the same with the for loop. My answer is not sorted. Why? I follow the above algorithm in Python 3.0. My ...
1
vote
2answers
69 views

Disprove sorting in O(log(n))

Assume an array $X=[x_1,...,x_n]$ is given, where each $x\in X$ is an integer. Array $X$ is sorted if $x_1 \le ... \le x_n$. Typical sorting algorithms have a worst-case performance of $\mathcal{O}(n\...
0
votes
0answers
62 views

Analyzing Hybrid Merge and Insertion Sort

We know that merge sort takes O(n log n) and insertion sort takes (n^2) for worst case. The combination of these two algorithm is to speed up and reduce key comparisons, as for a subarray with small ...
1
vote
1answer
36 views

Sorting by tournament sort

Is there somewhere a website/application/software/something where you can submit a list of string/image/audio/content/whatever and the appliance make a tournament sort by asking you question like &...
2
votes
1answer
102 views

Faster way to calculate number of passes needed for bubble sort

Is there is a faster way to calculate the number of passes (not the number of swaps) needed to complete the bubble sort than actually doing the sort (as demonstrated in the code)? E.g. 1, 2, 3 -> 1 ...
1
vote
0answers
23 views

Finding max values at a point given a list of ranges

In coding competitions I usually see problems that involve dealing with values in given ranges. A typical example is, given a list of 3-tuples defined as so ...
0
votes
0answers
30 views

Is there such thing as average space complexity? If so, what is it for Timsort?

I was reading about Timsort's use in Python and wondered what the time and space complexities were which are dispalyed on the wikipedia page. The Wikipedia page lists average time complexity for ...
0
votes
0answers
36 views

Which sorting algorithm is this?

I was trying to implement bubble sort in python, but turns out it's not bubble sort, it's faster than bubble sort. Can somebody please enlighten on me what sorting algorithm I implemented? ...
-1
votes
1answer
72 views

Sorting elements into k subarrays

Given are $n$ integer numbers in the range $0$ to $5n$. A SubSort algorithm organizes the numbers into $k=n/100$ sets, $s_{1}$, …, $s_{k}$ , each containing $100$ numbers, such that the following ...
1
vote
2answers
282 views

Sorting an array with x sorted subarrays

I have been given two True/False questions regarding sorting an array. The questions are as following - Question A Given an array A with 3n keys that contains three equal parts A[1,n], A[n+1,2n] and ...
0
votes
1answer
62 views

Lower bound on worst-case time complexity of all sorting algorithms neglecting reading input and accessing elements time

We know that the worst-case time complexity of any comparison sorting algorithm is $\Omega(n\log n)$. Is there a lower bound on the worst-case running time of sorting algorithms of any type? Not just ...
0
votes
1answer
47 views

Question on Erickson 'momselect' algorithm

In the Erickson Algorithms textbook (file:///C:/Users/G068078/OneDrive%20-%20Kaiser%20Permanente/Algorithms_Technique_and_Theory_CS_388G/Undergraduate_CS331/Algorithms-JeffE.pdf) it has pseudocode for ...
0
votes
1answer
25 views

comparision based sorting algorithms

The book CLRS says that any comparision sort algorithm requires omega(nlgn) comparisions n the worst case. My question is that why for heapsort it's O(nlgn) not omega(nlgn) since heapsort is also a ...
2
votes
1answer
24 views

How can I optimize the runtime of an algorithm that ranks binned columns cumulatively by average of another column?

I have a dense set of data that looks like this Y X1_BIN1 X1_BIN2 X2_BIN1 X2_BIN2 X2_BIN3 ... 0 1 0 0 1 0 ... 1 1 0 1 0 0 ... 0 0 1 0 0 1 ... 1 0 0 0 1 0 ... 0 1 1 0 0 0 ... but for millions of ...
1
vote
0answers
49 views

Sort rows and columns of matrix by permuting

I am trying to sort square matrix of size $N$ by $\textbf{only permuting}$ rows and columns, such that row appear in increasing (left to right) while columns appear in decreasing order (top to bottom)....
1
vote
1answer
25 views

Given a list of comparisons, sort items with as few additional comparisons as possible

You have n items x[0], ..., x[n-1]. Beforehand, you're given a list of several comparisons ...
1
vote
2answers
37 views

Sorting from independently chosen comparisons

I want to sort a list of n items from pairwise comparisons. Each round, I receive k comparisons, one each from ...
2
votes
2answers
56 views

What is a sorting algorithm that is robust to a faulty comparison?

I want to sort a list of n items with a comparison sort. However, one of the comparisons made by the algorithm will be flipped from what it's supposed to be. ...
2
votes
1answer
46 views

Hoare partition scheme may cause infinite recursion

Wiki states: "...partitioning algorithm guarantees lo ≤ p < hi which implies both resulting partitions are non-empty, hence there's no risk of infinite recursion." What prevents Hoare ...
0
votes
3answers
87 views

Runtime of sorting algorithms given a particular input

say that we have {2,3,5,4,6} as input that we want to sort in ascending order. Then, we know that we can use any of the sorting algorithms: bubble, insertion, selection, quick, merge, heap or counting....
2
votes
1answer
114 views

Understanding the upper bound proof for quick sort

I'm trying to understand the average run time of quicksort which is $O(n \log n)$. I understand the intuition behind it: if we partition array $A$ to e.g. $\alpha n $ and $(1-\alpha)n$ then we ...
0
votes
1answer
170 views

What is the optimal solution for the following "Largest lexicographical string with <= K consecutive elements" problem? Why is my answer wrong?

This is a simple question I ran into in a remote interview: Given a collection of letters, permute them (or one of its subset) into a string such that: each letter can only be repeated for <= 11 ...
1
vote
1answer
23 views

Is there a way to find the correct element in the array for the given index x?

In quick sort, in each iteration we are able to find correct index for an element (i.e. pivot element). Is there any algorithm to find correct element for a given index ? Here, correct index of an ...
1
vote
1answer
26 views

Number of unique values in array in $\theta(n)$ average expected time

My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by ...

1
2 3 4 5
17