[Solved] Sort String Grid more than 1 column

[dcelso]

Hello,
Is possible to sort stringGrids by more than one column?

Currently I put column clic sort property to true.

But if I do to sort a column and after I do to sort another column, I lost the sorted first column.

For example in JAVA swing it does not happend.

An example may be the next


col1    col2
A         aa
B         ss
A         zz
C         aa
A         gg
D         zz


If i sort by col2 the result is

col1    col2
A         aa
C         aa
A         gg
B         ss
A         zz
D         zz

Then if I sort by col 1 now, the result is the next

col1    col2
A         aa
A         zz
A         gg
B         ss
C         aa
D         zz


Instead of I was spected, that is the next
col1    col2
A         aa
A         gg
A         zz
B         ss
C         aa
D         zz

Because col2 was sorted before, I do not understad what are doing string grid sort to do not do it.

Any Idea?

[BigChimp]

IIRC, you can specify your own custom sorting algorithms for grids...

[BigChimp]

See
http://wiki.lazarus.freepascal.org/Grids_Reference_Page#Sorting_Columns_or_Rows
about
the OnCompareCells event

[JuhaManninen]

Yes, your custom sort could compare multiply columns.
There are also sorting algorithms that preserve the already sorted order better. One is TimSort:
  http://en.wikipedia.org/wiki/Timsort
If I understood right, it would behave just as you explained when sorting by one column. Mattias Gärtner had a plan to replace the current QuickSort with TimSort but maybe it was buried under other priorities. I must ask him.

[JuhaManninen]

I took the liberty to copy parts of the answer from Mattias here:
"
TimSort is a more optimized version of QuickSort, so it is in many cases
faster and some cases slower. Another disadvantage is that it needs to
allocate n div 2 temporary memory. So it is not a good replacement for
the default QuickSort of TFPList.

José Mejuto <joshyfun@gmail.com> did one implementation, but in my
tests it had so much overhead that it was often slower than the normal
QuickSort.
"

There were some other problems in the code, too. Maybe José Mejuto (joshyfun) can explain more himself.

Yet I think TimSort would make lots of sense in Grid components if it really solves the problem presented here. If somebody makes a well-tested patch that implements TimSort as a default algorithm for grids, I am sure it can be applied.

[Martin_fr]

This should not be about Sorting-Algorithm. And it should already be possible.

To sort by more than one column, it would be inefficient to sort twice (first by one column, then by another while preserving the last order for cells that equal in the 2nd run)

The sort should be done in a single run. When 2 rows are compared, then it should compare all involved columns (according to their priority in the sorting) until a column is found in which the rows differ.

StringGrid has OnCompareCells. This is called during sort. So it can be done

If you sort first by column n, and 2nd by column m, then it will be called with cells from various rows, but all from that column.
But if the 2 cells are equal then OnCompareCells should compare the values in column m (for the same rows).
This can be done with any amount of columns.

All that is needed, is to store the entire sorting info before calling sort. in a place readable from OnCompareCells.

There is no need to change the algorithm for this.

[JuhaManninen]

This should not be about Sorting-Algorithm. And it should already be possible.
To sort by more than one column, it would be inefficient to sort twice (first by one column, then by another while preserving the last order for cells that equal in the 2nd run)

The problem comes up when the user has set ColumnClickSorts = True, or implemented the same functionality otherwise.
Sorting by clicking columns is a very common thing, yet it had to be implemented again and again in user code for TStringGrid.
Finally I decided to implement a property for it. It sorts and shows an up/down icon for the sorted column.
I remember Vincent and Mattias already then mentioned the order of consecutive sorts is wrong because the algorithm does not preserve the order of keys with equal values.
TimSort was mentioned as a possible solution then.

[mattias]

I agree with Martin that the column issue should be handled in the compare function, instead of applying multiple sorts.

For the column approach:
MergeSort for TFPList is available in LCLProc and keeps order.
It has a stable runtime of O(n*logn).

[JuhaManninen]

I agree with Martin that the column issue should be handled in the compare function, instead of applying multiple sorts.

Yes, if the column order is known in advance. It is not known when a user just clicks the column headers. Multiple clicks lead to multiple sorts.

For the column approach:
MergeSort for TFPList is available in LCLProc and keeps order.
It has a stable runtime of O(n*logn).

Ok, I did not realize that. Maybe somebody creates a patch with MergeSort.

[dcelso]

thanks to all responses,
Finally I solved it merging a litte of all ideas
I created a my custom tstringrid that i override the sort method, to use the stringlist sort method (that uses mergesort of tfplist) seems use quick sort too
So I need create a stringlist to sort, so I need convert a entire row in a string using a char separator. and put in the first place the contend of the column to sort.

The result may be a very slow sort but is enough for me for now .

All feathures to this code are welcome

Code: [Select]

procedure TStringGridMio.Sort(ColSorting: Boolean; index, IndxFrom, IndxTo: Integer);
  procedure Split
     (const Delimiter: Char;
      Input: string;
      const Strings: TStrings) ;
  begin
     Assert(Assigned(Strings)) ;
     Strings.Clear;
     Strings.StrictDelimiter := true;
     Strings.Delimiter := Delimiter;
     Strings.DelimitedText := Input;
  end;

var
  list : TStringList;
  splitted : TStringList;
  i,j,k : integer;
  line : String;
  string1 : string;
begin
    if RowCount>FixedRows then begin
    CheckIndex(ColSorting, Index);
    CheckIndex(not ColSorting, IndxFrom);
    CheckIndex(not ColSorting, IndxTo);
    BeginUpdate;

    list := TStringList.Create;
    splitted := TStringList.Create;

    line :='';
    for i:= indxFrom to indxTo  do
    begin
      line := Cells[index,i] + chr(9);
      for j:= FixedCols to ColCount -1  do
      begin
        if j <> index then
        begin
          line := line + Cells[j,i] + chr(9);
        end;
      end;
      list.Add(line);
    end;

    list.Sort;

    for i:= 0 to list.Count-1  do
    begin
       split(chr(9),list.Strings[i],splitted);
       string1 := splitted[0];
       Cells[index,IndxFrom+i] := string1;
       k:= 1;
       for j:= FixedCols to ColCount -1  do
       begin
         if j <> index then
         begin
           string1:=splitted[k];
           Cells[j,IndxFrom+i]:=string1;
           k:=k +1;
         end;
       end;
    end;
    splitted.free;
    list.free;
    EndUpdate;
  end;
end;


[dcelso]

This is another faster solution than before.
Instead of compare all entire data row, only compare the column selected data and uses mergesort to do the compare. To do it you need an auxiliar list with the old index and de data to compare to later with this list sorted, create the result list correcly.

Code: [Select]

procedure TStringGridMio.Sort(ColSorting: Boolean; index, IndxFrom, IndxTo: Integer);
  procedure DuplicateRow( index_row : integer) ;
  var
    j : integer;
  begin
    rowcount := rowcount +1;
    for j:= FixedCols to ColCount -1  do
    begin
        Cells[j,rowcount-1] := Cells[j,index_row];
    end;
  end;

var
  list : TFPList;
  i,j,k : integer;
  string1 : string;
  PDataSortable : ^DataSortable;
begin
    if RowCount>FixedRows then begin
    CheckIndex(ColSorting, Index);
    CheckIndex(not ColSorting, IndxFrom);
    CheckIndex(not ColSorting, IndxTo);
    BeginUpdate;

    list := TFPList.Create;

    for i:= indxFrom to indxTo  do
    begin
      new (PDataSortable);
      PDataSortable^.index:=i;
      PDataSortable^.value:=Cells[index,i];
      list.Add(PDataSortable);
    end;

    MergeSort(list,@CompareDataSortable) ;

    for i:= 0 to list.Count-1  do
    begin
      PDataSortable:=list.Items[i];
      DuplicateRow(PDataSortable^.index);
      Dispose(PDataSortable);
    end;
    for i:= indxFrom to indxTo  do
    begin
      DeleteRow(indxFrom);
    end;
    list.free;
    EndUpdate;
  end;
end;