Insertion Sort

From PostgreSQL wiki

Jump to: navigation, search

Snippets

Insertion_Sort

Works with PostgreSQL

8.4+

Written in

SQL

Depends on

Nothing


This is a very simple example of how to use Recursive CTE to implement the (inefficient) insertion sort algorithm by me

WITH recursive isort(arr, POSITION, sorted_count) AS (
  SELECT ARRAY[7,3,6,9,0,42,9], 1, 1
  UNION ALL
  SELECT CASE WHEN POSITION=1 OR arr[POSITION]>=arr[position-1] THEN arr
              ELSE arr[1:position-2]||arr[POSITION]||arr[position-1]||arr[POSITION+1:array_length(arr, 1)] END,
         CASE WHEN POSITION=1 OR arr[POSITION]>=arr[position-1] THEN sorted_count+1
              ELSE position-1 END,
         CASE WHEN POSITION=1 OR arr[POSITION]>=arr[position-1] THEN 1 ELSE 0 END + sorted_count
  FROM isort
  WHERE sorted_count <= array_length(arr,1))
SELECT * FROM isort;

If you just want the sorted array, you could use select arr from isort where sorted_count=array_length(arr,1)+1 instead of select * from isort.

Personal tools