The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
24 views

Algorithm for inserting into sorted subset

A is a sorted list. B is a sorted list, and a subset of A. If an element is inserted into A at index i what's the most efficient way to determine the correct index i' for it's position in B? Given ...
0
votes
1answer
39 views

Parallel radix sort algorithm

I am trying to implement radix sort. While I understand the radix sort for serial implementation, I am confused about parallel implementation. I am trying to implement the algorithm given in ...
-5
votes
2answers
111 views

Best and worst case for the quicksort algorithm with 7 elements

part of my final project for my computer science class is developing a computer program that implements quicksort, but as a sort of pre-requisite, our teacher has given us this problem. Find 7 ...
2
votes
2answers
87 views

Set distances algorithm question

I have multiple sets containing integers. An integer maybe present in one set or multiple sets. I would like to find/match the sets with the most common integers. Example s1 {1, 2, 3, 4} s2 {1, 3, 4, ...
1
vote
2answers
66 views

Python sorted iterable set, modifiable during iteration

I am looking for a datastructure to handle cycling through a large number of ordered subroutines, some of which are active, most of which are not. I am thinking I need an implementation of a python ...
0
votes
3answers
130 views

Sorting an array when values are decreased by each swap [closed]

Recently in an interview I come across a question: We have an unsorted array, we need to sort it with minimum number of swap. We have in sort a 'tax' of 1 is deducted from the number we are ...
-1
votes
1answer
41 views

Short Sequential Search vs. Regular Sequential Search

Assuming a list of elements is sorted in ascending order, we search sequentially from the first element comparing the target to successive elements either until we find the target (succeed) or until ...
0
votes
1answer
54 views

expressing the speed of a sorting algorithm

How would I express the speed of the following sort algorithm? I know bubblesort is n^n (er, I mean n^2...as someone pointed out below). In the following the array decreases each time you call it ...
0
votes
0answers
26 views

I have URL and ID pairings, and I send the URLs to an API which it returns in no specific order. How should I pair them back up?

This is a programming problem that I haven't came across yet and I want to make sure I'm tackling it in an efficient manner. I have an array of dictionaries, with each dictionary consisting of a ...
1
vote
1answer
131 views

Fully Stable, In-Place Unique Algorithm in O(n)

Is there an algorithm that, given a sorted array, swaps all the first unique elements to the beginning of the array and the duplicates to the end, while remaining stable for both the unique subarray ...
3
votes
1answer
76 views

Algorithm that determines relevant attributes in ordered list

Suppose I have a list of objects sorted by a person based on that person's subjective taste. Let's assume that this person is being somewhat consistent in their sorting and that there are quantifiable ...
4
votes
3answers
1k views

Quickest way to split a delimited String in Java

I am building a Comparator that provides multi-column sort capability on a delimited String. I am currently using the split method from String class as my preferred choice for splitting the raw String ...
3
votes
1answer
230 views

which sorting algorithms is using OrderBy

I am litle curious about what sorting algorithm is using OrderBy (linq to objects). quicksort? heapsort? introspective sort ? As i see in MSDN documentation List.Sort is using introspective sort: ...
2
votes
3answers
265 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 ...
2
votes
3answers
470 views

Sorting an array of numbers with decimal places

Suppose I have an array of float values in the following format: { 1.34, 1.15, 1.1, 1.2, 1.26, 1.10, 1.20, 1.17 } Suppose they have been provided by user input (or some other mechanism), where the ...
1
vote
1answer
80 views

How to queue work orders by date and priority?

In my organization I work on orders based on date, so earliest work orders first. We also have an option for order to be marked "priority" in which case those orders are done first but not always. ...
2
votes
4answers
244 views

Looking for monotonically increasing (integer) hash function

I'm looking for a HashFunction(X,Y: Integer): Integer that is monotonically increasing on X, then Y. So: HashFunction(x1,y1) > HashFunction(x2,y2) if x1>x2 HashFunction(x,y1) > HashFunction(x,y2) if ...
0
votes
3answers
233 views

How to create single integer index value based on two integers where first is unlimited?

I have table data containing an integer value X ranging from 1.... unknown, and an integer value Y ranging from 1..9 The data need to be presented in order 'X then Y'. For one visual component I can ...
-1
votes
5answers
1k views

Reverse subarray of an array with O(1)

I have an idea how to implement sub array reverse with O(1), not including precalculation such as reading the input. I will have many reverse operations, and I can't use the trivial solution of O(N). ...
0
votes
1answer
557 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 ...
1
vote
1answer
116 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
1answer
282 views

Use ruby's array sort() method, or add items in correct place with a binary lookup?

If I am loading a whole load of items (un-ordered words from a file or something) would it be more efficient to load them all to a Ruby array, and then use the built in sort! method or to do a binary ...
0
votes
1answer
258 views

Sort rectangles in a grid based on a comparison of the center point of each

If I have a grid of rectangles and I move one of the rectangles, say above and to the left of another rectangle, how would I resort the rectangles? Note the rectangles are in an array, so each ...
2
votes
1answer
95 views

Sorting with continous input

I'm designing (not writing, yet) a task scheduler system for a complex video game. The rest of the program passes it objects containing a function and some metadata including an estimation of how much ...
1
vote
3answers
470 views

Sort an array in a specific order - not ascending/descending

I'm working on an algorithm that works best if the inputs are passed to it in a particular order, so I want to sort them that way. The difference is drastic enough for me to consider re-sorting the ...
5
votes
1answer
294 views

Sorting versus hashing

My problem is as follows. I have an array of n strings with m < n of them distinct. I want to create a one-to-one function which assigns each of the m distinct strings to the numbers 0 ... m-1. ...
13
votes
2answers
460 views

Trying to understand the 2N lnN compares for quicksort

I was going through the analysis of quicksort in Sedgewick's Algorithms book. He creates the following recurrence relation for number of compares in quicksort while sorting an array of N distinct ...
1
vote
1answer
224 views

Advantage of 2-way merge sort against n-way

It's known 2-way Merge sort takes N*logN time. I wonder, what would be the running time if we split an array of the size N into N subarrays and then do the same thing as we would do for 2-way Merge? ...
6
votes
6answers
3k 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 ...
6
votes
3answers
697 views

Why is Quicksort called “Quicksort”?

The point of this question is not to debate the merits of this over any other sorting algorithm - certainly there are many other questions that do this. This question is about the name. Why is ...
1
vote
2answers
404 views

Radix exchange sort implementation?

I need a little help understanding the implementation of radix exchange sort algorithm. Radix exchange (I don't know if it's the exact name in english based literature) is a lot similar to quicksort, ...
1
vote
3answers
291 views

Sorting and averaging the highest values of pixel data

Currently, I am using Android/Java. I am looking for the most efficient means to determine the average of the highest 100 pixel values taken from a greyscale preview. The preview part I am more or ...
5
votes
3answers
611 views

Why don't computers come with specialized hardware such as sorting networks?

Instead of programming the way we do, why don't we make specifications of common tasks such as "sorting", and then let the environment compile it to make best use of it's hardware? This way, we could ...
0
votes
3answers
126 views

Binary Search Programming implementation

Binary Search, as we all know requires the elements to be sorted. But we have to take care of unsorted elements too, in the worst case. If the input size is very large, is it a good idea to sort the ...
0
votes
1answer
982 views

Sorting an ArrayList by a Split Value [closed]

I am attempting to create an list which should be sorted by a particular field in a colon separated string. I have an array of strings with the following values: name1:535 name2:697 After sorting ...
1
vote
1answer
217 views

Custom Alphabetic Sorting of Array in Java

I have a requirement to read a text file with lines in tag=value format and then output the file with specific tags listed first and the rest sorted alphabetically. The incoming file is randomly ...
1
vote
1answer
2k 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 ...
2
votes
3answers
134 views

What kind of algorithm could be used to produce an ordering which maximizes # of satisfied 'less than' constraints?

Let's say I have a set of items {e1, e2, ..., en}, and I also have a set of constraints {c1, c2, ..., cm}, with ci := ej appears before ek, for some j and k. I want to produce an ordering of my items ...
32
votes
6answers
2k views

I'd like to write an “ultimate shuffle” algorithm to sort my mp3 collection

I'm looking for pseudocode suggestions for sorting my mp3 files in a way that avoids title and artist repetition. I listen to crooners - Frank Sinatra, Tony Bennett, Ella Fitzgerald etc. singing old ...
2
votes
4answers
690 views

Applications of heapsort

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 ...
0
votes
2answers
438 views

Does this version of insertion sort have O(n) complexity for best case?

for ( i = 1 ; i <= N ; i++ ) { for ( j = 0 ; j < i ; j++ ) { if ( arr[j] > arr[i] ) { temp = arr[j] ; arr[j] = arr[i] ; for ( k = i ; k > j ; k-- ) ...
0
votes
3answers
1k views

What are the most popular sorting algorithms in practice? [closed]

Although I suspect the answer to this question may be something along the lines of "popularity is irrelevant; each algorithm has its trade-offs", I'm interested in a list of popular sorting algorithms ...
1
vote
4answers
239 views

How important is understanding the coding behind sorts?

First off, if this is in the wrong place I apologise. I wasn't too sure on which of the Stack Exchange sites to ask it. I am studying Software Development at university, on a one year conversion ...
1
vote
3answers
375 views

Should I calculate hotness of a post on request or pre-calculate it?

Here is the Reddit's hot algorithm: cpdef double _hot(long ups, long downs, double date): """The hot formula. Should match the equivalent function in postgres.""" s = score(ups, downs) ...
4
votes
2answers
2k views

Help understanding MapReduce Sort example

From Section 5.3 of Google's paper describing MapReduce. "A Map function extracts a 10-byte sorting key from a text line and emits the key and the original text line as the intermediate ...
2
votes
1answer
814 views

Fastest Haskell library sort implementation

I am implementing an application in Haskell and, for sorting, I use the library function Data.List.sort. However, I was wondering whether this is the fastest sort implementation in the Haskell ...
4
votes
2answers
2k 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 ...
2
votes
2answers
474 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
1answer
370 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 - ...
6
votes
5answers
375 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 ...