PureBasic Forums - English

Code: Select all

; English forum: http://www.purebasic.fr/english/viewtopic.php?t=7503&highlight=
; Author: Pupil (updated for PB4.00 by blbltheworm + Andre)
; Date: 16. September 2003
; OS: Windows
; Demo: Yes


; With this small assembly of previous post you can now easily compare the different
; sorting algorithms. The code below contains some algorithms that has already been
; posted, i.e. the basic BubbleSort and oldefoxx's "fastest" bubblesort variation.
; New sorting algoritms are the CombSort and the QuickSort algorithm (quicksort as
; found in the PB examples folder). 

; The CombSort algorithm is a modification of bubblesort that addresses the weakness
; of propagation from bottom to top in the bubblesort algorithm. CombSort was published
; by Box And Lacey in 1991. The algorithm is so much more efficient than the original
; bubblesort that it is in fact comparable to some of the best sorting algorithms
; there is, like QuickSort and HeapSort to name a few. In the CombSort algorithm the
; optimal value of the shrinkFactor vary from one array to another, but doesn't stray
; far away from the value 1.3. 


;- Code: 

; Compare sort algorithms: 
; BubbleSort, modified BubbleSort, CombSort, 
; QuickSort and PB internal SortArray() command 
; 


ImportC "msvcrt.lib" 
  ftime( a ) As "__ftime@4"
EndImport


Structure _timeb
  time.l
  milli.w
  tz.w
  flag.w
EndStructure


#NMAX = 500000
Global Dim dummy.l(0) 
Global Dim array.l(#NMAX) 

Global t1._timeb
Global t2._timeb

DisableDebugger

; QuickSort - From PureBasic Advanced examples 
; 
Declare QuickSortRecursive(g.l, d.l) 

Procedure QuickSort(*ptr, n.l) 
  ; small dummy() wrapper. 
  tmpAddress.l = @dummy() 
  dummy() = *ptr 
  QuickSortRecursive(0, n) 
  dummy() = tmpAddress 
EndProcedure 

Procedure QuickSortRecursive(g.l, d.l) 
  If g < d 
    v = dummy(d) 
    i = g-1 
    j = d 
    Repeat 
      Repeat 
        i=i+1 
      Until dummy(i) >= v 
      ok = 0 
      Repeat 
        If j>0 
          j=j-1 
        Else 
          ok=1 
        EndIf 
        If dummy(j) <= v 
          ok=1 

        EndIf 
      Until ok<>0 
      tmp.l = dummy(i) 
      dummy(i) = dummy(j) 
      dummy(j) = tmp 
    Until j <= i 
    
    t = dummy(j) 
    dummy(j) = dummy(i) 
    dummy(i) = dummy(d) 
    dummy(d) = t 
    
    QuickSortRecursive(g, i-1) 
    QuickSortRecursive(i+1, d) 
  EndIf 
EndProcedure 

; Fill Array with random numbers 
For i = 0 To #NMAX 
  array(i) = Random($FFFF)
   ;array(i) = Random(32767)
Next 

; Need the exact conditions for both tests 
; so copy array. 
Mem = AllocateMemory(#NMAX*4+4)
If Mem = 0
  End 
EndIf 

CopyMemory(@array(0), Mem, #NMAX*4+4) 

; Time the QuickSort algorithm 
ftime(@t1) 
QuickSort(Mem, #NMAX) 
ftime(@t2) 

message.s = "QuickSort : "+Str(t2\milli-t1\milli)+"ms"+Chr(13)+Chr(10) 

; Time the internal SortArray() command 
ftime(@t1)
SortArray(array(), 0) 
ftime(@t2)


message + "SortArray : "+Str(t2\milli-t1\milli)+"ms"+Chr(13)+Chr(10) 
MessageRequester("Result", message, 0) 

FreeMemory(Mem) 

Code: Select all

//---------------------------------------------------------------------------
#include	<stdafx.h>
#include <stdlib.h>
#include <conio.h>
#include <stdio.h>
#include <sys\timeb.h>
#pragma hdrstop

#define gSz 500000

typedef struct {
	int len;
	int elem[gSz];
} vector;

void printv(char *str, vector* v)
{
	int i = 0;
	printf("%s", str);
	for (; i < v->len; ++i)
		printf("%d ", v->elem[i]);
	printf("\n");
}

#define MAX(a, b) ((a > b) ? (a) : (b))
#define MIN(a, b) ((a < b) ? (a) : (b))

int partition(vector *v, int p, int r)
{
	int x;
	int i;
	int j;

	if (p + 3 < r)
		x = MIN(v->elem[p], MAX(v->elem[p+1], v->elem[p+2]));
	else
		x = v->elem[p];

	i = p - 1;
	j = r + 1;
	while (1) {
		do {
			--j;
		} while (v->elem[j] > x);
		do {
			++i;
		} while (v->elem[i] < x);

		if (i < j) {
			int aux = v->elem[j];
			v->elem[j] = v->elem[i];
			v->elem[i] = aux;
		} else
			return j;
	}
}

void quicksort_real(vector *v, int p, int r) {
	if (p < r) {
		int q = partition(v, p, r);
		quicksort_real(v, p, q);
		quicksort_real(v, q + 1, r);
	}
}

void quicksort(vector *v) {
	printf("Quicksort...\n");
	quicksort_real(v, 0, v->len - 1);
}



int main(int argc, char* argv[])
{
	int i;
	int lDiv;
	vector lV;
	unsigned long lS;
	struct timeb t;


	lV.len = gSz;
	for ( i = 0; i < lV.len; ++i ) {
		lDiv = rand();
		lV.elem[i] = (int)(rand()/(lDiv==0?1:lDiv));
	}
	printf("Vector populated; Hit any key to quicksort...");
	getch();
	ftime(&t);
	lS = t.millitm;
	quicksort(&lV);
	ftime(&t);
	lS = t.millitm - lS;
	printf("Elapsed milliseconds: %ld", lS);


	return 0;
}
//---------------------------------------------------------------------------

Code: Select all

Procedure QuickSortLong(List.l(1), First.l, last.l)

    MedVal.l
    hi.l
    lo.l

    If First >= Last 
        ProcedureReturn
    EndIf
    
    MedVal = list(first)
    lo = first
    hi = last

    While 1
        While list(hi) >= medval
            hi = hi - 1
            If hi <= lo
                Break
            EndIf
        Wend

        If hi <= lo 
            list(lo) = medval
            Break
        EndIf

        list(lo) = list(hi) ;swap Vals

        lo = lo + 1

        While list(lo) < medval
            lo = lo + 1
            If lo >= hi
                Break 
            EndIf
        Wend

        If lo >= hi 
            lo = hi
            list (hi) = medVal
            Break
        EndIf

        list(hi) = list(lo) ;Swap Vals
    Wend

    QuickSortLong(list(), first, lo -1)
    QuickSortLong(list(), lo +1, last)

EndProcedure

;====================================

Dim Larray.l(20)

For i = 0 To 20 
  Larray(i) = Random($FFFF)
  Debug Larray(i) 
Next 

QuickSortLong(Larray(), 0,20) 

Debug "----------"

For i = 0 To 20 
  Debug Larray(i) 
Next

Code: Select all

Structure MemArray 
    Lng.l[0] 
EndStructure 

Procedure QuickSortLong(pList.l, First.l, last.l)

    If Last > first 
        
        MedVal.l
        hi.l
        lo.l
        *LstArray.MemArray = pList;@List()
    
        MedVal = *LstArray\lng[first]
        lo = first
        hi = last
    
        While 1
            While *LstArray\lng[hi] >= medval
                hi = hi - 1
                If hi <= lo
                    Break
                EndIf
            Wend
    
            If hi <= lo 
                *LstArray\lng[lo] = medval
                Break
            EndIf
    
            *LstArray\lng[lo] = *LstArray\lng[hi] ;swap Vals
    
            lo = lo + 1
    
            While *LstArray\lng[lo] < medval
                lo = lo + 1
                If lo >= hi
                    Break 
                EndIf
            Wend
    
            If lo >= hi 
                lo = hi
                *LstArray\lng[hi] = medVal
                Break
            EndIf
    
            *LstArray\lng[hi] = *LstArray\lng[lo] ;Swap Vals
        Wend
    
        QuickSortLong(pList, first, lo -1)
        QuickSortLong(pList, lo +1, last)
    
    EndIf
EndProcedure

#ArraySize = 5
Dim Larray.l(#ArraySize)
 *pLArray.MemArray = @Larray()

For i = 0 To #ArraySize 
  Larray(i) = Random($FF)
  Debug Larray(i) 
Next 

QuickSortLong(@Larray(), 0,#ArraySize) 

Debug "----Sorted------"

For i = 0 To #ArraySize 
  Debug Larray(i) 
 ;Debug "-" + Str(*pLArray\lng[i])
Next