For questions about sorting algorithms and their speed and complexity.

learn more… | top users | synonyms

4
votes
4answers
172 views

Best practice for getting last record inserted in DB

Me and a couple of colleagues are having a discussion regarding the following case: In an OrderStatus table we're keeping track of all the statuses an order goes through in time, including ...
1
vote
4answers
137 views

Should I be using any algorithm to sort/find items, or use a language's built-in ways?

I'm currently a first semester IT student, and I'm wondering if it's better to write my method to find something e.g. in a C# List, or to use any built in method to do these, such as LINQ or .Find or ...
6
votes
2answers
191 views

Efficient algorithm to merge n successive sorted arrays in place

I am developing an in-place sorting algorithm that leaves the array into a state where it is basically a succession of sorted subsequences of any size (most are bigger than log2(size(array))); then it ...
0
votes
2answers
87 views

How to find the kth minimum element in an array

I am looking for an efficient algorithm to find the k'th minimum element in an unsorted array of n elements, where 1 <= k <= n. The obvious thing is to sort the array first, then pick the k'th ...
5
votes
2answers
114 views

How to store ordered information in a Relational Database

I am trying to understand how to properly store ordered information in a relational database. An example: Say I have a Playlist, consisting of Songs. Inside my Relational Database, I have a table of ...
2
votes
1answer
119 views

How to sort a list containing bounded set of values in linear time when length is unknown?

Given a list of integers whose length is unknown, and each of its elements lies between 1 to 1000, how does one sort this list in linear time?
-2
votes
1answer
70 views

Sorting array according to a formula [closed]

I need to sort the values according to the following problem: For every n, determine the triples (i,j,k) that satisfies i+j+k=n, then sort the triples (for every n) with respect to the value of the ...
3
votes
2answers
78 views

How do I model a sortable resource in sql database? [closed]

I encounter this issue when I create REST API. I cannot tell the exact scenario, but let's say it is for a website that has category and product resources. Each category has many products and both ...
-3
votes
1answer
77 views

complexity of an algorithm, sorting 5% out [duplicate]

I have been asked the following question.. An algorithm considers n elements, sorts 5% of n out, considers the remain elements(95%), sorts 5% of the remain elements, and so on until finally one last ...
3
votes
3answers
101 views

How to model heuristic uncertainty when sorting data?

Sorting algorithms assume you have a defined comparator. For example, if sorting integers A and B, the A > B operation allows you to determine if A should be after or before B. Imagine you want ...
5
votes
1answer
88 views

Sorting algorithm that can handle some error

Suppose you want to sort your movie collection, from favorite to hated. You apply the rules of some sorting algorithm by asking many questions of the form: "Did I like A or B more?" It's now sorted, ...
4
votes
2answers
97 views

Sort a list while putting together or after?

I have to read through an extremely large amount of network data from various log files, and compile relevant information about that data to perform statistical analysis on it (the top communicators, ...
2
votes
1answer
80 views

Why is Python sorted() result like this?

I might be missing something obvious here, but why does Python 2.x sorted() function work like this? In [95]: l = [1, '5', 4, 2, '3', 'b', 'c', '-a'] In [96]: sorted(l) Out[96]: [1, 2, 4, '-a', '3', ...
-1
votes
2answers
114 views

Merging Sorted Lists (with no comparison function)

I have a few lists of items (which will likely but not necessarily have common elements). The lists are known to be sorted, but don't have a comparison function (they were manually put into the system ...
4
votes
1answer
159 views

Optimal fixed-size sequential sorting algorithms

I have been working on sorting algorithms for a few weeks now, but one of my question still hasn't an answer: are there optimal sequential comparison sorts for fixed-size – and random-access – ...
0
votes
0answers
95 views

Algorithm to maximize pairwise comparisons using transitive property

I'm looking for some direction on building an algorithm that will maximize the number of pairwise comparisons of objects in a set using transitivity. To explain in detail: Suppose there are x ...
0
votes
3answers
222 views

Analysis of insertion sort does not equal O(n^2)?

I'm learning more about algorithms and data structures. According to Wikipedia and other reliable sources, an insertion sort has a worst-case time complexity of O(n2). I'm attempting to measure that ...
1
vote
2answers
225 views

Shuffle/Randomize a collection without knowing the number of items? [closed]

Let's say I have a sequence of items of unknown length, n. I want to randomize the order of this sequence without having to go through the entire sequence. Are there any algorithms that can do this? ...
-2
votes
1answer
48 views

Move file into apropriate directory based upon first letter of second word, followed by the first two letters of the second word with Python [closed]

EDIT: Apparently the below question is too specific. Let me rephrase: I'm looking for a way to fit a letter into a list of specified ranges such that, if given the letter S and the ranges A-F, G-M, ...
0
votes
1answer
196 views

How to sort fractions (small numbers)

We have 100 000 fractions: Let's consider following fractions. p/(2^q) such that 0 <= p,q <= 10 As you can see there are <= 10 * 10 different fractions, but we have 100 000 that we have to ...
3
votes
2answers
101 views

(Partially) Sorting a lazy-evaluated collection

So I'm trying to implement a lazy-evaluating data type (in PHP, though that shouldn't matter any) where you can queue up actions to take on a set of data. This data can come (theoretically) from any ...
0
votes
1answer
136 views

Is external merge sort a divide-and-conquer algorithm? [closed]

Today I was corrected for mentioning "External Merge Sort" as an example of a divide-and-conquer (D&C) algorithm and after doing a lot of research online and in the most prominent books on ...
5
votes
1answer
324 views

Kth selection routine - Floyd Algorithm 489

I have recently come across a promising Kth selection routine that reportedly outperforms quickselect the Floyd, Rivest Select routine. This Wikipedia article provides a pseudocode version which I ...
4
votes
1answer
304 views

Sorting a large number of unknown items with multiple stacks

Here is a problem I'm trying to solve for a personal project. I'm not exactly sure how best to even approach it. Problem: I have a single stack already populated with several thousands of unknown ...
6
votes
3answers
411 views

Picking m number in the best possible time

Imagine we want to pick m numbers from n numbers so that the difference of the maximum and minimum of the m numbers be minimum, for example if m = 4 n =6 numbers: 10 12 10 7 5 22 The ...
2
votes
3answers
267 views

fast, say O(log2(N)), sliding median algorithm

So I know how to do a fast O(log2(N)) sliding max or sliding min algorithm. Brookes: "Algorithms for Max and Min Filters with Improved Worst-Case Performance" IEEE TRANSACTIONS ON CIRCUITS AND ...
1
vote
1answer
221 views

How to count sort comparison

When it is said that this sort has M number of comparisons what does it mean? As an example: procedure bubbleSort( A : list of sortable items ) n = length(A) repeat swapped = false ...
0
votes
2answers
291 views

Average number of comparison for sort algorithms

I need to write different sort algorithms such as bubbleSort insertionSort selectionSort quickSort mergeSort And measure how many average comparison does each one for N number (averaging between ...
0
votes
2answers
195 views

Can relational database tables always be topologically sorted by their FK reference relation?

Suppose I have some conceptual, not physical, E-R diagram describing a relational database. I want to sort all the tables in the database using a topological sort, where the partial ordering between ...
1
vote
1answer
104 views

filtering data from db

I've taken over a web application that someone else built. It's a pretty simple application that queries ALL records from a db and displays them in a list. They've also provided a way to 'filter' the ...
0
votes
1answer
159 views

Sorting Sentences by New Words in Each

A very useful learning tool I stumbled across for Chinese was a massive list of sentences that, barring the first 10 or 15, only differed by the ones before by one or two words, or at least as few as ...
4
votes
3answers
170 views

Algorithm that generates a group of men and women who are each interested in everyone from the other gender

In my dating app, I need to compile lists of men and women where all of the men in the list are potentially interested in all of the women in the list, and vice versa. That is, in a list of 10 men ...
1
vote
1answer
154 views

What algorithm can be used to determine order given incomplete information?

Given a series of statements such as: a<c a<b b<c (Read as "a is before b", "a is before c", etc.) What is the order of the elements? In this example, the answer is a<b<c. A less ...
0
votes
1answer
78 views

How to efficiently determine when changes occur in event lists

We have a system that stores event information. There is a primary list of events as well as a secondary list, these may overlap. Secondary lists are combined with the primary based on 3 main rules. ...
0
votes
2answers
620 views

Algorithm for merging multiple rows of data

I need an algorithm to merge multiple rows for data, where one column is the index column and if one or more rows have the same index value merge the column values into a single row, and lastly sort ...
2
votes
1answer
336 views

Insertion sorting Algorithm comparison

I recently came across sorting techniques and of particular, 'insertion sorting'. Although the logic and method is fairly understandable, the actual function seemed a bit complex (given below). ...
3
votes
3answers
187 views

sorting / merging hashtable

For my project I have a hashtable with 1M buckets (sometimes more). Each bucket contains lots of values and they are stored sorted in a dynamic array. I am looking for easy enough way to store all ...
4
votes
4answers
467 views

Why are return values from compare functions in many languages defined loosely?

Many languages define that compare functions should return ANY negative value, zero, or ANY positive value. Is there some reason that it shouldn't be clearly defined as -1 0 and 1? Does a wide range ...
0
votes
1answer
78 views

What would be the best sort to use on a something with sorted “chunks”?

Imagine a sorted deck of N cards that has been cut K times by moving X cards from the top to the bottom (X is a different / random amount each time, X is always < N) - what would be the best way to ...
2
votes
1answer
555 views

Quickest sorting algorithm for sorting a low number of integers

I am making a program on my spare time that I want to run as quickly as possible. The program is written in C. A large set of the procedures operate on pointers to 7 integers that are sorted by their ...
1
vote
2answers
90 views

multiple comparison sorting

I have a set of songs where I want to sort them by a particular quality. In order to do this (by crowdsourcing) I will present users with a comparison between two songs. The user will then choose ...
1
vote
0answers
296 views

In-place merging of sorted intervals in an array?

So I have code producing k sorted intervals in an n-sized array. What I'm brainstorming is the possibility of in-place merge of these intervals into a single sorted interval/array. The problem is ...
1
vote
1answer
71 views

Sorting list and changing same values to nearly the same

I have a list of doubles that need to be sorted and changed so that there are no two numbers that are the same (difference smaller then 0.05) and I need to do it fast. I don't care about preserving ...
5
votes
2answers
403 views

Is there any language-agnostic specification for “String Natural Sorting Order”

As I painfully try to find a good natural sorting algorithm written in JavaScript I then stumble upon a bunch of different implementations, & interesting blog posts & answers on Stack ...
1
vote
0answers
115 views

An algorithm to implement SQL's ORDER BY with TOP/LIMIT or OFFSET/FETCH

Is there a general algorithm to implement SQL's ORDER BY with OFFSET/LIMIT more efficiently than sorting all the records? The algorithm for a simple TOP x is easy enough. It takes one full pass ...
4
votes
2answers
5k views

What makes for a bad case for quick sort?

I am learning about quicksort and want to illustrate different arrays that quicksort would have a hard time on. The quicksort I have in mind does not have an initial random shuffling, does 2 ...
1
vote
1answer
197 views

How to efficiently sort a recursively defined Stack?

I am trying to implement a recursively defined Stack and sort it in Java. I don't have a particular usage of this program in mind. I found this approach of stack implementation a bit useful while ...
0
votes
1answer
573 views

Count Sort Algorithm efficiency

As I read a book about "Algorithm Analysis", I came across count_sort Algorithm. However, I have read elsewhere that "Quick Sort/ Merge Sort" are the best and the most efficient sorting algorithms. I ...
1
vote
1answer
666 views

Dual pivot quicksort in face of expensive swaps

I was told this is better place to ask this TLDR Has anyone tested dual pivot quicksort performance with expensive-to-swap elements? It seems that in this case, it should massively underperform ...
1
vote
2answers
505 views

Level order sorted binary tree from a binary tree

Lets suppose we have a binary tree . Tree node structure is as struct node { int val ; struct node *left , *right ; } Now we have to sort the tree in level order manner . For example lets ...