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