# Tagged Questions

For questions about sorting algorithms and their speed and complexity.

40 views

### Sorting a 2d array in java

I'm a high school student who is interested in computer science, I asked this question to my teacher but she told me not to bother messing around with code and trying to understand how to modify ...
78 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 ...
54 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 ...
183 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" ...
4k views

### sorting using a custom definition of “>” and “< ” in python

suppose I have a custom function such as def greater(a, b): if (a % b) % 2 == 0: return 1 return 0 It defines how to compare two numbers and determine which is greater. In this ...
73 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 ...
108 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.
332 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 ...
230 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 ...
197 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 ...
12k views

### How do I figure out the minimum number of swaps to sort a list in-place?

In-place sorting is essentially swapping elements without using extra storage, correct? How can I find the minimum number of swaps required for a list? A C D Q R Z E // input | | | > > >...
258 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",...
2k views

### What's the best way to manage list item sort order with Drag & Drop UI?

I have a list of Students that I should display to user on a web page in tabular format. The items are stored in DB along with SortOrder information. On the web page, user can rearrange the list ...
159 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 ....
347 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 ...
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 ...
869 views

### Efficient way to sort large set of numbers

I have to sort a set of 100000 integers as a part of a programming Q. The time limit is pretty restrictive, so I have to use the most time-efficient approach possible. My current code - #include<...
102 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, ...
180 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 ...
130 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 ...
125 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 ...
126 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 ...
4k views

### Applications of heapsort [closed]

Heapsort is a sorting algorithm that has a time complexity of O(nlogn), and performs sorting using O(1) space complexity. However, I know that because it's unstable, it doesn't find many applications (...
144 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, ...
6k views

### How to handle sorting of complex objects?

How would one sort a list of objects that have more than one sortable element? Suppose you have a simple object Car and car is a defined as such: class Car { public String make; public ...
89 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', '...
123 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 ...
855 views

### Tournament bracket method to put distance between teammates

I am using a proper binary tree to simulate a tournament bracket. It's preferred any competitors in the bracket that are teammates don't meet each other until the later rounds. What is an efficient ...
206 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 – ...
5k views

### Fast algorithm for finding common elements of two sorted lists

Suppose I have two lists of N 3 by 3 vectors of integers. I need to find a quick way (say of running time at most N^(1+epsilon)) to find the vectors of the first list that have the same 1st ...
3k views

### Which sorting algorithms have a different worst case complexity than their average case? [closed]

I'v been working on sorting for a while now but I can't figure these two questions apart, I'm kind of getting mixed up somewhere ... Somebody help a) Which sorting algorithms have a different worst ...
124 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 ...
305 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? ...
53 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-...
277 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 ...
473 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 ...
615 views

### How can I rank teams based off of head to head wins/losses

I'm trying to write an algorithm (specifically in Ruby) that will rank teams based on their record against each other. If a team A and team B have won the same amount of games against each other, then ...
931 views

### How can this deterministic linear time selection algorithm be linear?

I'm trying to understand the basic concepts of algorithms through the classes offered at Coursera (in bits and pieces), I came across the deterministic linear time selection algorithm that works as ...
137 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 ...
153 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 ...
516 views

### Type of AI to tackle this problem?

I posted this on stackoverflow but want to get your recommendations as well as a user on overflow recommended I post it here. I'm going to say from the beginning that I am not a programmer, I have a ...
665 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 ...
439 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 ...
182 views

### Heuristic for consistiently ordering points in a a plane

I have rectangular regions in a plane. I want to consistently order them in a human-friendly way that a typical y-x sort won't work for. Basically I want (0,0), (1,0), and (0,1) to sort the same as (0,...
264 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 ...