[PHP] 퀵정렬을 활용하여 다차원 배열 소팅

 

sort.php

0.01MB

 

이번에 다차원 배열 소팅을 개발하였는데, 재미있게 개발해서 글을 남겨본다.

 

다차원 배열을 sort를 해야하고 양이 많다 보니 수행속도가 빨라야 했고 데이터가 어느정도 정렬이 된 상태여서 

퀵정렬을 사용하였다.

 

<?php

class Csort
{
    public static function _sort( $sort_items, $sort_method_str )
    {
        $sort_method_arr = preg_split( "/,/", $sort_method_str, -1, PREG_SPLIT_NO_EMPTY );
        $qlen = count($sort_items)-1;
        $fields = array();
        $sort_range = array();
        $methods = array();

        foreach( $sort_method_arr as $sort_method )
        {
            $str_arr = preg_split( "/\s/", trim($sort_method), -1, PREG_SPLIT_NO_EMPTY );
            $fields[] = $str_arr[0];
            $methods[] = $str_arr[1];
        }
        $count = 0;
        if( $methods[0] == "asc" )
            Csort::sort_asc( $sort_items, 0, -1, $fields[0] );
        else if( $methods[0] == "desc" )
            Csort::sort_desc( $sort_items, 0, -1, $fields[0] );

        if( count($sort_method_arr) > 1 )
        {
            $previous_val = $sort_items[0][$fields[1]];
            $previous_count = count( array_keys(array_column( $sort_items, $fields[1] ), $previous_val) )-1;
            Csort::recusive_by_sort( $sort_items, 0, $previous_count, $fields, $methods, 1 , -1, null, $count );
        }
        return $sort_items;
    }

    public static function recusive_by_sort( &$sort_items, $start, $last, $fields, $methodes, $index=1, $end=-1, $tmp = null)
    {
        if( $end == -1 )
            $end = count( $sort_items )-1;

        $w = 1;
        while( $start < $end )
        {
            $field = "";
            $val = "";
            $field = $fields[ ($index -1) ];//이전에 소팅했던 filde를 구함
            $val = $sort_items[$start][$field];

            if( $index == 1 )
                $last = (count( array_keys(array_column( $sort_items, $field ), $val) )-1) + $start;
            else
                $last = (count( array_keys(array_column( $tmp, $field ), $val) )-1) + $start;

            if( $methodes[$index] == "asc")
                Csort::sort_asc( $sort_items, $start, $last, $fields[$index] );
            else if( $methodes[$index] == "desc")
                Csort::sort_desc( $sort_items, $start, $last, $fields[$index] );

            if( array_key_exists( $index+1 , $fields ) )//다음 정렬이 필요한 경우
            {
                $tmp_sort_items = array_slice( $sort_items, $start, ($last-$start)+1 );
                $tmp_field = $fields[ ($index ) ];
                $tmp_val = $tmp_sort_items[0][$tmp_field];
                $tmp_last = (count( array_keys(array_column( $tmp_sort_items, $tmp_field ), $tmp_val) )-1) + $start;
                $tmp_index = $index + 1;

                Csort::recusive_by_sort( $sort_items, $start, $tmp_last, $fields, $methodes, $tmp_index, $last, $tmp_sort_items );
            }
            $start = ($last + 1);
        }
    }

    public static function pivot_replace( $key, $value )//피벗이 비교연산자로 비교가 불가능할떄 replace하기위해
    {
        if( $key == 'sample' )
        {
            if( !empty($value) )
                return substr( $value, 4 );
            else
                return 1;
        }

        return $value;
    }

    public static function sort_desc( &$item, $L=0, $R=-1, $key )//내림차순
    {
        if($R==-1)
            $R=count($item)-1;

        $l_temp = null;
        $r_temp = null;
        $pivot = Csort::pivot_replace( $key, $item[$L][$key] );
        for( $left = $L, $right = $R; $left < $right; $right-- )
        {
            while( Csort::pivot_replace( $key, $item[$right][$key] ) <= $pivot && $left < $right )
                 $right--;

            if( $left < $right )
            {
                $l_temp = $item[$left];
                $item[$left] = $item[$right];
                $item[$right] = $l_temp;
            }

            while( Csort::pivot_replace( $key, $item[$left][$key] ) >= $pivot && $left < $right )
                 $left++;
                 
                 if( $left >= $right ) break;
            $r_temp = $item[$right];
            $item[$right] = $item[$left];
            $item[$left] = $r_temp;
        }

        if( $left > $L )
            Csort::sort_desc( $item, $L, $left - 1, $key );
        if( $left < $R )
            Csort::sort_desc( $item, $left + 1, $R, $key );
    }

    public static function sort_asc( &$item, $L=0, $R=-1, $key )//오름차순
    {
        if($R==-1)
            $R=count($item)-1;

        $l_temp = null;
        $r_temp = null;
        $pivot = Csort::pivot_replace( $key, $item[$L][$key] );
        for( $left = $L, $right = $R; $left < $right; $right-- )
        {
            while( Csort::pivot_replace( $key, $item[$right][$key] ) >= $pivot && $left < $right )
                $right--;
            if( $left < $right )
            {
                $l_temp = $item[$left];
                $item[$left] = $item[$right];
                $item[$right] = $l_temp;
            }

            while( Csort::pivot_replace( $key, $item[$left][$key] ) <= $pivot && $left < $right )
                $left++;

            if( $left >= $right ) break;
            $r_temp = $item[$right];
            $item[$right] = $item[$left];
            $item[$left] = $r_temp;
        }

        if( $left > $L )
            Csort::sort_asc( $item, $L, $left - 1, $key );
        if( $left < $R )
            Csort::sort_asc( $item, $left + 1, $R, $key );
    }
}
$sort_items = array();
//for( $i=0; $i < 5000; $i++ )
for( $i=0; $i < 10; $i++ )
{
    $temp = array( 'first' => rand(0, 10),
                   'second' => rand(0, 10),
                   'third' => rand(0, 10),
                   'fourth' => rand(0, 10) );

    array_push( $sort_items, $temp );
}

$sort_items = Csort::_sort($sort_items, "first asc, second asc, third asc, fourth asc" );
print_r( $sort_items );

/*************** output ***************
Array
(
    [0] => Array
        (
            [first] => 0
            [second] => 1
            [third] => 10
            [fourth] => 5
        )

    [1] => Array
        (
            [first] => 0
            [second] => 4
            [third] => 4
            [fourth] => 6
        )

    [2] => Array
        (
            [first] => 1
            [second] => 2
            [third] => 7
            [fourth] => 5
        )

    [3] => Array
        (
            [first] => 1
            [second] => 5
            [third] => 0
            [fourth] => 7
        )

    [4] => Array
        (
            [first] => 1
            [second] => 6
            [third] => 4
            [fourth] => 4
        )

    [5] => Array
        (
            [first] => 1
            [second] => 8
            [third] => 5
            [fourth] => 10
        )

    [6] => Array
        (
            [first] => 2
            [second] => 6
            [third] => 0
            [fourth] => 0
        )

    [7] => Array
        (
            [first] => 2
            [second] => 9
            [third] => 1
            [fourth] => 1
        )

    [8] => Array
        (
            [first] => 3
            [second] => 7
            [third] => 10
            [fourth] => 3
        )

    [9] => Array
        (
            [first] => 10
            [second] => 2
            [third] => 7
            [fourth] => 1
        )

)
*/