From: Zyt3x
Nice! I knew you'd have some kind of hack :)
Doesn't help much towards the generic quicksort function though, since we'd need a "hacked" swap function as well
From: Dgby714
Write a quicksort method that uses a pointer and some type info (say item size, and count?) then write wrapper for each array type
This is the best I could come up with in all honesty:
Function PtrLength(Ptr: Pointer): UInt32;
type
PUInt32 = ^UInt32;
begin
Result := (PUInt32(Ptr) - sizeof(UInt32))^ + 1;
end;
Procedure PtrSwap(A, B: Pointer; Size_Ptr: Integer);
type
BytePtr = ^Byte;
var
I: Integer;
T: Byte;
Begin
T := 0;
While (I < Size_Ptr) Do
Begin
T := BytePtr(A[I])^;
BytePtr(A[I])^ := BytePtr(B[I])^;
BytePtr(B[I])^ := T;
Inc(I);
End;
End;
Procedure PtrSort(List: Pointer; Size_Ptr: Integer; Comparator: Function(A, B: Pointer): Boolean);
var
Size: Integer;
I, J: Integer;
Begin
I := 0;
Size := PtrLength(List) * Size_Ptr;
While(I < Size) Do
Begin
J := 0;
While(J < Size - I - Size_Ptr) Do
Begin
If (Comparator(List[J + Size_Ptr], List[J])) Then
PtrSwap(List[J + Size_Ptr], List[J], Size_Ptr);
J := J + Size_Ptr;
End;
I := I + Size_Ptr;
End;
End;
Function IntComparator(A, B: Pointer): Boolean;
Begin
Result := Integer(A^) < Integer(B^);
End;
Function CharComparator(A, B: Pointer): Boolean;
Begin
Result := Char(A^) < Char(B^);
End;
Function FloatComparator(A, B: Pointer): Boolean;
Begin
Result := Extended(A^) < Extended(B^);
End;
Function TPointXSorter(A, B: Pointer): Boolean;
Begin
Result := TPoint(A^).X < TPoint(B^).X;
End;
var
CA: TCharArray;
IA: TIntegerArray;
FA: Array Of Extended;
PA: TPointArray;
begin
CA := ['a', 'j', 'c', 'i', 'h', 'g', 'd', 'e', 'b', 'f'];
IA := [1, 3, 9, 7, 2, 4, 10, 6, 5, 8];
FA := [1.0, 1.3, 1.9, 1.7, 1.2, 1.4, 1.1, 1.6, 1.5, 1.8];
PA := [Point(1, 0), Point(3, 10), Point(9, 11), Point(7, 200), Point(2, 2), Point(4, 1), Point(10, 13), Point(6, 7), Point(5, 3), Point(8, 4)];
PtrSort(@CA[0], SizeOf(CA[0]), @CharComparator);
writeln(CA);
PtrSort(@IA[0], SizeOf(IA[0]), @IntComparator);
writeln(IA);
PtrSort(@FA[0], SizeOf(FA[0]), @FloatComparator);
writeln(FA);
PtrSort(@PA[0], SizeOf(PA[0]), @TPointXSorter);
writeln(PA);
end.
[a, b, c, d, e, f, g, h, i, j]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 1.1, 1.2, 1.3, 1.4, 1.5, 1.6, 1.7, 1.8, 1.9]
[{X = 1, Y = 0}, {X = 2, Y = 2}, {X = 3, Y = 10}, {X = 4, Y = 1}, {X = 5, Y = 3}, {X = 6, Y = 7}, {X = 7, Y = 200}, {X = 8, Y = 4}, {X = 9, Y = 11}, {X = 10, Y = 13}]
With the above hackery, all that is required of the user is to create functions for comparing as follows:
Function IntComparator(A, B: Pointer): Boolean;
Begin
Result := Integer(A^) < Integer(B^);
End;
Function CharComparator(A, B: Pointer): Boolean;
Begin
Result := Char(A^) < Char(B^);
End;
Function FloatComparator(A, B: Pointer): Boolean;
Begin
Result := Extended(A^) < Extended(B^);
End;
Function TPointXSorter(A, B: Pointer): Boolean;
Begin
Result := TPoint(A^).X < TPoint(B^).X;
End;
Function SomethingComparator(A, B: Pointer): Boolean;
Begin
Result := Something(A^) < Something(B^); //Use less-than for ascending order OR use greater-than to sort in descending order..
End;
You pass the comparator function to the generic sort function and voila, it sorts whatever data it is you are trying to sort..
If anyone wants a proper explanation, just let me know and I'll write how it works.. You'll need to understand how swaps truly work (using byte swapping) and a lot of pointer arithmetic..
Not many would care how it works.. Just as long as it does.. And it does.
