Tagged Questions

For questions about sorting algorithms and their speed and complexity.

58 views

mergesort complexity O(nlogn) + O(n)?

When analyzing the time complexity of the merge sort, I know that since there are O(log(n)) levels and each level takes a O(n) operation, the entire time complexity should be O(nlog(n)). However, ...
61 views

How can I efficiently add/delete/get sorted data in Java?

I am writing a telephone directory program and need to store the entries in a CSV formatted file. However, I am having difficulty keeping the entries in order when adding. I was considering reading in ...
105 views

Should I use this very short Python Quicksort implementation?

def quicksort(N): if len(N) < 2: return N else: less = quicksort([number for number in N[1:] if number < N[0]]) more = quicksort([number for number in N[1:] if ...
119 views

How does this recursive function exit? [closed]

In the merge_sort part, there are multiple calls to the same function within the recursive. How are the other two executed when the definition holds that till a condition is false, the recursion does ...
58 views

Why does Erlang provide built-in ordering(sorting) of the basic data types?

In Erlang, an ordering of the built-in basic data types has been established: number < atom < reference < fun < port < pid < tuple < list < bit string This means that ...
189 views

a funky interleaved sorting problem

I have an array of items. Some items have a number on both sides. I'll call these "matched pairs". I need to sort the items between the matched pairs in a particular way. There's a "from number" ...
75 views

Data structure for storing sorted data

What's a good way to store loads of sorted string on a file so that inserts and reads are fast? I could store it up in a tree, and read/modify/store it as needed, but that seems wasteful for ...
83 views

How to combine N non-comparable arrays up to an output limit in a fair way?

Given N non-comparable arrays of different sizes, what is the best method to combine them into one output array? Since the input arrays are non-comparable, a metric is needed to represent how ...
116 views

Most efficient way to find top values

Let's say we're given n positive integers in random order. What's the most efficient way to find the m largest elements and what's the complexity? For example, given 1000 values, find the top 10.
235 views

Which programming languages provide a Schwartzian transform like interface for sorting

Introduction The Schwartzian transform -- also known as map-sort-map or decorate-sort-undecorate (DSU) --, attributed to Randal Schwartz of the Perl community, sorts elements of a list or array by a ...
214 views

Merge sort and O(n log n) mystery

I read every explanation here but still not convinced. I think mergesort is n * n and I know I am wrong but not sure where. Here is what I think: Suppose we are sorting 8 elements and this is the ...
360 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 "Pending",...
161 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 ....
345 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 ...
96 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 ...
189 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 ...
136 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?
78 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 ...
137 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 ...
83 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 ...
129 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 ...
105 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, ...
161 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, ...
91 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', '...
124 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 ...
225 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 – ...
131 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 ...
313 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 ...
239 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? ...
56 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, N-...
293 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 ...
279 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 ...
154 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 ...
449 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 ...
357 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 ...
414 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 ...
311 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 ...
326 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 ...
753 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 N!...
270 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 ...
158 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 ...
206 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 ...
175 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 ...
202 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 ...
82 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. ...
1k 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 ...
373 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). ...
246 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 ...