Quicksort

From PostgreSQL wiki

(Difference between revisions)
Jump to: navigation, search
 
Line 2: Line 2:
  
 
A pure SQL implementation of QuickSort Algorithm using Recursive CTE expressions, ''by N. Can KIRIK ( can(at)epati.com.tr )''
 
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.
  
  
 
----
 
----
  
We're using a status stack 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 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 ):
 
A custom composite type that uses a custom enum type (direction) to track status ( call stack data type ):
Line 19: Line 23:
 
----
 
----
  
To swap elements in an array, we're using this shorthand function.
+
This shorthand function used to swap elements in an array.
  
 
<source lang="SQL">
 
<source lang="SQL">
Line 53: Line 57:
 
----
 
----
  
Next, the core functionality of QuickSort algorithm, partition function which is implemented using recursive CTE's
+
The Partition function, core functionality of QuickSort algorithm, is implemented using recursive CTE's
We're also using a custom composite type to return 2 values. first is pivot index, second is the partitioned array.
+
"t_quickSort_partitionResult" custom composite type used to able to return two different values, which are pivot index and partitioned array.
  
 
<source lang="SQL">
 
<source lang="SQL">
Line 79: Line 83:
 
             i < $3
 
             i < $3
 
     )
 
     )
SELECT "result" FROM (
+
SELECT
     SELECT LAST( ROW( "index", "fn_quickSort_swap"( "a", "index", $3 ) )::"t_quickSort_partitionResult" ) OVER () AS "result" FROM "partition"  
+
     ROW(
) "p" LIMIT 1;
+
        "index"
 +
        ,"fn_quickSort_swap"( "a", "index", $3 )
 +
    )::"t_quickSort_partitionResult"
 +
FROM
 +
    "partition"
 +
WHERE
 +
    i = $3
 +
;
  
 
$BODY$ LANGUAGE 'sql' IMMUTABLE;
 
$BODY$ LANGUAGE 'sql' IMMUTABLE;
Line 172: Line 183:
 
----
 
----
  
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.
+
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.

Latest revision as of 09:25, 11 November 2013

Snippets

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.

Personal tools