Recent

Author Topic: Sort Routine  (Read 1376 times)

JLWest

  • Hero Member
  • *****
  • Posts: 806
Sort Routine
« on: January 04, 2020, 08:04:01 am »
I have a text file with 43K+- lines. Each line has 11 fields. ( example below )
They are loaded in an array. I need to be able to sort the records by various fields. Say one sort by field 3 and another time by field 7.

A bubble sort doesn't work well. I have done a search on sorts and some reading there are a few examples and a lot of discussion.

Wondering what kind of sort routine would work best and is there an code example.


Note: this is all one line:
|Nil|XED2H|ED|[H] Niebuell Kreiskrankenhaus|Nil|Schleswig-Holstein|Germany|54.79384949|008.84454735|I|O|

Thanks
FPC 3.2.0, Lazarus IDE v2.0.4
 Windows 10 Pro 32-GB
 Intel i7 770K CPU 4.2GHz 32702MB Ram
GeForce GTX 1080 Graphics - 8 Gig
4.1 TB

julkas

  • Hero Member
  • *****
  • Posts: 628
  • KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: Sort Routine
« Reply #1 on: January 04, 2020, 10:40:25 am »
If you want old style take a look at Wolfgang Ehrhardt's util archive (sort.pas unit).
Search forum.

Happy New Year.
Regards.

procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

howardpc

  • Hero Member
  • *****
  • Posts: 3487
Re: Sort Routine
« Reply #2 on: January 04, 2020, 12:34:53 pm »
Why not use all the code Jesus Reyes has already written in the grids unit?
Add a line such as
Code: Pascal  [Select][+][-]
  1. |0|1|2|3|4|5|6|7|8|9|10|
as the first line of your data file.

Drop a TStringGrid on your main form.
Set its properties along these lines:
Code: Pascal  [Select][+][-]
  1.   Grid.FixedCols := 0;
  2.   Grid.LoadFromCSVFile('your data file.txt','|',True);
  3.   Grid.AutoSizeColumns;
  4.   Grid.ColumnClickSorts := True;

Now a simple click on the column header sorts the strings. To sort numeric columns you have to do a bit of work yourself.
If you strip the opening and closing '|' from each line of your data file you will avoid having empty first and last columns in the grid.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8244
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Sort Routine
« Reply #3 on: January 04, 2020, 12:39:24 pm »
I don't know what your field types are, but commonly if it involves complex types such as strings, merge sort will perform the best as it uses the fewest comparison. Plus, it's stable.

valdir.marcos

  • Hero Member
  • *****
  • Posts: 993
Re: Sort Routine
« Reply #4 on: January 04, 2020, 03:04:29 pm »
I have a text file with 43K+- lines. Each line has 11 fields. ( example below )
They are loaded in an array. I need to be able to sort the records by various fields. Say one sort by field 3 and another time by field 7.

A bubble sort doesn't work well. I have done a search on sorts and some reading there are a few examples and a lot of discussion.

Wondering what kind of sort routine would work best and is there an code example.

Note: this is all one line:
|Nil|XED2H|ED|[H] Niebuell Kreiskrankenhaus|Nil|Schleswig-Holstein|Germany|54.79384949|008.84454735|I|O|

If you want old style take a look at Wolfgang Ehrhardt's util archive (sort.pas unit).
Search forum.

Why not use all the code Jesus Reyes has already written in the grids unit?
Add a line such as
Code: Pascal  [Select][+][-]
  1. |0|1|2|3|4|5|6|7|8|9|10|
as the first line of your data file.

Drop a TStringGrid on your main form.
Set its properties along these lines:
Code: Pascal  [Select][+][-]
  1.   Grid.FixedCols := 0;
  2.   Grid.LoadFromCSVFile('your data file.txt','|',True);
  3.   Grid.AutoSizeColumns;
  4.   Grid.ColumnClickSorts := True;

Now a simple click on the column header sorts the strings. To sort numeric columns you have to do a bit of work yourself.
If you strip the opening and closing '|' from each line of your data file you will avoid having empty first and last columns in the grid.

I don't know what your field types are, but commonly if it involves complex types such as strings, merge sort will perform the best as it uses the fewest comparison. Plus, it's stable.
@JLWest
Why don't you use a cheap operation embedded database engine instead of an expensive operation large text file?

julkas

  • Hero Member
  • *****
  • Posts: 628
  • KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: Sort Routine
« Reply #5 on: January 04, 2020, 03:13:25 pm »
I have a text file with 43K+- lines. Each line has 11 fields. ( example below )
They are loaded in an array. I need to be able to sort the records by various fields. Say one sort by field 3 and another time by field 7.

A bubble sort doesn't work well. I have done a search on sorts and some reading there are a few examples and a lot of discussion.

Wondering what kind of sort routine would work best and is there an code example.

Note: this is all one line:
|Nil|XED2H|ED|[H] Niebuell Kreiskrankenhaus|Nil|Schleswig-Holstein|Germany|54.79384949|008.84454735|I|O|

If you want old style take a look at Wolfgang Ehrhardt's util archive (sort.pas unit).
Search forum.

Why not use all the code Jesus Reyes has already written in the grids unit?
Add a line such as
Code: Pascal  [Select][+][-]
  1. |0|1|2|3|4|5|6|7|8|9|10|
as the first line of your data file.

Drop a TStringGrid on your main form.
Set its properties along these lines:
Code: Pascal  [Select][+][-]
  1.   Grid.FixedCols := 0;
  2.   Grid.LoadFromCSVFile('your data file.txt','|',True);
  3.   Grid.AutoSizeColumns;
  4.   Grid.ColumnClickSorts := True;

Now a simple click on the column header sorts the strings. To sort numeric columns you have to do a bit of work yourself.
If you strip the opening and closing '|' from each line of your data file you will avoid having empty first and last columns in the grid.

I don't know what your field types are, but commonly if it involves complex types such as strings, merge sort will perform the best as it uses the fewest comparison. Plus, it's stable.
@JLWest
Why don't you use a cheap operation embedded database engine instead of an expensive operation large text file?

What is - embedded database engine ?
« Last Edit: January 04, 2020, 03:44:10 pm by julkas »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

valdir.marcos

  • Hero Member
  • *****
  • Posts: 993
Re: Sort Routine
« Reply #6 on: January 04, 2020, 03:46:14 pm »
@JLWest
Why don't you use a cheap operation embedded database engine instead of an expensive operation large text file?
What is - embedded database engine ?[/quote]
"An embedded database system is a database management system (DBMS) which is tightly integrated with an application software that requires access to stored data, such that the database system is "hidden" from the application’s end-user and requires little or no ongoing maintenance."
https://en.wikipedia.org/wiki/Embedded_database

I preferably use Firebird embedded, but there are many others alternatives.
Sometimes, projects come to me already using SQLite.

julkas

  • Hero Member
  • *****
  • Posts: 628
  • KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: Sort Routine
« Reply #7 on: January 04, 2020, 05:33:57 pm »
I preferably use Firebird embedded, but there are many others alternatives.
Sometimes, projects come to me already using SQLite.
Agree, if sort by is dynamic lite db may be the best solution.
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

johnmc

  • New Member
  • *
  • Posts: 31
Re: Sort Routine
« Reply #8 on: January 15, 2020, 06:48:57 pm »
To answer the original question, if you want to code your own sort routine quicksort is a much faster than a bubble sort.

https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Pascal

However as others have said there may be better solutions.

 

TinyPortal © 2005-2018