TheGameCreators - CodeBase - Quicksort Natural Sort Order

Category: Functions

Version: 1.0

Information

Uploaded: 29th Jun 2023 15:09

Modified: 29th Jun 2023 15:09

Author: Ashingda 27

Summary

A method of using Quicksort to get a Natural sort order. Instead of getting "A10" sorted before "A5" you will get the correct sorting where the value of the numbers are taken into consideration.

Full Description

This is a simple and dirty way to achieve a Natural sort order. What is a Natural sort order? Normally when you sort with alphanumeric you will get incorrect ordering with numbers. Example: 1300 coming before 140 Thus to solve this issue this method will pars through the original string array and creates a duplicate array but this one has all the numbers transformed so that they all have a digit of 6 (may be higher if desired) with ZEROs before the value of the number. Example: "Dave6" = "Dave000006" "001Doc80" = "000001Doc000080" "Joe20Danny999" = "Joe000020Danny000999" We now use QuickSort to sort out this modified array however the original array also gets sorted alongside it.

DarkBASIC Professional Source Code

` This code was downloaded from The Game Creators

` It is reproduced here with full permission

` http://www.thegamecreators.com

remstart

//-------------------------------------------------

This is a simple and dirty way to achieve a Natural sort order.

What is a Natural sort order? Normally when you sort with

alphanumeric you will get incorrect ordering with numbers.

Example: 1300 coming before 140

Thus to solve this issue this method will pars through

the original string array and creates a duplicate array

but this one has all the numbers transformed so that they

all display ZEROs in front to the mas string length

of 6. (may be higher if desired)

Example:

"Dave6" = "Dave000006"

"001Doc80" = "000001Doc000080"

"Joe20Danny999" = "Joe000020Danny000999"

After creating this duplicate array with the modified

strings we will run it through QuickSort but the trick

is while we sort the modified array the original array

is sorted alongside it at the same index position.

//-------------------------------------------------

remend

sync on

sync rate 0

indexCount = 7

dim Name_Array$(indexCount)

dim Sort_Array$(indexCount)

//Manually set the strings

Name_Array$(0) = "A100"

Name_Array$(1) = "A10"

Name_Array$(2) = "A5"

Name_Array$(3) = "A1"

Name_Array$(4) = "A"

Name_Array$(5) = "0000A"

Name_Array$(6) = "A000"

Name_Array$(7) = "A1A"

Display_Array(0, 0, "Original Arrays", indexCount)

Modify_Sort_Array(indexCount)

QuickSort(0, indexCount)

Display_Array(300, 0, "Sorted Arrays", indexCount)

sync

loop

function Display_Array(x, y, s$, count)

text x, y, s$

inc y, 16

for i = 0 to count

text x, y + i * 16, Name_Array$(i)

text x + 100, y + i * 16, Sort_Array$(i)

next i

endfunction

function Modify_Sort_Array(count)

for i = 0 to count

length = len(Name_Array$(i))

number$ = ""

for m = 1 to length

//Get a single string from the Name_Array$ into s$

//Get the ASCII value of the single string s$

//Check if the single string is a number. Example: asc(1) = 49

//If the single string is a number then collect it into number$

s$ = mid$(Name_Array$(i),m)

a = asc(s$)

isNumber = (a >= 48 && a < 58)

if isNumber then number$ = number$ + s$

//Upon reaching the end of length OR the single string is NOT a number

//If the number$ string has anything stored in it

//Collect the number into Sort_Array$ but add ZEROs in front of it to the max total length of 6. Example: 610 = 000610

//Reset this string

if m = length || isNumber = 0

if number$ <> ""

Sort_Array$(i) = Sort_Array$(i) + right$("000000" + number$, 6)

number$ = ""

endif

//If the single string is NOT a number then collect into Sort_Array$ as normal

if isNumber = 0 then Sort_Array$(i) = Sort_Array$(i) + s$

next m

next i

endfunction

function QuickSort(L, R)

CheckL = L

CheckR = R

Pivot$ = Sort_Array$(R)

repeat

while Sort_Array$(CheckL) < Pivot$

inc CheckL

endwhile

while Pivot$ < Sort_Array$(CheckR)

dec CheckR

endwhile

if CheckL <= CheckR

//Swap the Sort_Array$

Swap$ = Sort_Array$(CheckL)

Sort_Array$(CheckL) = Sort_Array$(CheckR)

Sort_Array$(CheckR) = Swap$

//Also swap the Name_Array$ at the same position

Swap$ = Name_Array$(CheckL)

Name_Array$(CheckL) = Name_Array$(CheckR)

Name_Array$(CheckR) = Swap$

inc CheckL

dec CheckR

endif

until CheckL >= CheckR

if L < CheckR then QuickSort(L,CheckR)

if CheckL < R then QuickSort(CheckL,R)

endfunction

Download

Please login to download

Comments

No comments yet.

Author Name:	Ashingda 27
CodeBase Entries:	2

CodeBase - Quicksort Natural Sort Order

Information

Summary

Full Description

DarkBASIC Professional Source Code

Download

Screen Shot

Author

Comments