Questions tagged [sorting]

Sorting is the process of applying some order to a collection of items.

Filter by
Sorted by
Tagged with
54
votes
4answers
180k views

Grouping elements in array by multiple properties

During work, I was given this task: to group elements with similar properties in the array. In general, the problem is as follows: ...
46
votes
3answers
9k views

Sorting millions of integers

Last Friday I was hit with a sorting interview question that I never really had to deal with. Develop a your own sorting algorithm. It cannot use any other Classes for help. It needs to ...
42
votes
10answers
67k views

Given an array of integers, return the smallest positive integer not in it

Write a function: function solution(A); that, given an array A of N integers, returns ...
40
votes
12answers
9k views

Efficiently squaring each element in a sorted array, keeping it sorted

The other day I was asked the following question during an interview: Given a sorted array, how would you square each element of this array, while keeping it sorted? I froze up and wrote a ...
37
votes
4answers
7k views

“How are you spending your time on the computer?”

I've made a Windows Forms application to track all of the processes running on my machine and it also saves the time an application is "active", an active application is the one that is on focus ...
36
votes
2answers
5k views

Quicksort implementation seems too slow with large data

I've written a program to compare different sorting algorithms with the array size being 10, 1,000, 100,000, 1,000,000 and 10,000,000. I, of course, expect Insertion to win out on 10 and merge heap ...
36
votes
5answers
3k views

Sorting strings by length - functional Python

I'm trying to port this little F# snippet while staying pythonic: ...
30
votes
10answers
14k views

Sorting large 1GB file with 100 millions numbers using merge sort

My task is to sort 1GB file with 100 million numbers using merge sort without recursion. My idea is to split file into 4 pieces, then to 2 and at the end to one file. ...
25
votes
1answer
2k views

Merge sort in Scheme

...
24
votes
5answers
78k views

Java Implementation of Quick Sort

This is my implementation of quicksort (algorithm taken from Cormen book). This is an in place implementation. Please let us know issues with this or any ideas to make it better. It performs at logN. ...
22
votes
5answers
5k views

Sorting algorithms - Bubble sort

For pure practice purposes, I started implementing different sorting algorithms in modern C++ in a standard library style way (i.e. using templates on iterators). This is my version of bubble sort. ...
19
votes
1answer
20k views

QuickSort C# Implementation

It has been a while since I've implemented a QuickSort and I wanted to write it down like I remembered. ...
19
votes
1answer
439 views

QuickMergeSort — The power of internal buffering

Amongst the lesser-known unstable sorting algorithms is the QuickXsort family of algorithms, as described in QuickXsort: Efficient Sorting with n log n - 1.399n +o(n) Comparisons on Average by Stefan ...
18
votes
1answer
2k views

Ford-Johnson merge-insertion sort

The Ford-Johnson algorithm, also known as merge-insertion sort (the name was probably given by Knuth) is an in-place sorting algorithm designed to perform as few comparisons as possible to sort a ...
17
votes
7answers
131k views

Finding repeating numbers in an array

I want to search through an array of n numbers and find the numbers that are repeated. So far I have this code, which does the job, but I find it to be a rather cumbersome method, but I can't seem to ...
17
votes
3answers
8k views

Insertion Sorting in C++

From Wikipedia: Insertion sort iterates, consuming one input element each repetition, and growing a sorted output list. Each iteration, insertion sort removes one element from the input data, ...
17
votes
2answers
3k views

Pancake sort interview with Python

I got asked this question during my interview. You can find information about this question here. Pancake Sort Given an array of integers arr: Write a function flip(arr, k) that reverses ...
16
votes
2answers
366 views

Exact sort - sorting with few move operations

A while ago, I found a somewhat interesting sorting algorithm named Exact-Sort, which is introduced with the following somewhat bold claim: No sort algorithm can sort an array with less position ...
15
votes
4answers
30k views

Sort three numbers using only if-statements

Beginner here, trying to make a small program that sorts three numbers from smallest to largest only by using ifs. Any thoughts on how to improve this? ...
15
votes
5answers
127k views

Sorting an HTML table with JavaScript

The following code sorts an HTML table with JavaScript (without using any external libraries like jQuery). Are there any shortcomings or possible improvements I could make? ...
15
votes
2answers
1k views

Is this C++ quicksort program okay?

I wrote a quicksort program in C++. Is it okay to implement it this way? Am I using pointers correctly? Is my style okay? Any ideas to speed it up or save memory? ...
14
votes
4answers
7k views

Sorting 10,000 unique randomly-generated numbers

I have to write this program in java. Write a program name sorting.java that will use an array to store 10,000 randomly generated numbers (ranging from 1 to 10,000 no repeat number). Here is what ...
14
votes
3answers
422 views

Building unusual IComparer<T> from expressions

I've needed a couple of very special comparers recenty and didn't want to implement each one of them every time so I created a builder and a couple of supporting classes that do that for me. Example ...
14
votes
4answers
4k views

Least significant digit (LSD) radix sort of strings

I am learning string algorithms and wrote this C example based on a Java example I found online. Any feedback relating to style, code clarity, whether it is generic enough to be re-used, interface, ...
14
votes
2answers
879 views

A Lisp version of the Schwartzian transform

Randal Schwartz stole Lisp's decorate-sort-undecorate idiom when he came up with what we'd later call the Schwartzian transform. All of my Lisp knowledge disappeared through nine half lives, but I ...
14
votes
3answers
639 views

Allowing the user to alphabetize or randomize the contents of a text file

As a newbie programmer, I decided to try my hand at making a program whose function actually might be useful to someone, somewhere. This utility takes a text file, reads it out to the user, displays ...
14
votes
2answers
1k views

IP sorting program

The purpose of this little program is to: Separate IPv4 addresses and IPv6 addresses Will be able to sort them even if the ...
14
votes
2answers
8k views

Parallel Merge Sort

Parallism is achieved by using a simple call to tbb::parallel_invoke(). However I can't break a speedup factor of x2 (after ~3-4 parallel HW threads), although 8 ...
13
votes
1answer
250 views

Vergesort — A runs-adaptive layer to enhance sorting algorithms

More than a full-fledged sorting algorithm, vergesort is a Runs-adaptive algorithm that falls back most of the time to another sorting algorithm to sort a sequence of elements, but is able to identify ...
12
votes
4answers
1k views

Shell Sort, Insertion Sort, Bubble Sort, Selection Sort Algorithms (Python)

There is a follow-up question available: shell-sort-insertion-sort-bubble-sort-selection-sort-algorithms-python. Selection Sort The selection sort algorithm sorts a list (array) by finding the ...
12
votes
4answers
41k views

Merge Sort an integer array

I've implemented merge sort an integer array. Is it okay to use i,j,k as variable name for looping? Should I change them to more meaningful names? Overall, any further suggestions on this code? ...
12
votes
4answers
28k views

Number aware string sorting with comparator

I have this class for use in sorting strings such that if strings have a number in the same position it will order the numbers in increasing order. Alphabetical gives: file1 file10 file2 What I'm ...
12
votes
2answers
565 views

Attempt at a sorting algorithm

I've been playing around and reading up on some sorting algorithms, and I've decided to try writing my own. It turned out to be quite fast (compared to the others shown in the image below). I'm very ...
12
votes
3answers
5k views

Natural Order Comparator

I've been looking for an implementation of Comparator that provides a "natural order". I found a couple but they were buggy or poorly designed. I wrote my own with ...
12
votes
1answer
3k views

Bubble Sort in C: Array vs Linked List

A few weeks ago I posted a code review of a linked list so I decided to implement bubble sort on my journey of learning C. Here is the referenced linked list library, though this isn't really what's ...
12
votes
2answers
462 views

Forecast maintenance interval for fleet of aircraft

Being new to VBA, and many years removed from college programming courses in Java, I'm seeking opinions about design, implementation, readability and general better practices using VBA to tackle ...
12
votes
2answers
4k views

Parallel Quicksort

As my parallel mergesort implementation was very memory dependent, I wanted to write a parallel quicksort one. Here it comes: ...
12
votes
3answers
301 views

Melsort — Sorting with encroaching lists

For the nth time already I come back with yet another alien sorting algorithm. Today I will present Melsort, implemented from the description I found in the paper Encroaching Lists as a Measure of ...
12
votes
1answer
2k views

Generic radix sort

This started out with my answer to Radix Sort on an Array of Strings?. Since I intend to write a generic radix sort for my own purposes anyway, I continued a little bit, and here is a version tested ...
11
votes
2answers
796 views

Milking order compatible with maximum number of observations

I'm using some old USA Computing Olympiad (USACO) problems to help teach me. This is the "Milking order" problem: Farmer John has \$N\$ cows (\$1≤N≤10^5\$), numbered \$1…N\$. He has made \$M\$ ...
11
votes
5answers
690 views

Selection sorter

Reference: Is this a faithful rendition of the selection sort algorithm? I'm working through an elementary book on sort and search algorithms, and writing some sample code to test my understanding. ...
11
votes
3answers
29k views

Creating a list containing the rank of the elements in the original list

I don't really know how to explain what I'm looking for in a way that makes sense, but here goes: Say I have a list $$L=(4,7,9,10,6,11,3)$$ What I want to produce is a corresponding list $$ K = (1,3,...
11
votes
6answers
408 views

Quad-sort: 4 sorting methods in one C++ file

I am fairly new to C++, and to have a break from all that Java programming, I decided to do something in C++, which is sorting. The four sorting algorithms are: Bubble Sort Insertion Sort Quick Sort ...
11
votes
3answers
12k views

Bubble sort algorithm in Python

I'm starting to implement basic sorting algorithms. Criticisms on the implementation is welcome. ...
11
votes
2answers
5k views

Always sorted list

In this list, each newly inserted element is put in its place in order using IComparer<T>. The implementation uses a ...
11
votes
3answers
7k views

Return characters in a string in alphabetical order

Problem Take a string and return all input characters in alphabetical order Assume that no numbers or punctuation will be used For the same character, uppercase characters should be returned ...
11
votes
2answers
445 views

Python implementation of quicksort

My teacher often tells me that I don't take full advantage of Python capabilities, I would like to know if my implementation of Quicksort is good enough and how could I improve it, aside from doing it ...
11
votes
2answers
5k views

Efficient way of sorting a List based on multiple properties using Google Guava

I'm using Google Guava 17.0 library. I have a class named AroundBust containing only two properties id of type ...
11
votes
2answers
413 views

Frequency counter utility class

Some very common tasks that keep popping up from time time: Find the most frequent something in a collection of things ... or the count of that thing ... or both (the item and its count) Get the list ...
11
votes
1answer
131 views

Composable by-member comparison

Motivation Quite often, I find myself creating types that must be compared memberwise. For example, consider this simple Person: ...