Quicksort
A pure SQL implementation of QuickSort Algorithm using Recursive CTE expressions, by N. Can KIRIK ( can(at)epati.com.tr )
PS. This implementation, which is heavily resource-hungry, is education purposes only. Don't use this implementation on production environment, instead use "sort" function of "intarray" contrib package.
A status stack used to simulate a function call stack. This can't be done without a stack due to difference in nature of recursive functionality of CTE expressions.
A custom composite type that uses a custom enum type (direction) to track status ( call stack data type ):
CREATE TYPE "enum_quickSort_direction" AS ENUM ('up', 'down', 'left', 'right');
CREATE TYPE "t_quickSort_status" AS ("direction" "enum_quickSort_direction", "left" int4, "pivot" int4, "right" int4);
This shorthand function used to swap elements in an array.
CREATE OR REPLACE FUNCTION "fn_quickSort_swap"( "myArray" _int4, "old" int4, "new" int4) RETURNS _int4 AS $BODY$
SELECT
CASE
WHEN $2 = $3 THEN
$1
ELSE
CASE
WHEN ARRAY_LOWER( $1, 1 ) <= LEAST( $2, $3 ) - 1 THEN
$1[ ARRAY_LOWER( $1, 1 ) : LEAST( $2, $3 ) - 1 ] || $1[ GREATEST( $2, $3 ) ]
ELSE
ARRAY[ $1[ GREATEST( $2, $3 ) ] ]
END
||
CASE
WHEN $2 != $3 THEN
$1[ LEAST( $2, $3 ) + 1 : GREATEST( $2, $3 ) - 1 ] || $1[ LEAST( $2, $3 ) ]
ELSE
ARRAY[ $1[ LEAST( $2, $3 ) ] ]
END
||
$1[ GREATEST( $2, $3 ) + 1 : ARRAY_UPPER( $1, 1 ) ]
END
;
$BODY$ LANGUAGE 'sql' IMMUTABLE;
The Partition function, core functionality of QuickSort algorithm, is implemented using recursive CTE's "t_quickSort_partitionResult" custom composite type used to able to return two different values, which are pivot index and partitioned array.
CREATE TYPE "public"."t_quickSort_partitionResult" AS ( "pivot" int4, "myArray" int4[] );
CREATE OR REPLACE FUNCTION "public"."fn_quickSort_partition"( "myArray" _int4, "left" int4, "right" int4 ) RETURNS "t_quickSort_partitionResult" AS $BODY$
WITH RECURSIVE
"partition" AS (
SELECT
$2 AS i
,$2 AS "index"
,"fn_quickSort_swap"( $1, ( $2 + $3 ) / 2, $3 ) AS "a"
WHERE
$2 < $3
UNION ALL
SELECT
i + 1
,"index" + ( "a"[ i ] <= "a"[ $3 ] )::INT
,CASE WHEN "a"[ i ] <= "a"[ $3 ] AND i != "index" THEN "fn_quickSort_swap"( "a", i, "index" ) ELSE "a" END
FROM
"partition"
WHERE
i < $3
)
SELECT
ROW(
"index"
,"fn_quickSort_swap"( "a", "index", $3 )
)::"t_quickSort_partitionResult"
FROM
"partition"
WHERE
i = $3
;
$BODY$ LANGUAGE 'sql' IMMUTABLE;
Main function, QuickSort, which also implemented using recursive CTE's
CREATE OR REPLACE FUNCTION "fn_quickSort"( _int4 ) RETURNS _int4 AS $BODY$
WITH RECURSIVE
"sort" AS (
SELECT
$1 AS "myArray"
,ARRAY[ ROW( 'down', ARRAY_LOWER( $1, 1 ), NULL, ARRAY_UPPER( $1, 1 ) )::"t_quickSort_status" ] AS "status"
UNION ALL
SELECT
"myArray"
,CASE
WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'down' THEN "status"[ 1 : "idx_active" - 2 ]
WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'right' THEN "status"[ 1 : "idx_active" - 2 ] || ROW( 'up', 0, 0, 0 )::"t_quickSort_status"
WHEN ( "active" )."direction" = 'up' AND ( "previous" )."direction" = 'left' THEN "status"[ 1 : "idx_active" - 2 ] || ROW( 'right', ( "previous" )."left", ( "previous" )."pivot", ( "previous" )."right" )::"t_quickSort_status"
WHEN "left" < "right" THEN "status" || ROW( 'left', "left", "pivot", "right" )::"t_quickSort_status"
WHEN ( "active" )."direction" = 'right' THEN "status"[ 1 : "idx_active" - 1 ] || ROW( 'up', 0, 0, 0 )::"t_quickSort_status"
WHEN ( "active" )."direction" = 'left' THEN "status"[ 1 : "idx_active" - 1 ] || ROW( 'right', ( "active" )."left", ( "active" )."pivot", ( "active" )."right" )::"t_quickSort_status"
END
FROM
(
SELECT
( COALESCE(
"fn_quickSort_partition"( "myArray", "left", "right" )
,ROW( ( "active" )."pivot", "myArray" )::"t_quickSort_partitionResult"
) ).*
,"left"
,"right"
,"status"
,"idx_active"
,"active"
,"previous"
FROM
(
SELECT
"myArray"
,CASE ( "active" )."direction"
WHEN 'up' THEN 0
WHEN 'down' THEN ( "active" )."left"
WHEN 'left' THEN ( "active" )."left"
WHEN 'right' THEN ( "active" )."pivot" + 1
END AS "left"
,CASE ( "active" )."direction"
WHEN 'up' THEN 0
WHEN 'down' THEN ( "active" )."right"
WHEN 'left' THEN ( "active" )."pivot" - 1
WHEN 'right' THEN ( "active" )."right"
END AS "right"
,"status"
,"idx_active"
,"active"
,"previous"
FROM
(
SELECT
*
,ARRAY_LENGTH( "status", 1 ) AS "idx_active"
,"status"[ ARRAY_LENGTH( "status", 1 ) ] AS "active"
,"status"[ ARRAY_LENGTH( "status", 1 ) - 1 ] AS "previous"
FROM
"sort"
WHERE
ARRAY_LENGTH( "status", 1 ) > 0
) s
) s
) s
)
SELECT
"myArray"
FROM
"sort"
WHERE
"status"[ 1 ] IS NULL
LIMIT 1;
$BODY$ LANGUAGE 'sql' IMMUTABLE;
PS. This implementation, which is heavily resource-hungry, is education purposes only. Don't use this implementation on production environment, instead use "sort" function of "intarray" contrib package.
