Re: Efficiently Extracting Identical Values From A List/Array

From: Karl Heinz Buchegger (kbuchegg_at_gascad.at)
Date: 02/21/05


Date: Mon, 21 Feb 2005 17:56:17 +0100

Adam Hartshorne wrote:
>
> I think you may have misunderstood,

Maybe

> there are no actual point
> coordinates. Simply a list of points, a list of lines and a list that is
> been used to link lines to the points.
>
> What I am concerned with is the linking list. So say the following
>
> I = {10,10,4,6,5,5}
>
> That says lines 1 and 2 are linked to node 10, line 3 to node 4 etc etc
>
> What I want is a result of the search that gives me
>
> O = {10{1,2}, 5{5,6}}

Same strategy.
Set up a helper datastructure

  struct SortHelper
  {
     int NodeIndex;
     int OriginalPosition;
  }

and create an array (or whatever) of that:

I = { 10, 4, 8, 10, 4, 5 }

becomes

  { 10, 1 }
  { 4, 2 }
  { 8, 3 }
  { 10, 4 }
  { 4, 5 }
  { 5, 6 }

Now sort that array according to NodeIndex:

  { 4, 2 }
  { 4, 5 }
  { 5, 6 }
  { 8, 3 }
  { 10, 1 }
  { 10, 4 }

and scan through it: there are 2 consecutive '4' Nodes in the list and they
appeared in the original I at positions 2 and 5. '5' is single and thus
of no interest to you (if I understand correctly), same for '8'. But then
there is 10 which occours 2 times in I at positions 1 and 4.

The strategy is always the same. If you need to compare each element with each
other element in a datastructure, you have a potential O(n^2) algorithm. If
possible (and often it is), sort that thing such that equal elements get
consecutive. Sorting is of order O(n*log(n)), plus an additional O(n) for
running through the data structure and sorting things out. Much better
then O(n^2) for large values of n.

-- 
Karl Heinz Buchegger
kbuchegg@gascad.at


Relevant Pages

  • Re: A Fast sorting algorithm for almost sorted data
    ... far my compressor has potential but is nowhere near ready. ... It does however make heavy use of sorting. ... which I am currently calling Run sort. ... entire selected run can be added to the sorted output array. ...
    (comp.compression)
  • Re: Sorting routine
    ... n RSHIFT shifts n bits. ... in the output array. ... This would be handy for sign sorting of 2's complement. ... So Radix/Distribution sort is about 1.4 times faster than Sedge's Sort. ...
    (comp.lang.forth)
  • Re: sorting columns
    ... Because sorting an N-element list requires something like 2 N log N ... the sort algorithms refer to an element by its index number. ... What do you mean with two-dimensional array? ... or does each second-level-array contain the relevant cell content ...
    (comp.lang.javascript)
  • Re: indirect sort
    ... I wrote a Comparator (I don't want to use ... Comparable in order to be able to choose the field I am sorting by) ... a way to create a doublearray of my fields I want to sort by, ...
    (comp.lang.java.programmer)
  • Re: "Sorting" assignment
    ... And many others prefer to call partition exchange because "quicksort" ... bin B depending on whether it is greater than, ... If the array is already sorted, this means that you end up ... attempt to sort them. ...
    (comp.programming)