jeeswg's sort algorithms mini-tutorial

Put simple Tips and Tricks that are not entire Tutorials in this forum
User avatar
jeeswg
Posts: 6547
Joined: 19 Dec 2016, 01:58
Location: UK

jeeswg's sort algorithms mini-tutorial

11 May 2019, 11:04

This tutorial explains, and gives example code for, 6 algorithms:
selection sort
insertion sort
bubble sort
merge sort
quicksort (simple logic)
quicksort (in place)

All code examples use iterative approaches. No recursive approaches are used.

Explanations:

Code: Select all

==================================================

SORT ALGORITHMS MINI-TUTORIAL BY JEESWG

==================================================

> CONTENTS

> INTRO
> QUICKSORT (SIMPLE LOGIC)
> MERGE SORT
> BUBBLE SORT
> INSERTION SORT
> SELECTION SORT
> QUICKSORT (IN PLACE)

==================================================

> INTRO

Some sorting algorithms: quick, merge, bubble, insertion, selection.

==================================================

> QUICKSORT (SIMPLE LOGIC)

[note: see lower down, 'QUICKSORT (IN PLACE)']

pick the middle item to be the pivot
e.g. abcd, 2 or 3, Ceil(4/2) = 2
e.g. abcde, 3, Ceil(5/2) = 3
put smaller items before the pivot, and larger items after the pivot

where () indicates a pivot item
where [] indicates an item in the correct place

qwertyuiopas(d)fghjklzxcvbnm
acb[d]qwertyuiopsfghjklzxvnm

a(c)b[d]qwertyuiop(s)fghjklzxvnm
ab[c][d]qeriopfghjklnm[s]wtyuzxv

(a)b[c][d]qeriop(f)ghjklnm[s]wty(u)zxv
[a]b[c][d]e[f]qriopghjklnm[s]t[u]wyzxv

[a](b)[c][d](e)[f]qriop(g)hjklnm[s](t)[u]wy(z)xv
[a][b][c][d][e][f][g]qriophjklnm[s][t][u]wyxv[z]

[a][b][c][d][e][f][g]qriop(h)jklnm[s][t][u]w(y)xv[z]
[a][b][c][d][e][f][g][h]qriopjklnm[s][t][u]wxv[y][z]

[a][b][c][d][e][f][g][h]qrio(p)jklnm[s][t][u]w(x)v[y][z]
[a][b][c][d][e][f][g][h]iojklnm[p]qr[s][t][u]wv[x][y][z]

[a][b][c][d][e][f][g][h]ioj(k)lnm[p](q)r[s][t][u](w)v[x][y][z]
[a][b][c][d][e][f][g][h]ij[k]olnm[p][q]r[s][t][u]v[w][x][y][z]

[a][b][c][d][e][f][g][h](i)j[k]o(l)nm[p][q](r)[s][t][u][v][w][x][y][z]
[a][b][c][d][e][f][g][h][i]j[k][l]onm[p][q][r][s][t][u][v][w][x][y][z]

[a][b][c][d][e][f][g][h][i](j)[k][l]o(n)m[p][q][r][s][t][u][v][w][x][y][z]
[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]

[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]
[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]

==================================================

> MERGE SORT

note:
Merge sort - Wikipedia
https://en.wikipedia.org/wiki/Merge_sort
Merge sort's most common implementation does not sort in place

qwertyuiopasdfghjklzxcvbnm (split into pairs)
qw er ty ui op as df gh jk lz xc vb nm (sort each pair)
qw er ty iu op as df gh jk lz cx bv mn (merge)
eqrw ituy aops dfgh jklz bcvx mn (merge)
eiqrtuwy adfghops bcjklvxz mn (merge)
adefghiopqrstuwy bcjklmnvxz (merge)
abcdefghijklmnopqrstuvwxyz

MERGE SORT: MERGE

an example of a merge:
each of the two lists will be pre-sorted,
compare the first item in each list,
select the smaller item

where [] indicates an item in the correct place

 eqrw ituy
[e] qrw ituy
[e][i] qrw tuy
[e][i][q] rw tuy
[e][i][q][r] w tuy
[e][i][q][r][t] w uy
[e][i][q][r][t][u] w y
[e][i][q][r][t][u][w] y
[e][i][q][r][t][u][w][y]

==================================================

> BUBBLE SORT

sort 1st and 2nd items,
then sort 2nd and 3rd items,
... then sort second-to-last and last items

where [] indicates an item in the correct place

pass 1
eiadfghjcb (ei leave, ia swap)
eaidfghjcb (id swap)
eadifghjcb (if swap)
eadfighjcb (ig swap)
eadfgihjcb (ih swap)
eadfghijcb (ij leave, jc swap)
eadfghicjb (jb swap)
eadfghicb[j]

pass 2
eadfghicb[j] (ea swap)
aedfghicb[j] (ed swap)
adefghicb[j] (ef fg gh hi leave, ic swap)
adefghcib[j] (ib swap)
adefghcb[i][j]

pass 3
adefghcb[i][j] (ad de ef fg gh leave, hc swap)
adefgchb[i][j] (hb swap)
adefgcb[h][i][j]

pass 4
adefgcb[h][i][j] (ad de ef fg leave, gc swap)
adefcgb[h][i][j] (gb swap)
adefcb[g][h][i][j]

pass 5
adefcb[g][h][i][j] (ad de ef leave, fc swap)
adecfb[g][h][i][j] (fb swap)
adecb[f][g][h][i][j]

pass 6
adecb[f][g][h][i][j] (ad de leave, ec swap)
adceb[f][g][h][i][j] (eb swap)
adcb[e][f][g][h][i][j]

pass 7
adcb[e][f][g][h][i][j] (ad leave, dc swap)
acdb[e][f][g][h][i][j] (db swap)
acb[d][e][f][g][h][i][j]

pass 8
acb[d][e][f][g][h][i][j] (ac leave, cb swap)
ab[c][d][e][f][g][h][i][j]

pass 9
ab[c][d][e][f][g][h][i][j] (ab leave)
a[b][c][d][e][f][g][h][i][j]

pass 10
a[b][c][d][e][f][g][h][i][j]
[a][b][c][d][e][f][g][h][i][j]

==================================================

> INSERTION SORT

for i = 1 to n:
move item i into the correct place relative to the items before it

qwertyuiopasdfghjklzxcvbnm (leave q, leave w, move e)
eqwrtyuiopasdfghjklzxcvbnm (move r)
eqrwtyuiopasdfghjklzxcvbnm (move t)
eqrtwyuiopasdfghjklzxcvbnm (leave y, move u)
eqrtuwyiopasdfghjklzxcvbnm (move i)
eiqrtuwyopasdfghjklzxcvbnm (move o)
eioqrtuwypasdfghjklzxcvbnm (move p)
eiopqrtuwyasdfghjklzxcvbnm (move a)
aeiopqrtuwysdfghjklzxcvbnm (move s)
aeiopqrstuwydfghjklzxcvbnm (move d)
adeiopqrstuwyfghjklzxcvbnm (move f)
adefiopqrstuwyghjklzxcvbnm (move g)
adefgiopqrstuwyhjklzxcvbnm (move h)
adefghiopqrstuwyjklzxcvbnm (move j)
adefghijopqrstuwyklzxcvbnm (move k)
adefghijkopqrstuwylzxcvbnm (move l)
adefghijklopqrstuwyzxcvbnm (leave z, move x)
adefghijklopqrstuwxyzcvbnm (move c)
acdefghijklopqrstuwxyzvbnm (move v)
acdefghijklopqrstuvwxyzbnm (move b)
abcdefghijklopqrstuvwxyznm (move n)
abcdefghijklnopqrstuvwxyzm (move m)
abcdefghijklmnopqrstuvwxyz

==================================================

> SELECTION SORT

move the smallest item in the unsorted list
to the sorted list

 qwertyuiopasdfghjklzxcvbnm
a qwertyuiopsdfghjklzxcvbnm
ab qwertyuiopsdfghjklzxcvnm
abc qwertyuiopsdfghjklzxvnm
abcd qwertyuiopsfghjklzxvnm
abcde qwrtyuiopsfghjklzxvnm
abcdef qwrtyuiopsghjklzxvnm
abcdefg qwrtyuiopshjklzxvnm
abcdefgh qwrtyuiopsjklzxvnm
abcdefghi qwrtyuopsjklzxvnm
abcdefghij qwrtyuopsklzxvnm
abcdefghijk qwrtyuopslzxvnm
abcdefghijkl qwrtyuopszxvnm
abcdefghijklm qwrtyuopszxvn
abcdefghijklmn qwrtyuopszxv
abcdefghijklmno qwrtyupszxv
abcdefghijklmnop qwrtyuszxv
abcdefghijklmnopq wrtyuszxv
abcdefghijklmnopqr wtyuszxv
abcdefghijklmnopqrs wtyuzxv
abcdefghijklmnopqrst wyuzxv
abcdefghijklmnopqrstu wyzxv
abcdefghijklmnopqrstuv wyzx
abcdefghijklmnopqrstuvw yzx
abcdefghijklmnopqrstuvwx yz
abcdefghijklmnopqrstuvwxy z
abcdefghijklmnopqrstuvwxyz

==================================================

> QUICKSORT (IN PLACE)

an in place sort, sorts items, without needing external storage space

pick the middle item to be the pivot
e.g. abcd, 2 or 3, Ceil(4/2) = 2
e.g. abcde, 3, Ceil(5/2) = 3

==============================

the approach:

after each pass, various items are confirmed as being in the correct place,
leaving smaller and smaller unsorted sublists

for each unsorted sublist:
{
swap the pivot item and the rightmost item

place pointer L to the left of the leftmost item:
place pointer R at the rightmost item (the pivot item):

loop
{
move pointer L right until you find an item greater than (or equal to) the pivot
move pointer R left until you find an item less than the pivot
if pointers L and R are adjacent, in the order 'RL', break out of the loop
otherwise, swap the items at pointers L and R
}

swap the pivot item and the item at pointer L
(note: sometimes the pivot item, and the item at pointer L, are the same item)

the pivot item is now in the correct place

note: if there is only one item in the sublist, it is in the correct place
}

when all items are marked as in the correct place, the sort is complete
}

==============================

in the example below:
an item known to be in the correct place, is capitalised
P: pivot
E: end element (rightmost element)
L: pointer L
R: pointer R
*: only 1 item in the sublist, therefore it's in the correct place

==============================

qwertyuiopasdfghjklzxcvbnm

==============================

pass 1

qwertyuiopasdfghjklzxcvbnm
            P            E
qwertyuiopasmfghjklzxcvbnd
L                      R
bwertyuiopasmfghjklzxcvqnd
 L                   R
bcertyuiopasmfghjklzxwvqnd
  L       R
bcartyuiopesmfghjklzxwvqnd
  RL                     P
bcaDtyuiopesmfghjklzxwvqnr

==============================

pass 2

bcaDtyuiopesmfghjklzxwvqnr
 PE
bacDtyuiopesmfghjklzxwvqnr
 RL                      P
baCDtyuiopesmfghjklzxwvqnr

=====

baCDtyuiopesmfghjklzxwvqnr
              P          E
baCDtyuiopesmfrhjklzxwvqng
    L        R
baCDfyuiopesmtrhjklzxwvqng
     L    R
baCDfeuiopysmtrhjklzxwvqng
     RL                  P
baCDfeGiopysmtrhjklzxwvqnu

==============================

pass 3

baCDfeGiopysmtrhjklzxwvqnu
PE
abCDfeGiopysmtrhjklzxwvqnu
RL
 P
aBCDfeGiopysmtrhjklzxwvqnu

=====

aBCDfeGiopysmtrhjklzxwvqnu
    PE
aBCDefGiopysmtrhjklzxwvqnu
    RL
     P
aBCDeFGiopysmtrhjklzxwvqnu

=====

aBCDeFGiopysmtrhjklzxwvqnu
                P        E
aBCDeFGiopysmtrhuklzxwvqnj
        L      R
aBCDeFGihpysmtrouklzxwvqnj
        RL               P
aBCDeFGihJysmtrouklzxwvqnp

==============================

pass 4

aBCDeFGihJysmtrouklzxwvqnp
*
ABCDeFGihJysmtrouklzxwvqnp

=====

ABCDeFGihJysmtrouklzxwvqnp
    *
ABCDEFGihJysmtrouklzxwvqnp

=====

ABCDEFGihJysmtrouklzxwvqnp
       PE
ABCDEFGhiJysmtrouklzxwvqnp
       RL
        P
ABCDEFGhIJysmtrouklzxwvqnp

=====

ABCDEFGhIJysmtrouklzxwvqnp
                 P       E
ABCDEFGhIJysmtrouplzxwvqnk
         RL              P
ABCDEFGhIJKsmtrouplzxwvqny

==============================

pass 5

ABCDEFGhIJKsmtrouplzxwvqny
       *
ABCDEFGHIJKsmtrouplzxwvqny

=====

ABCDEFGHIJKsmtrouplzxwvqny
                  P      E
ABCDEFGHIJKsmtroupyzxwvqnl
          RL             P
ABCDEFGHIJKLmtroupyzxwvqns

==============================

pass 6

ABCDEFGHIJKLmtroupyzxwvqns
                  P      E
ABCDEFGHIJKLmtroupszxwvqny
                   L    R
ABCDEFGHIJKLmtroupsnxwvqzy
                       RLP
ABCDEFGHIJKLmtroupsnxwvqYz

==============================

pass 7

ABCDEFGHIJKLmtroupsnxwvqYz
                 P     E
ABCDEFGHIJKLmtrouqsnxwvpYz
             L     R
ABCDEFGHIJKLmnrouqstxwvpYz
              LR
ABCDEFGHIJKLmnoruqstxwvpYz
              RL       P
ABCDEFGHIJKLmnoPuqstxwvrYz

=====

ABCDEFGHIJKLmnoPuqstxwvrYz
                         *
ABCDEFGHIJKLmnoPuqstxwvrYZ

==============================

pass 8

ABCDEFGHIJKLmnoPuqstxwvrYZ
             PE
ABCDEFGHIJKLmonPuqstxwvrYZ
            RLP
ABCDEFGHIJKLmNoPuqstxwvrYZ

=====

ABCDEFGHIJKLmNoPuqstxwvrYZ
                   P   E
ABCDEFGHIJKLmNoPuqsrxwvtYZ
                L  R
ABCDEFGHIJKLmNoPrqsuxwvtYZ
                  RL   P
ABCDEFGHIJKLmNoPrqsTxwvuYZ

==============================

pass 9

ABCDEFGHIJKLmNoPrqsTxwvuYZ
            *
ABCDEFGHIJKLMNoPrqsTxwvuYZ

=====

ABCDEFGHIJKLMNoPrqsTxwvuYZ
              *
ABCDEFGHIJKLMNOPrqsTxwvuYZ

ABCDEFGHIJKLMNOPrqsTxwvuYZ
                 PE
ABCDEFGHIJKLMNOPrsqTxwvuYZ
               RL P
ABCDEFGHIJKLMNOPQsrTxwvuYZ

=====

ABCDEFGHIJKLMNOPQsrTxwvuYZ
                     P E
ABCDEFGHIJKLMNOPQsrTxuvwYZ
                    L R
ABCDEFGHIJKLMNOPQsrTvuxwYZ
                     RLP
ABCDEFGHIJKLMNOPQsrTvuWxYZ

==============================

pass 10

ABCDEFGHIJKLMNOPQsrTvuWxYZ
                 PE
ABCDEFGHIJKLMNOPQrsTvuWxYZ
                 RL
                  P
ABCDEFGHIJKLMNOPQrSTvuWxYZ

=====

ABCDEFGHIJKLMNOPQrSTvuWxYZ
                    PE
ABCDEFGHIJKLMNOPQrSTuvWxYZ
                    RL
                     P
ABCDEFGHIJKLMNOPQrSTuVWxYZ

=====

ABCDEFGHIJKLMNOPQrSTuVWxYZ
                       *
ABCDEFGHIJKLMNOPQrSTuVWXYZ

==============================

pass 11

ABCDEFGHIJKLMNOPQrSTuVWXYZ
                 *
ABCDEFGHIJKLMNOPQRSTuVWXYZ

ABCDEFGHIJKLMNOPQRSTuVWXYZ
                    *
ABCDEFGHIJKLMNOPQRSTUVWXYZ

==================================================

summary:

qwertyuiopasdfghjklzxcvbnm
bcaDtyuiopesmfghjklzxwvqnr
baCDfeGiopysmtrhjklzxwvqnu
aBCDeFGihJysmtrouklzxwvqnp
ABCDEFGhIJKsmtrouplzxwvqny
ABCDEFGHIJKLmtroupyzxwvqns
ABCDEFGHIJKLmtroupsnxwvqYz
ABCDEFGHIJKLmnoPuqstxwvrYZ
ABCDEFGHIJKLmNoPrqsTxwvuYZ
ABCDEFGHIJKLMNOPQsrTvuWxYZ
ABCDEFGHIJKLMNOPQrSTuVWXYZ
ABCDEFGHIJKLMNOPQRSTUVWXYZ

==================================================

Code examples:

Code: Select all

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

;sort examples

;selection sort
;insertion sort
;bubble sort
;merge sort
;quicksort (simple logic)
;quicksort (in place)

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

return

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

;q:: ;selection sort
oArray := StrSplit("qwertyuiopasdfghjklzxcvbnm")
oArray2 := []
vOutput := JEE_StrJoin("", oArray2*) " " JEE_StrJoin("", oArray*) "`r`n"
while oArray.Length()
{
	vMin := 1
	Loop, % oArray.Length()
	{
		if (oArray[A_Index] < oArray[vMin])
			vMin := A_Index
	}
	oArray2.Push(oArray[vMin])
	oArray.RemoveAt(vMin)
	vOutput .= JEE_StrJoin("", oArray2*) " " JEE_StrJoin("", oArray*) "`r`n"
}
Clipboard := vOutput
MsgBox, % vOutput
return

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

;q:: ;insertion sort
oArray := StrSplit("qwertyuiopasdfghjklzxcvbnm")
vOutput := JEE_StrJoin("", oArray*) "`r`n"
Loop, % oArray.Length()
{
	vIndex := A_Index
	Loop, % vIndex - 1
	{
		if (oArray[vIndex] < oArray[A_Index])
		{
			vTemp := oArray.RemoveAt(vIndex)
			oArray.InsertAt(A_Index, vTemp)
		}
	}
	vOutput .= JEE_StrJoin("", oArray*) "`r`n"
}
Clipboard := vOutput
MsgBox, % vOutput
return

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

;q:: ;bubble sort
oArray := StrSplit("qwertyuiopasdfghjklzxcvbnm")
oArray := StrSplit("eiadfghjcb") ;first 10 letters
vOutput := ""
vNum := oArray.Length()
Loop, % oArray.Length()
{
	vNum--
	vOutput .= "pass " A_Index "`r`n"
	vOutput .= JEE_StrJoin("", oArray*) "`r`n"
	Loop, % vNum
	{
		if (oArray[A_Index] > oArray[A_Index+1])
		{
			vTemp := oArray[A_Index]
			oArray[A_Index] := oArray[A_Index+1]
			oArray[A_Index+1] := vTemp
			vOutput .= JEE_StrJoin("", oArray*) "`r`n"
		}
	}
	vOutput .= "`r`n"
}
vOutput := RTrim(vOutput, "`r`n") "`r`n"
Clipboard := vOutput
MsgBox, % vOutput
return

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

;note:
;Merge sort - Wikipedia
;https://en.wikipedia.org/wiki/Merge_sort
;Merge sort's most common implementation does not sort in place

;q:: ;merge sort
oArray := StrSplit("qwertyuiopasdfghjklzxcvbnm")

vOutput := JEE_StrJoin("", oArray*) "`r`n"
vTemp := ""
for vKey, vValue in oArray
	vTemp .= vValue (Mod(vKey, 2) ? "" : " ")
vOutput .= RTrim(vTemp) "`r`n"

Loop, % oArray.Length() // 2
{
	vIndex := A_Index*2 - 1
	if (oArray[vIndex] > oArray[vIndex+1])
	{
		vTemp := oArray[vIndex]
		oArray[vIndex] := oArray[vIndex+1]
		oArray[vIndex+1] := vTemp
	}
}

vTemp := ""
for vKey, vValue in oArray
	vTemp .= vValue (Mod(vKey, 2) ? "" : " ")
vOutput .= RTrim(vTemp) "`r`n"
;vOutput .= JEE_StrJoin("", oArray*) "`r`n"

;.......................... (slice)
;.. .. .. .. .. .. .. .. .. .. .. .. .. (sort each pair)
;[.. ..][.. ..][.. ..][.. ..][.. ..][.. ..][..] (merge)
;[.... ....][.... ....][.... ....][..] (merge)
;[........ ........][........ ..] (merge)
;[................ ..........] (merge)
;..........................

vNum := 2
vCount := oArray.Length()
Loop
{
	vNum <<= 1
	oTemp := oArray
	oArray := []
	Loop, % Ceil(vCount / vNum)
	{
		vPos1 := vNum*(A_Index-1) + 1
		vPos2 := vPos1 + (vNum // 2)
		vCount1 := vNum // 2
		vCount2 := vNum // 2
		if !oTemp.HasKey(vPos2)
			vCount2 := 0
		Loop, % vNum
		{
			if !vCount2
			|| (vCount1 && (oTemp[vPos1] <= oTemp[vPos2]))
			{
				oArray.Push(oTemp[vPos1])
				vPos1++, vCount1--
				if !oTemp.HasKey(vPos1)
					vCount1 := 0
			}
			else if !vCount1
			|| (vCount2 && (oTemp[vPos1] > oTemp[vPos2]))
			{
				oArray.Push(oTemp[vPos2])
				vPos2++, vCount2--
				if !oTemp.HasKey(vPos2)
					vCount2 := 0
			}
			if !vCount1 && !vCount2
				break
		}
	}

	vTemp := ""
	for vKey, vValue in oArray
		vTemp .= vValue (Mod(vKey, vNum) ? "" : " ")
	vOutput .= RTrim(vTemp) "`r`n"
	;vOutput .= JEE_StrJoin("", oArray*) "`r`n"
	if (vNum >= vCount)
		break
}
oTemp := ""
Clipboard := vOutput
MsgBox, % vOutput
return

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

;q:: ;quicksort (simple logic)
oArray := StrSplit("qwertyuiopasdfghjklzxcvbnm")
oDone := []
Loop, % oArray.Length()
	oDone.Push(0)
oDone.Push(1)

vLen := oArray.Length()
vOutput := ""
for _, vValue in oArray
	vOutput .= vValue
vOutput .= "`r`n"
Loop, % vLen
{
	vPos1 := vPos2 := vIsMatch := 0
	Loop, % vLen+1
	{
		if (A_Index = vLen+1)
		{
			if !vIsMatch
				break 2
			else
				break
		}
		if !vPos1 && !oDone[A_Index]
			vPos1 := A_Index, vIsMatch := 1
		if vPos1 && oDone[A_Index+1]
		&& (vPos1 = A_Index)
		{
			oDone[A_Index] := 1
			vPos1 := vPos2 := 0
		}
		else if vPos1 && oDone[A_Index+1]
		{
			vPos2 := A_Index
			vPosPivot := Floor((vPos1+vPos2)/2)
			vPivot := oArray[vPosPivot]
			oTemp1 := [], oTemp2 := [], vPos := vPos1
			Loop, % vPos2 - vPos1 + 1
			{
				if (vPos = vPosPivot)
					Sleep, 0 ;NoOp()
				else if (oArray[vPos] < vPivot)
					oTemp1.Push(oArray[vPos])
				else
					oTemp2.Push(oArray[vPos])
				vPos++
			}
			vPos := vPos1
			for _, vValue in oTemp1
				oArray[vPos] := vValue, vPos++
			oDone[vPos] := 1
			oArray[vPos] := vPivot, vPos++
			for _, vValue in oTemp2
				oArray[vPos] := vValue, vPos++
			vPos1 := vPos2 := 0
		}
	}
	for _, vValue in oArray
		vOutput .= oDone[A_Index] ? Format("{:U}", vValue) : vValue
	vOutput .= "`r`n"
}
Clipboard := vOutput
MsgBox, % "done"
return

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

;count the number of items to sort
;create a 'completed' array with that many items
;each time an item is confirmed as being in the correct place,
;mark the appropriate item in the 'completed' array as true

;q:: ;quicksort (in place)
oArray := StrSplit("qwertyuiopasdfghjklzxcvbnm")
oDone := []
Loop, % oArray.Length()
	oDone.Push(0)
oDone.Push(1)

vLen := oArray.Length()
vOutput := ""
for _, vValue in oArray
	vOutput .= vValue
vOutput .= "`r`n"
Loop, % vLen
{
	vPos1 := vPos2 := vIsMatch := 0
	Loop, % vLen+1
	{
		if (A_Index = vLen+1)
		{
			if !vIsMatch
				break 2
			else
				break
		}
		if !vPos1 && !oDone[A_Index]
			vPos1 := A_Index, vIsMatch := 1
		if vPos1 && oDone[A_Index+1]
		&& (vPos1 = A_Index)
		{
			oDone[A_Index] := 1
			vPos1 := vPos2 := 0
		}
		else if vPos1 && oDone[A_Index+1]
		{
			vPos2 := A_Index
			vPosPivot := Floor((vPos1+vPos2)/2)
			vPivot := oArray[vPosPivot]
			JEE_ObjSwapKeys(oArray, vPosPivot, vPos2)
			vPosL := vPos1, vPosR := vPos2-1
			Loop
			{
				while (oArray[vPosL] < vPivot)
					vPosL++
				while (oArray[vPosR] >= vPivot)
					vPosR--
				if (vPosL > vPosR)
					break
				JEE_ObjSwapKeys(oArray, vPosL, vPosR)
				vPosL++, vPosR--
			}
			JEE_ObjSwapKeys(oArray, vPos2, vPosL)
			oDone[vPosL] := 1
			vPos1 := vPos2 := 0
		}
	}
	for _, vValue in oArray
		vOutput .= oDone[A_Index] ? Format("{:U}", vValue) : vValue
	vOutput .= "`r`n"
}
Clipboard := vOutput
MsgBox, % "done"
return

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

; ;e.g.
; oArray := StrSplit("abcdefghijklmnopqrstuvwxyz")
; MsgBox, % JEE_StrJoin(" - ", oArray*)
; MsgBox, % JEE_StrJoin(["=", "`r`n"], oArray*)
; MsgBox, % JEE_StrJoin(["`t", "`r`n"], oArray*)
; MsgBox, % JEE_StrJoin(["`t", "`t", "`r`n"],  oArray*)
; MsgBox, % JEE_StrJoin(["`t", "`t", "`t", "`r`n"],  oArray*)
; MsgBox, % JEE_StrJoin(["`t", "`t", "`t", "`t", "`r`n"],  oArray*)
; MsgBox, % JEE_StrJoin(["", "", "", "", "`r`n"],  oArray*)

JEE_StrJoin(vSep, oArray*)
{
	local
	VarSetCapacity(vOutput, oArray.Length()*200*2)
	if IsObject(vSep) && (vSep.Length() = 1) ;convert 1-item array to string
		vSep := vSep.1
	if !IsObject(vSep)
	{
		Loop, % oArray.MaxIndex()-1
			vOutput .= oArray[A_Index] vSep
		vOutput .= oArray[oArray.MaxIndex()]
	}
	else
	{
		oSep := vSep, vCount := oSep.Length(), vIndex := 0
		Loop, % oArray.MaxIndex()-1
		{
			;vIndex := Mod(A_Index-1, vCount)+1
			vIndex := (vIndex = vCount) ? 1 : vIndex+1
			, vOutput .= oArray[A_Index] oSep[vIndex]
		}
		vOutput .= oArray[oArray.MaxIndex()]
	}
	return vOutput
}

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

JEE_ObjSwapKeys(oArray, vKey1, vKey2)
{
	local
	if (vKey1 = vKey2)
		return
	vTemp := oArray[vKey1]
	oArray[vKey1] := oArray[vKey2]
	oArray[vKey2] := vTemp
}

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

Links:

[quicksort in place]
Quick sort in 4 minutes - YouTube
https://www.youtube.com/watch?v=Hoixgm4-P4M
Quick Sort | GeeksforGeeks - YouTube
https://www.youtube.com/watch?v=PgBzjlCcFvc

Sorting algorithm - Wikipedia
https://en.wikipedia.org/wiki/Sorting_algorithm

computer science resources - AutoHotkey Community
https://autohotkey.com/boards/viewtopic.php?f=17&t=60677

[bonus videos]
Lego Bubble Sort - YouTube
https://www.youtube.com/watch?v=MtcrEhrt_K0
15 Sorting Algorithms in 6 Minutes - YouTube
https://www.youtube.com/watch?v=kPRA0W1kECg
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA

Return to “Tips and Tricks”

Who is online

Users browsing this forum: No registered users and 3 guests