Re: Efficient sort function allowing own test and swap function as parameter

[Ali Çehreli via Digitalmars-d-learn]

On 10/6/20 3:18 PM, Alaindevos wrote:
I have a large table consisting of two columns.One with words.Another 
with frequencies. I want to sort them efficiently according to the names 
or frequency.
For this I need an efficient sort function where I can plugin my proper 
test of order, and proper swap. Currently I do it using an own written 
bubble sort that doesn't scale well.


I had fun writing the following program. Note how makeIndex allows 
visiting elements in sorted order without actually sorting them.

import std.random;
import std.range;
import std.algorithm;
import std.conv;
import std.stdio;

struct S {
  string word;
  size_t frequency;
}

bool byWord(S a, S b) {
  return a.word < b.word;
}

bool byFrequency(S a, S b) {
  return a.frequency < b.frequency;
}

auto dump(R)(string title, R range) {
  writefln!"\n%s:\n%(%s\n%)"(title, range);
}

// A test function that makes an S
S makeS() {
  string makeWord() {
    static letters = iota('a', 'z' + 1).map!(to!dchar).array;
    return letters.randomSample(4).to!string; // Four-letter words! :p
  }
  size_t makeFrequency() {
    return uniform(0, 100);
  }
  return S(makeWord(), makeFrequency());
}

// A test function that makes some S'es
S[] makeSs() {
  return 10.iota.map!(i => makeS()).array;
}

void main() {
  auto ss = makeSs();
  dump("Unsorted", ss);

  auto byWordIndexes = new size_t[ss.length];
  ss.makeIndex!byWord(byWordIndexes);
  dump("Still unsorted but visited by word order",
       byWordIndexes.map!(i => ss[i]));

  auto byFrequencyIndexes = new size_t[ss.length];
  ss.makeIndex!byFrequency(byFrequencyIndexes);
  dump("Still unsorted but visited by frequency order",
       byFrequencyIndexes.map!(i => ss[i]));

  ss.sort!byWord();
  dump("Actually sorted by words", ss);

  ss.sort!byFrequency();
  dump("Actually sorted by frequencies", ss);
}

Sample output:

Unsorted:
S("bfmp", 78)
S("imsx", 17)
S("kmwy", 60)
S("klpw", 92)
S("hnrt", 24)
S("aivz", 29)
S("prst", 24)
S("cdlm", 86)
S("alvz", 13)
S("mnxz", 52)

Still unsorted but visited by word order:
S("aivz", 29)
S("alvz", 13)
S("bfmp", 78)
S("cdlm", 86)
S("hnrt", 24)
S("imsx", 17)
S("klpw", 92)
S("kmwy", 60)
S("mnxz", 52)
S("prst", 24)

Still unsorted but visited by frequency order:
S("alvz", 13)
S("imsx", 17)
S("hnrt", 24)
S("prst", 24)
S("aivz", 29)
S("mnxz", 52)
S("kmwy", 60)
S("bfmp", 78)
S("cdlm", 86)
S("klpw", 92)

Actually sorted by words:
S("aivz", 29)
S("alvz", 13)
S("bfmp", 78)
S("cdlm", 86)
S("hnrt", 24)
S("imsx", 17)
S("klpw", 92)
S("kmwy", 60)
S("mnxz", 52)
S("prst", 24)

Actually sorted by frequencies:
S("alvz", 13)
S("imsx", 17)
S("hnrt", 24)
S("prst", 24)
S("aivz", 29)
S("mnxz", 52)
S("kmwy", 60)
S("bfmp", 78)
S("cdlm", 86)
S("klpw", 92)

Ali