with Text_io;
procedure QUICKSORTDEMO is --{by RJBotting, after Kruse 257 & 259}
 
    max_index:constant:=80;
 
    subtype ITEM is character;
    subtype INDEX is integer range 1..max_index;
    type LIST is array (INDEX) of ITEM;
 
    type SUBLIST is array(INDEX range <>) of ITEM;
		--Quick Sort works by extracting sublists and sorting them
 
    L:LIST:=(1..max_index=>ASCII.DEL);
    SIZE:INDEX;
 
    swap_count:integer:=0;
 
    procedure GET_LIST(L:out LIST; size:out index) is
    begin
        for I in INDEX loop
            Text_io.get(L(I));
	    if text_io.end_of_line then
		size:=I;
		return;
	    end if;
        end loop;
    end GET_LIST;
 
    procedure WRITELIST(L:in SUBLIST) is
    begin
        for I in L'range loop
            Text_io.Put(L(I));
        end loop;
    end WRITELIST;
 
    procedure SWAP(X,Y:INDEX; L:in out SUBLIST) is
        T:ITEM:=L(X);
    begin
	swap_count:=swap_count+1;
        L(X):=L(Y); L(Y):=T;
    end SWAP;
 
    procedure SORT2(L:in out SUBLIST) is
		-- sorts the first and last elements of L
    begin
        if L(L'first)>L(L'last)  then
            SWAP(L'first, L'last, L);
        end if;
    end SORT2;
 
    procedure SORT3(L:in out SUBLIST; MID:in INDEX) is
			--sorts the first, middle and last elements of L
    begin
        SORT2(L(L'first..MID));
        SORT2(L(MID..L'last));
        SORT2(L(L'first..MID));
    end SORT3;
 
    procedure PARTITION(L:in out SUBLIST;  PIVOTLOC:out INDEX) is
        MIDDLE:INDEX:=(l'first+l'last)/2;
    begin
	 -- text_io.put_line(integer'image(middle));
        SORT3(L, MIDDLE);
			-- L(first)<=L(Middle)<=L(last)
        PIVOTING: declare
            PIVOTVAL:ITEM := L(Middle);
            LASTSMALL:INDEX:=L'first;
        begin
	    SWAP(MIDDLE, L'LAST-1, L); 
            for I in L'first+1 .. L'last-2 loop
                -- L(first..lastsmall) are   all <= pivot
                -- and L(lastsmall+1..i-1) are all >= pivot
                if L(I)<PIVOTVAL then
                    LASTSMALL:=INDEX'succ(LASTSMALL);
                    SWAP(LASTSMALL, I, L);
                end if;
            end loop;
	    SWAP(LASTSMALL+1, L'LAST-1, L); 
	    PIVOTLOC:=LASTSMALL+1;
        end PIVOTING;
 
        --L(first..pivotloc)<=L(pivotloc)<=L(pivotloc..last)
    end;
 
    procedure SORT( L:in out SUBLIST) is
    begin
	writelist(L); text_io.new_line;
        case L'length is
	when 0|1=> null;
	when 2=> SORT2(L);
        when 3=> SORT3(L, L'first+1);
        when others=> 
            PARTITION_L: declare PIVOT_LOC:INDEX;
            begin
                PARTITION(L, PIVOT_LOC);
                SORT( L(L'first..PIVOT_LOC-1) );
                SORT( L(PIVOT_LOC+1..L'last )   );
            end PARTITION_L;
        end case;
	writelist(L); text_io.new_line;
    end;
 
begin--{quickSort(L)}
    Text_io.Put("Input upto ");
    Text_io.Put(integer'image(MAX_INDEX));
    Text_io.Put_line(" characters and tap Enter...");
    Get_list(L, size);
    declare
	S:SUBLIST(1..SIZE):=SUBLIST(L(1..SIZE));
    begin
    	WRITELIST(S);
	text_io.new_line;
 
    	SORT(S);
 
    	WRITELIST(S);
	text_io.new_line;
	text_io.put(integer'image(swap_count));
	text_io.new_line;
   end;
end;