database.sarang.net
UserID
Passwd
Database
DBMS
MySQL
PostgreSQL
Firebird
ㆍOracle
Informix
Sybase
MS-SQL
DB2
Cache
CUBRID
LDAP
ALTIBASE
Tibero
DB 문서들
스터디
Community
공지사항
자유게시판
구인|구직
DSN 갤러리
도움주신분들
Admin
운영게시판
최근게시물
Oracle Q&A 40756 게시물 읽기
No. 40756
쿼리 퀴즈입니다.(퀵소트 따라하기)
작성자
김흥수(protokhs)
작성일
2015-03-30 13:49ⓒ
2015-03-31 14:12ⓜ
조회수
8,632

 두뇌활동과 sql 자유자재로 다루기에 도움이 되는 쿼리 퀴즈입니다.

 

퀵소트는 아주 잘 알려진 정렬 알고리즘 중 하나이다.
알고리즘이 아주 간단한데
다음 단계를 거치면 된다.
 
1. 목록중 하나를 골라(주로 첫 항목) 그보다 작거나 같은 항목들과 큰 항목으로 분리한다.
2. 위에서 분리된 각각 항목을 퀵소트한다.
3. 작거나같은항목 퀵소트 결과 + 선택항목 + 큰항목 퀵소트 결과로 합친다.
 
이렇게 하면 퀵소트가 된다.
 
예를 들어서
 
38,27,43,9,3,82,10
 
의 목록이 있다면
제일 첫 항목인 38을 선택하여 이보다 작거나 같은 목록 27,9,3,10 과 43,82 로 나누면 다음과 같이 된다.
 
27,9,3,10    ,38,      43,82
 
그다음 두 부분에  똑같은 작업을 하면
 
9,3,10    ,27    ,38,      43,      82
 
그다음은
 
3    ,9,    10    ,27    ,38,      43,      82
 
이 되어 소트가 완성된다.
 
sql로 이 소트되는 중간 결과를 다음과 같이 출력하라.
 
 
레벨 중간결과
0 38,27,43,9,3,82,10
1 27,9,3,10,38,43,82
2 9,3,10,27,38,43,82
3 3,9,10,27,38,43,82
 
 
이 글에 대한 댓글이 총 1건 있습니다.

 흑흑 ...

이 문제는 재미가 없나보네요...

 

재미는 없어도 이 문제가 좀 의미는 있는데요..

왜냐면 SQL로도 분할 정복이 가능하다는 것을 알 수 있기 때문입니다.

 

조금 복잡하지만 아래와 같습니다.

 

with base_table as
(
    select
        --'38,27,65,102,43,10,82,3,25,67,33,88' target
        '38,27,43,9,3,82,10' target
    from    dual
)
 
, recur (target,cnt,head,kind,maxlevel,ord) as
(
select
    target,0 cnt,'X',1 , length(target) - length(replace(target,',','')),0
from    base_table
union all
select
    case when a.kind = 2 or target = replace(target,',') then
        a.target
    else
        (
            select
                case
                    when dvd.lvl = 1 then
                        listagg(
                            case when to_number(substrb(a.target,1,instr(a.target,',')-1)) >= to_number(substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)) then
                                substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)
                            end
                            ,',') within group (order by column_value)
                    when dvd.lvl = 2 then
                        substrb(a.target,1,instr(a.target,',')-1)
                    else
                        listagg(
                            case when to_number(substrb(a.target,1,instr(a.target,',')-1)) < to_number(substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)) then
                                substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)
                            end
                            ,',') within group (order by column_value)
                end
            from    table(select collect(level) from dual connect by level <= length(a.target) - length(replace(a.target,',','')) )
        )
    end target
    , a.cnt + 1
    , substrb(a.target,1,instr(a.target,',')-1) head
    , case when a.kind = 2 or target = replace(target,',') then 2 else dvd.lvl end
    , maxlevel
    , ord * 3 + case when a.kind = 2 or target = replace(target,',') then 2 else dvd.lvl end
from    recur a
        , (
                    select
                        level lvl
                    from    dual
                    connect by level < 4
        ) dvd
where   a.cnt < a.maxlevel
and     lvl < (case when a.kind = 2 or target = replace(target,',') then 2 else 4 end )
and
    case when a.kind = 2 or target = replace(target,',') then
        a.target
    else
        (
            select
                case
                    when dvd.lvl = 1 then
                        listagg(
                            case when to_number(substrb(a.target,1,instr(a.target,',')-1)) >= to_number(substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)) then
                                substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)
                            end
                            ,',') within group (order by column_value)
                    when dvd.lvl = 2 then
                        substrb(a.target,1,instr(a.target,',')-1)
                    else
                        listagg(
                            case when to_number(substrb(a.target,1,instr(a.target,',')-1)) < to_number(substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)) then
                                substr(a.target, instr(a.target||',',',',1,column_value) +1 , instr(a.target||',',',',1,column_value + 1) - instr(a.target||',',',',1,column_value) - 1)
                            end
                            ,',') within group (order by column_value)
                end
            from    table(select collect(level) from dual connect by level <= length(a.target) - length(replace(a.target,',','')) )
        )
    end is not null
 
)
select
    a.cnt
    , a.target
from
    (
        select
            a.cnt
            , listagg(a.target,',') within group ( order by a.cnt,a.ord) target
            , lag(listagg(a.target,',') within group ( order by a.cnt,a.ord)) over (order by a.cnt) pre_target
        from
            (
                select
                    a.target
                    ,a.cnt
                    ,a.head
                    ,a.kind
                    ,a.ord
                    , max(a.head) over (partition by a.cnt) maxhead
                from    recur a
            ) a
        where   a.maxhead is not null
        group by
            a.cnt
    ) a
 
 
recursive-with를 사용하여 재귀호출을 흉내냈습니다.
 
 recursive-with는 계층구조 뿐 아니라 일반적인 점화식에 쓰일 수 있고
이와 같이 재귀호출 구조에도 사용할 수 있습니다.(트리 탐색도 재귀적이고...)
 
 
김흥수(protokhs)님이 2015-04-08 09:06에 작성한 댓글입니다.
이 댓글은 2015-04-08 09:08에 마지막으로 수정되었습니다.
[Top]
No.
제목
작성자
작성일
조회
40761쿼리 퀴즈입니다(울타리 자르기) [1]
김흥수
2015-04-01
11296
40760교차되는 값 데이타구하기 query 질문 [6]
강형석
2015-03-31
8182
40759ORA-00979 에러에 대한 문의 [1]
이성근
2015-03-31
6550
40756쿼리 퀴즈입니다.(퀵소트 따라하기) [1]
김흥수
2015-03-30
8632
40755쿼리 퀴즈입니다.(시계맞추기) [7]
김흥수
2015-03-30
9754
40754초보자 쿼리 짜는것좀 도와주세요 ㅠㅠ [2]
첼시리우
2015-03-26
6473
40753TYPE object 를 만들고 다른 디비에서 디비 링크로 사용 할 수 없나요? [2]
안녕하세요
2015-03-26
6470
Valid XHTML 1.0!
All about the DATABASE... Copyleft 1999-2024 DSN, All rights reserved.
작업시간: 0.017초, 이곳 서비스는
	PostgreSQL v16.2로 자료를 관리합니다