The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
98 views

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

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
30 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
115 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 ...
4
votes
4answers
450 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 ...
-1
votes
0answers
32 views

Javascript Array Sorting issue [migrated]

I have a program that basically allows a viewer to enter an employees name, and their salary, and then hit a confirmation button. When this button is hit, a table row and cell is added for both the ...
1
vote
3answers
407 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 ...
3
votes
1answer
794 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 ...
1
vote
1answer
123 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 ...
3
votes
2answers
57 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
92 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 ...
6
votes
5answers
492 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 ...
0
votes
1answer
492 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 ...
5
votes
1answer
261 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 ...
1
vote
2answers
153 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
votes
2answers
80 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 ...
0
votes
1answer
99 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 ...
6
votes
3answers
403 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
221 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 ...
2
votes
2answers
809 views

About insertion sort and especially why it's said that copy is much faster than swap?

From Lafore's "Data Structures and Algorithms in Java": (about insertion sort (which uses copy + shift instead of swap (used in bubble and selection sort))) However, a copy isn’t as time-consuming ...
0
votes
2answers
126 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 ...
1
vote
1answer
105 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 ...
1
vote
1answer
56 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 ...
18
votes
3answers
2k views

Java and .NET: Why different sorting algorithms are used by default?

Just wondering why Java and .NET Framework uses different sorting algorithm by default. In Java Array.Sort() uses Merge Sort algorithm by default and as Wikipedia.com says: In Java, the ...
1
vote
1answer
7k views

Quicksort and middle pivot

I am having a head ache understanding quicksort with middle pivot. I found lot of explanations about using left most or right most, but not many about a middle one. Can I safely assume these?: If ...
4
votes
3answers
159 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 ...
2
votes
5answers
5k views

Is Bubble Sort the slowest sorting algorithm? [closed]

Is bubble sort the least Big-O efficient? If the answer is no, then what is the least efficient sorting algorithm?
1
vote
1answer
127 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
69 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
367 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 ...
0
votes
2answers
2k views

efficient way to count number of swaps in insertion sort

I am browsing some online coding challenge online and got struck somewhere . Objective of program is to find maximum number of swaps required in sorting an array via insertion sort in efficient time ...
-2
votes
3answers
523 views

Situations when O(n^2) better than O(n*log(n)) [duplicate]

Is there any situation a sorting algorithm of time complexity O(n2) could be better than an O(n log(n)) sorting algorithm in any way?
9
votes
7answers
8k views

Why is binary search,which needs sorted data, considered better than linear search?

I have always heard that linear search is a naive approach and binary search is better than it in performance due to better asymptotic complexity. But I never understood why is it better than linear ...
2
votes
1answer
222 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
129 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 ...
0
votes
1answer
64 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 ...
1
vote
7answers
11k views

Merge sort versus quick sort performance

I have implemented merge sort and quick sort using C (GCC 4.4.3 on Ubuntu 10.04 running on a 4 GB RAM laptop with an Intel DUO CPU at 2GHz) and I wanted to compare the performance of the two ...
4
votes
2answers
2k 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 ...
2
votes
1answer
326 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
79 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 ...
0
votes
0answers
207 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
68 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
335 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
88 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 ...
1
vote
1answer
167 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 ...
1
vote
1answer
496 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
348 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 ...
1
vote
3answers
467 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 ...
28
votes
2answers
9k views

What does it mean for a sorting algorithm to be “stable”?

In reading about various sorting algorithms I've seen it mentioned that some are "stable" and some are not. What does that mean, and what tradeoffs are involved on that basis when selecting an ...
2
votes
4answers
402 views

Is there any sorting algorithm which is not inherently sequential and is task distributable?

After googling for a couple hours, I came to a conclusion that all sorting algorithms are inherently sequential which can be data distributed but not task distributable. Is there any algorithm which ...
3
votes
1answer
3k views

Why is time complexity of k-way merge sort O(nk^2)?

I'm comparatively new to algorithm analysis and am taking a related course on coursera where I came accross k way merge sort. The time complexity of 2 way merge sort is n log2 n, of 3 way merge sort ...