# Quicksort

QuickSort

Works with PostgreSQL

8.4+

Written in

SQL

Depends on

Nothing

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.