How to resolve the algorithm Sorting algorithms/Quicksort step by step in the 360 Assembly programming language
How to resolve the algorithm Sorting algorithms/Quicksort step by step in the 360 Assembly programming language
Table of Contents
Problem Statement
Sort an array (or list) elements using the quicksort algorithm. The elements must have a strict weak order and the index of the array can be of any discrete type. For languages where this is not possible, sort an array of integers.
Quicksort, also known as partition-exchange sort, uses these steps.
The best pivot creates partitions of equal length (or lengths differing by 1). The worst pivot creates an empty partition (for example, if the pivot is the first or last element of a sorted array). The run-time of Quicksort ranges from O(n log n) with the best pivots, to O(n2) with the worst pivots, where n is the number of elements in the array.
This is a simple quicksort algorithm, adapted from Wikipedia. A better quicksort algorithm works in place, by swapping elements within the array, to avoid the memory allocation of more arrays. Quicksort has a reputation as the fastest sort. Optimized variants of quicksort are common features of many languages and libraries. One often contrasts quicksort with merge sort, because both sorts have an average time of O(n log n). Quicksort is at one end of the spectrum of divide-and-conquer algorithms, with merge sort at the opposite end.
With quicksort, every element in the first partition is less than or equal to every element in the second partition. Therefore, the merge phase of quicksort is so trivial that it needs no mention! This task has not specified whether to allocate new arrays, or sort in place. This task also has not specified how to choose the pivot element. (Common ways to are to choose the first element, the middle element, or the median of three elements.) Thus there is a variety among the following implementations.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Sorting algorithms/Quicksort step by step in the 360 Assembly programming language
Source code in the 360 programming language
* Quicksort 14/09/2015 & 23/06/2016
QUICKSOR CSECT
USING QUICKSOR,R13 base register
B 72(R15) skip savearea
DC 17F'0' savearea
STM R14,R12,12(R13) prolog
ST R13,4(R15) "
ST R15,8(R13) "
LR R13,R15 "
MVC A,=A(1) a(1)=1
MVC B,=A(NN) b(1)=hbound(t)
L R6,=F'1' k=1
DO WHILE=(LTR,R6,NZ,R6) do while k<>0 ==================
LR R1,R6 k
SLA R1,2 ~
L R10,A-4(R1) l=a(k)
LR R1,R6 k
SLA R1,2 ~
L R11,B-4(R1) m=b(k)
BCTR R6,0 k=k-1
LR R4,R11 m
C R4,=F'2' if m<2
BL ITERATE then iterate
LR R2,R10 l
AR R2,R11 +m
BCTR R2,0 -1
ST R2,X x=l+m-1
LR R2,R11 m
SRA R2,1 m/2
AR R2,R10 +l
ST R2,Y y=l+m/2
L R1,X x
SLA R1,2 ~
L R4,T-4(R1) r4=t(x)
L R1,Y y
SLA R1,2 ~
L R5,T-4(R1) r5=t(y)
LR R1,R10 l
SLA R1,2 ~
L R3,T-4(R1) r3=t(l)
IF CR,R4,LT,R3 if t(x)
IF CR,R5,LT,R4 if t(y)
LR R7,R4 p=t(x) |
L R1,X x |
SLA R1,2 ~ |
ST R3,T-4(R1) t(x)=t(l) |
ELSEIF CR,R5,GT,R3 elseif t(y)>t(l) |
LR R7,R3 p=t(l) |
ELSE , else |
LR R7,R5 p=t(y) |
L R1,Y y |
SLA R1,2 ~ |
ST R3,T-4(R1) t(y)=t(l) |
ENDIF , end if |
ELSE , else |
IF CR,R5,LT,R3 if t(y)
LR R7,R3 p=t(l) |
ELSEIF CR,R5,GT,R4 elseif t(y)>t(x) |
LR R7,R4 p=t(x) |
L R1,X x |
SLA R1,2 ~ |
ST R3,T-4(R1) t(x)=t(l) |
ELSE , else |
LR R7,R5 p=t(y) |
L R1,Y y |
SLA R1,2 ~ |
ST R3,T-4(R1) t(y)=t(l) |
ENDIF , end if |
ENDIF , end if ---+
LA R8,1(R10) i=l+1
L R9,X j=x
FOREVER EQU * do forever --------------------+
LR R1,R8 i |
SLA R1,2 ~ |
LA R2,T-4(R1) @t(i) |
L R0,0(R2) t(i) |
DO WHILE=(CR,R8,LE,R9,AND, while i<=j and ---+ | X
CR,R0,LE,R7) t(i)<=p | |
AH R8,=H'1' i=i+1 | |
AH R2,=H'4' @t(i) | |
L R0,0(R2) t(i) | |
ENDDO , end while ---+ |
LR R1,R9 j |
SLA R1,2 ~ |
LA R2,T-4(R1) @t(j) |
L R0,0(R2) t(j) |
DO WHILE=(CR,R8,LT,R9,AND, while i
CR,R0,GE,R7) t(j)>=p | |
SH R9,=H'1' j=j-1 | |
SH R2,=H'4' @t(j) | |
L R0,0(R2) t(j) | |
ENDDO , end while ---+ |
CR R8,R9 if i>=j |
BNL LEAVE then leave (segment finished) |
LR R1,R8 i |
SLA R1,2 ~ |
LA R2,T-4(R1) @t(i) |
LR R1,R9 j |
SLA R1,2 ~ |
LA R3,T-4(R1) @t(j) |
L R0,0(R2) w=t(i) + |
MVC 0(4,R2),0(R3) t(i)=t(j) |swap t(i),t(j) |
ST R0,0(R3) t(j)=w + |
B FOREVER end do forever ----------------+
LEAVE EQU *
LR R9,R8 j=i
BCTR R9,0 j=i-1
LR R1,R9 j
SLA R1,2 ~
LA R3,T-4(R1) @t(j)
L R2,0(R3) t(j)
LR R1,R10 l
SLA R1,2 ~
ST R2,T-4(R1) t(l)=t(j)
ST R7,0(R3) t(j)=p
LA R6,1(R6) k=k+1
LR R1,R6 k
SLA R1,2 ~
LA R4,A-4(R1) r4=@a(k)
LA R5,B-4(R1) r5=@b(k)
IF C,R8,LE,Y if i<=y ----+
ST R8,0(R4) a(k)=i |
L R2,X x |
SR R2,R8 -i |
LA R2,1(R2) +1 |
ST R2,0(R5) b(k)=x-i+1 |
LA R6,1(R6) k=k+1 |
ST R10,4(R4) a(k)=l |
LR R2,R9 j |
SR R2,R10 -l |
ST R2,4(R5) b(k)=j-l |
ELSE , else |
ST R10,4(R4) a(k)=l |
LR R2,R9 j |
SR R2,R10 -l |
ST R2,0(R5) b(k)=j-l |
LA R6,1(R6) k=k+1 |
ST R8,4(R4) a(k)=i |
L R2,X x |
SR R2,R8 -i |
LA R2,1(R2) +1 |
ST R2,4(R5) b(k)=x-i+1 |
ENDIF , end if ----+
ITERATE EQU *
ENDDO , end while =====================
* *** ********* print sorted table
LA R3,PG ibuffer
LA R4,T @t(i)
DO WHILE=(C,R4,LE,=A(TEND)) do i=1 to hbound(t)
L R2,0(R4) t(i)
XDECO R2,XD edit t(i)
MVC 0(4,R3),XD+8 put in buffer
LA R3,4(R3) ibuffer=ibuffer+1
LA R4,4(R4) i=i+1
ENDDO , end do
XPRNT PG,80 print buffer
L R13,4(0,R13) epilog
LM R14,R12,12(R13) "
XR R15,R15 "
BR R14 exit
T DC F'10',F'9',F'9',F'6',F'7',F'16',F'1',F'16',F'17',F'15'
DC F'1',F'9',F'18',F'16',F'8',F'20',F'18',F'2',F'19',F'8'
TEND DS 0F
NN EQU (TEND-T)/4)
A DS (NN)F same size as T
B DS (NN)F same size as T
X DS F
Y DS F
PG DS CL80
XD DS CL12
YREGS
END QUICKSOR
You may also check:How to resolve the algorithm File modification time step by step in the Java programming language
You may also check:How to resolve the algorithm Sort stability step by step in the C# programming language
You may also check:How to resolve the algorithm Map range step by step in the Pascal programming language
You may also check:How to resolve the algorithm Inconsummate numbers in base 10 step by step in the Java programming language
You may also check:How to resolve the algorithm Empty program step by step in the EGL programming language