[Matlab] quicksort (퀵소트)

코드 먼저 보여드리고 설명 하겠습니다.

X = [0.8147 0.9058 0.1270 0.9134 0.6324 0.2785 0.5469 0.9575 0.9649];
tic % 타이머 시작
X = bubbleSort(X);
%X = sort(X); % matlab 제공 sort 이거보다 빠를 수 있을깡..
toc % 타이머 끝

%% quickSort
function X = quickSort(X)
X = qSortRecursive(X, 1,length(X));
end

%% recursive
function X = qSortRecursive(X,left,right)

if (left >= right)
    return;
end

pivot = left;
i = pivot+1;
j = right;

while (i <= j)

    while (i <= right && ...
            (X(i) <= X(pivot)))
        i = i + 1;
    end
    while (j > left && ...
            X(j) >= X(pivot))
        j = j - 1;
    end

    if (i > j)
        tmp = X(j);
        X(j) = X(pivot);
        X(pivot) = tmp;
    else
        tmp = X(i);
        X(i) = X(j);
        X(j) = tmp;
    end
end

X = qSortRecursive(X, left, j-1);
X = qSortRecursive(X,j+1, right);
end

qSort.zip

0.00MB

기본적으로 Matlab 에서는 함수에 전달하는 변수가

포인터로 전송되는 것이 아닌

값으로 전달 되고

배열의 시작 지점이

0이 아닌 1인 이유로

다른 언어의 코드와 다를 수 있습니다.

 

데이터는

[3 5 1 8 6 2] 로 구성되어 있습니다

코드를 따라가며 퀵소트를 해봅시다!

퀵소트는 기본적으로

left 와 right 를 기준으로

둘중 한 지점을 pivot 으로 정하고

왼쪽을 pivot 보다 작은 수(혹은 큰 수)

오른쪽을 pivot 보다 큰 수(혹은 작은 수)

로 배치 시키고

그 가운데에 pivot 이 들어가는 형태입니다.

 

첫번째 swap 은 i 가 pivot 보다 크고

j 가 pivot 보다 작을 때

왼쪽에 작은 것들을 배치하고

오른쪽에 큰 것들을 배치하기 위해

두 값들을 swap 해줍니다.

그리고 이 과정을 i 와 j 가 교차하는 순간 까지!

해주고 나면

최종적으로

마지막 j 의 위치에는 pivot 보다 작은 수가 위치하고

그 왼쪽에는 pivot 보다 작은 수

오른쪽에는 pivot 보다 큰 수가 배치 됩니다.

(자세한 것은 직접 해보시면 감이 오실겁니다!!)

그렇게 pivot 을 j 와 swap 해주고

이후 pivot 의 왼쪽과 오른쪽을 sort 해주면

이것이 quicksort !

 

quick sort 의 특징으로는 배열을 pivot 기준으로 나눠주어

대략 n/2 정도로 분할 해서 sort 를 진행 하는 과정처럼 보입니다.

n (n/2 + n/2) ...

계속 2 로 나눠주는 과정이므로 log(n) 으로 고려합니다.

따라서 시간복잡도는 O(nlog(n))...

하지만..

최악의 상황에서는 n^2 이 되니..

그것은 분할이 안되는 경우입니다!!

그러면 계속 n*(1+n) 꼴이 되니..

버블 정렬이랑 다를게 없겠죠..