Jump to content

Sort question in C++


Go to solution Solved by Danyfirex,

Recommended Posts

Hi everybody,

I'm a total newbie in C++ . Just started it a couple of days ago using CodeBlocks IDE (which includes the MinGW compiler).
I found a script that gives a good sort result when the array is composed of integers.
But if I try to adapt it to doubles, then the sorting isn't accurate.

Let's start with integers :

/* qsort example */
#include <stdlib.h>     /* qsort */
#include <iostream>
using namespace std;

int values[10] = { 40, 10, 100, 90, 20, 25, -50, -100, -1, 65 };

int compare (const void* a, const void* b) {
    return ( *(int*)a - *(int*)b );
}

int main () {
    qsort (values, 10, sizeof(int), compare);
    for (int n=0; n<10; n++) {
        cout << values[n] << endl;
    }
    return 0;
}

Correct console result :

-100
-50
-1
10
20
25
40
65
90
100

Now let's try it for doubles :

/* qsort example */
#include <stdlib.h>     /* qsort */
#include <iostream>
using namespace std;

double values[10] = { -9.9995, 9.9995, -9.9997, 9.9997, -9.9996, 9.9996,
                      -9.9999, 9.9999, -9.9998, 9.9998 };

int compare (const void* a, const void* b) {
    return ( *(double*)a - *(double*)b );
}

int main () {
    qsort (values, 10, sizeof(double), compare);
    for (int n=0; n<10; n++) {
        cout << values[n] << endl;
    }
    return 0;
}

Console result :

-9.9995
-9.9999
-9.9997
-9.9996
-9.9998
9.9995
9.9999
9.9996
9.9997
9.9998

Doubles aren't accurately sorted in the reworked script. Any idea what went wrong ?

Thanks

Link to post
Share on other sites

I'd check the double-to-integer conversion you are doing in the compare function, floating math may not function like you'd expect.

An unrelated suggestion: You might wanna start with C first as it's the basis of C++ but it's a lot simpler in concept, nailing the fundamentals will really help you later in your C/C++ journey :)

EasyCodeIt - A cross-platform AutoIt implementation

DcodingTheWeb Forum - Follow for updates and Join for discussion

Link to post
Share on other sites
  • Solution

Change your compare function to:

 

int compare(const void *x, const void *y)
{
  double xx = *(double*)x, yy = *(double*)y;
  if (xx < yy) return -1;
  if (xx > yy) return  1;
  return 0;
}

Saludos

Link to post
Share on other sites

My journey through C++ :)
I just "created" a very short script in C++ for sorting a structure of integers, then compiled it into a dll and called it from AutoIt. Markyrocks did that in another thread a few days ago but I wanted to try all this by myself. Here is the result :

C++ code is 1 file only, named "main.cpp", here is its content :

#include <stdlib.h>     /* qsort */

int comp (const void* x, const void* y) {
    return *(int*)x - *(int*)y;
}

extern "C" void __declspec(dllexport) my_sort(int* my_struct, int nb_elem) {
    qsort(my_struct, nb_elem, sizeof(int), comp);
}

AutoIt code for testing  :

#include <WinAPIDiag.au3>

$iNb_elem = 10000 ; change this value for testing less or more elements

$hDLL  = DllOpen(@ScriptDir & "\Structure 03.dll")
If $hDLL = -1 Then Exit Msgbox(0, "DllOpen", "error occured")

_SplashOn("Filling structure")
$tStruct = DllStructCreate("int arr[" & $iNb_elem & "]")
For $i = 1 To $iNb_elem
    $tStruct.arr(($i)) = Random(-100000, +100000, 1) ; note (($i)) and not ($i) <=================
Next
SplashOff()

If $iNb_elem <= 10000 Then
    _SplashOn("Displaying structure #1")
    _WinAPI_DisplayStruct($tStruct, "int arr[" & $iNb_elem & "]", "$tStruct UNsorted")
    SplashOff()
EndIf

$hTimer = TimerInit()
$aRet = DllCall($hDLL, "none:cdecl", "my_sort", "ptr", DllStructGetPtr($tStruct), "int", $iNb_elem)
If @error Then Exit Msgbox(0, "DllCall", "error " & @error & " occured")

If IsArray($aRet) Then
    ConsoleWrite($iNb_elem & " elements sorted in " & TimerDiff($htimer) & " ms" & @CRLF)
    If $iNb_elem <= 10000 Then
        _SplashOn("Displaying structure #2")
        _WinAPI_DisplayStruct($tStruct, "int arr[" & $iNb_elem & "]", "$tStruct sorted")
        SplashOff()
    EndIf
Else
    Exit Msgbox(0, "error", "$aRet is not an Array")
EndIf

DllClose($hDLL)

;==========================================================
Func _SplashOn($sFirstLine, $sSecondLine = "please wait...")
    SplashTextOn("", $sFirstLine & @CRLF & $sSecondLine, _
        250, 50, -1, -1, $DLG_NOTITLE + $DLG_TEXTVCENTER)
EndFunc   ;==>_SplashOn

Results (with 10 elements only (for pics convenience) :

629620664_Structure03UNsorted.png.3f5250d27dcf16899203a87032d89007.png

315506327_Structure03sorted.png.1835c0eb8fb30f7d574a85e1d2c6f40a.png

Notes : the AutoIt variable $iNb_elem contains the number of elements for the test.
* Until 10.000 elements, it will sort then display the results in the _WinAPI_DisplayStruct() GUI as shown in the above pics
* If > 10.000 elements, it will sort but won't display anything (because it may take too long to display). This 10.000 value for displaying can be easily changed in the script)

In all cases, the time for sorting will show in AutoIt console. For example, on my old PC, it sorts 1 million elements in less than 1s

AutoIt Console :

1000000 elements sorted in 493.493167427704 ms

I have no idea if I should attach the dll or not because VirusTotal indicates that 1AV (out of 66 !) flags the dll malicious (this AV is named ESET-NOD32) . Anyway, you got the C++ code so you can compile it by yourself if interested, in case you have the appropriate tool for that (I used the MinGW compiler found in CodeBlocks IDE)

My next step is to rework the Dll to allow float & doubles sorting too. If you guys have comments on the C++ code above, please don't hesitate to comment as I'm a total beginner in C++ 

Mods : could you please be kind enough and suppress my precedent deleted message ?

Thanks :)

Edited by pixelsearch
shortened C++ code
Link to post
Share on other sites

@pixelsearch I try to write your C++ code in Freebasic.
To run the code you can use this site https://www.jdoodle.com/execute-freebasic-online/

1st time I am coding using Freebasic so getting warning, may be @UEZ can point out my mistake.
warning 3(2): Passing different pointer types...

#include "crt/stdlib.bi"

Declare Function QCompare cdecl (ByVal e1 As Any Ptr, ByVal e2 As Any Ptr) As Integer

Sub PrintArray( karray() As Integer )
    For position As Integer = LBound(karray) To UBound(karray)
        Print karray(position) ;
    Next
    Print  !"\n";
End Sub

Function QCompare cdecl (ByVal e1 As Any Ptr, ByVal e2 As Any Ptr) As Integer
  Return (*(CPtr(Integer Ptr, e1)) - *(CPtr(Integer Ptr, e2)))
End Function

Dim oarray(9) As Integer = { 10, 9, 6, 8, 5, 1, 3, 2, 7, 4 }

PrintArray( oarray() )
qsort @oarray(0), 10, Sizeof(Integer), @QCompare
PrintArray( oarray() )

 

Sub PrintArray( karray() As Integer )
    For position As Integer = LBound(karray) To UBound(karray)
        Print karray(position) ;
    Next
    Print  !"\n";
End Sub

Function Partition( Array() As Integer, start As Integer, oEnd As Integer) As Integer
    Dim pivot as Integer
    Dim t as Integer
    Dim As Integer i, j

    pivot = Array(oEnd)
    i = (start - 1)
    For j = start To oEnd - 1
        If (Array(j) < pivot) Then
            i = i + 1
            t = Array(i)
            Array(i) = Array(j)
            Array(j) = t
        End If
   Next
    t = Array(i + 1)
    Array(i+1) = Array(oEnd)
    Array(oEnd) = t
    Partition = (i + 1)
End Function

Sub quickSort( Array() As Integer, start As Integer, oEnd As Integer)
    Dim p As Integer
    If (start < oEnd) Then
        p = Partition(Array(), start, oEnd)
        quickSort(Array(), start, p - 1)
        quickSort(Array(), p + 1, oEnd)
    End If
End Sub

Dim oarray(9) As Integer = { 10, 9, 6, 8, 5, 1, 3, 2, 7, 4 }

PrintArray( oarray() )
quickSort( oarray(), 0, UBound(oarray))
PrintArray( oarray() )

 

Edited by jugador
Link to post
Share on other sites
2 hours ago, jugador said:

1st time I am coding using Freebasic so getting warning, may be @UEZ can point out my mistake.
warning 3(2): Passing different pointer types...

You have to cast the last parameter (pointer to function):

qsort @oarray(0), 10, Sizeof(Integer), Cast(Any Ptr, @QCompare)

 

Or use Quicksort written in FB:

Sub QsortA(array() As Integer, _start As Integer, _end As Uinteger) 'ascending
    _end = Iif(_end > Ubound(array), Ubound(array), _end)
    _start = Iif(_start < 0, 0, _start)
    Dim As Integer I = _start, J = _end
    Dim As Integer X = array(((I + J) \ 2))
    While I <= J
        While array(I) < X  'change to > for descending
            I += 1
        Wend
        While array(J) >'change to < for descending
            J -= 1
        Wend
        If I <= J Then
            Swap array(I), array(J)
            I += 1
            J -= 1
        Endif
    Wend
    If J > _start Then QsortA(array(), _start, J)
    If I < _end Then QsortA(array(), I, _end)
End Sub

Sub PrintArray( karray() As Integer )
    For position As Integer = LBound(karray) To UBound(karray)
        Print karray(position) ;
    Next
    Print  !"\n";
End Sub


Dim oarray(9) As Integer = { 10, 9, 6, 8, 5, 1, 3, 2, 7, 4 }

PrintArray( oarray() )
QsortA( oarray(), 0, Ubound(oarray))
PrintArray( oarray() )

Sleep

 

Edited by UEZ

Please don't send me any personal message and ask for support! I will not reply!

Selection of finest graphical examples at Codepen.io

The own fart smells best!
Her 'sikim hıyar' diyene bir avuç tuz alıp koşma!
¯\_(ツ)_/¯  ٩(●̮̮̃•̃)۶ ٩(-̮̮̃-̃)۶ૐ

Link to post
Share on other sites

 I got no issues with this.  Would have been nice to get a tag.  Pixelsearch seems like one of the good ones.  If anyone was following the other thread as I said in there the new version is drastically different than this.  The whole thing was essentially rewritten to get rid of any copying except when absolutely necessary (strings) .  That being said it doesn't even need a struct it just sorts the pointers at the actual autoit variant type variable.   That and I eliminated all calls to processread/write.  I'm almost ready to drop a new version.   Getting to the strings is some Uber obscure syntax but I got em.  I promise I'm not going to hijack this thread.  I would have helped out but I didn't see this until just now.  It took me roughly 5 years to get to this point with c++.  I'm like so good with it I'm beginning to think that I can see into the future.   Joking.  Goodluck.  Take care. 

Link to post
Share on other sites
  • Developers
2 hours ago, markyrocks said:

If anyone was following the other thread as I said in there the new version is drastically different than this.  The whole thing was essentially rewritten to get rid of any copying except when absolutely necessary (strings) . 

You can't leave it alone can you and even listen to a simple request,  so let me make it very and ultimately simple for you:

Consider this your final warning. Post one other comment like this and you will be removed from our forums.

Jos

Edited by Jos

SciTE4AutoIt3 Full installer Download page   - Beta files       Read before posting     How to post scriptsource   Forum etiquette  Forum Rules 
 
Live for the present,
Dream of the future,
Learn from the past.
  :)

Link to post
Share on other sites
  • 2 weeks later...

Hi everybody 
A few days ago, I was lucky to discover in this link a thread from @funkey (dated from 2013) where we can find a part in AutoIt and a part in C. funkey's script is interesting, not only for its content, but it helps to learn C and C++ when you're a newbie like me, as it's nicely written.

As I found it challenging, then I tried to write some simple code to quickly sort a 1D array of strings (creating a dll) and the result look promising :)

First of all, here is my code in AutoIt :

#include <Array.au3>

$hDLL = DllOpen(@ScriptDir & "\rrr.dll")
If $hDLL = -1 Then Exit Msgbox(0, "DllOpen", "error occured")

;======================================
Local $aArray[14] = ["john", "bobby", "hello", "test", "catherine", "nomi", "shinta", _
                       "martin", "abe", "may", "zeno", "zack", "angel", "gaby"] ; 56 + 14 delim => 80

; OR for more elements :

;~ Local $iItems = 100000, $aArray[$iItems]
;~ FillArray($aArray, $iItems)

;======================================
Local $iNbElem = Ubound($aArray), $sDelim = chr(1), $sData = ""

For $i = 0 To $iNbElem - 1
    $sData &= $aArray[$i] & $sDelim
Next

_ArrayDisplay($aArray, "UNsorted")

;====================
$hTimer = TimerInit()

$iBufferSize = StringLen($sData)
$tStruct = DllStructCreate("char[" & $iBufferSize & "]")
If @error Then Exit Msgbox(0, "DllStructCreate", "error " & @error)

DllStructSetData($tStruct, 1, $sData)
If @error Then Exit Msgbox(0, "DllStructSetData", "error " & @error)

ConsoleWrite("Writing structure = " & TimerDiff($htimer) & " ms" & @crlf)

MsgBox(0, "Pointer of struct", DllStructGetPtr($tStruct) & "   Buffer size = " & $iBufferSize)

;====================
$hTimer = TimerInit()

$aRet = DllCall($hDLL, "int:cdecl", "StringSort", "ptr", DllStructGetPtr($tStruct), "str", $sDelim, "int", $iNbElem)
If @error Then Exit Msgbox(0, "DllCall StringSort", "error " & @error)

ConsoleWrite("DllCall = " & TimerDiff($htimer) & " ms" & @crlf)

_ArrayDisplay($aRet, "$aRet")

;====================
$hTimer = TimerInit()

$sSorted = DllStructGetData($tStruct, 1)
If @error Then Exit Msgbox(0, "DllStructGetData", "error " & @error)

Local $aArray2 = StringSplit($sSorted, Chr(1), 2) ;  $STR_NOCOUNT = 2

ConsoleWrite("Reading structure = " & TimerDiff($htimer) & " ms" & @crlf)

_ArrayDisplay($aArray2, "Sorted")

_StringSplitFree($tStruct)

DllClose($hDLL)

;======================================
Func FillArray( ByRef $aItems, $iItems ) ; LarsJ (fill array with random strings)
    Local $aLetters[26] = [ 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', _
                            'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' ], $s
    For $i = 0 To $iItems - 1
        $s = $aLetters[Random(0,25,1)]
        For $j = 1 To Random(10,30,1)
            $s &= $aLetters[Random(0,25,1)]
        Next
        $aItems[$i] = $s
    Next
EndFunc   ;==>_FillArray

;======================================
Func _StringSplitFree(ByRef $tStruct) ; Funkey
    DllCall("msvcrt.dll", "none:cdecl", "free", "ptr", DllStructGetPtr($tStruct))
    If @error Then Exit Msgbox(0, "DllCall Free", "error " & @error & " occured")
    $tStruct = 0
EndFunc   ;==>_StringSplitFree

Now the C/C++ code :

#include <algorithm>     // sort
#include <string.h>      // strtok, strcpy
using namespace std;

extern "C" __declspec(dllexport) int StringSort(char* structure, char* sdelim, int inbelem)
{
    string arr[inbelem];
    int i = 0, ipos = 0;
    char* p;

    p = strtok(structure, sdelim); // split string into tokens (returns a pointer).
                                   // End of the token (delimiter) is automatically replaced by a null-character
                                   // https://www.cplusplus.com/reference/cstring/strtok/
    while ((p != NULL) && (i < inbelem))
        {
            arr[i] = p;
            p = strtok(NULL, sdelim);
            i++;
        }

    sort(arr, arr + inbelem);

    for(i = 0; i < inbelem; ++i)
        {
            strcpy(&structure[ipos], (arr[i] +
                ((i < inbelem - 1) ? sdelim : "")).c_str()); // strcpy adds a x00 at the end

            ipos += arr[i].size() + 1; // overwrite each preceding x00 from strcpy
        }

    return 1;
}

The result on 100.000 random strings looks great on my antique computer. This is what AutoIt console shows for 100.000 sorted strings :

Writing structure = 69.5580024835559 ms
DllCall = 581.134194429739 ms
Reading structure = 585.444239421491 ms

Here are the different phases I went through, based on a simpler array of 14 strings (also found in the AutoIt code) :

* create a string composed of all the (unsorted) array elements, separated by a delimiter. I choosed chr(1) as delimiter, maybe we'll discuss this point later in case you guys have a better idea. There's also a delimiter chr(1) at the end of the string.

* Still in AutoIt, create a structure of char's and populate it with a single instruction (no loop) . Here is what the corresponding memory dump shows at this exact moment :

2135927720_beforeCsort.png.ac0f5548f544e40cae2c6a54a21360eb.png

* DllCall : this phase will :

a) Split the big unsorted string found in the structure, ending with tokens (each token is an element of a new C array) . It's the C strtok instruction that splits and create tokens.
b) Then Sort the Array of strings using C Sort
c) Finally overwrite the structure using C strcpy instruction, overwriting carefully each chr(0) that strtok added (it replaced all my separators chr(1) with chr(0) !) . So we'll replace all chr(0) with the originals chr(1)
Watch out carefully for the last byte of the buffer, to avoid ending with a "buffer overflow"... only for one last byte !
Here is what the corresponding memory dump shows at this exact moment : the strings are sorted and there's no buffer overflow if you look at the 81th byte which is outside the buffer (its content is still 0B as in the preceding pic) :

2030898097_afterCsort.png.94abb5aa8248b59485d65508cc51dffa.png

* Back to AutoIt : now we read the structure with 1 instruction (no loop) and StringSplit is used to immediately create a new sorted array, that's it.

I compiled the C/C++ code with the the free MinGW compiler found in CodeBlocks 17.12 IDE . In case you're interested, it should be easy for you to do same.

Thanks for reading :)

Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Recently Browsing   0 members

    No registered users viewing this page.

×
×
  • Create New...