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.