ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 퀵 정렬 Quick Sort
    알고리즘/알고리즘 개념 및 정리 2019.03.09 19:30

    선택, 버블, 삽입 정렬 알고리즘들은 시간복잡도가 평균 O( N^2)였으며

    이러한 알고리즘들은 정렬할 데이터의 수가 10만이 넘어가면 

    너무나 많은 연산이 요구되므로 사용하기 어렵다.



    이에 반해 분할 정복 알고리즘 중 하나인 퀵 정렬알고리즘은 평균 시간복잡도가 O( N * logN )이다



    퀵 정렬은 불안정 정렬에 속하며 다른 원소와 비교하는 것만으로

    정렬을 진행하기 때문에 비교정렬이라도고 할 수 있다.




    * 분할 정복의 의미* 

    하나의 큰 문제를 2개의 문제로 분리하여 각각 해결한 뒤

    다시 그 결과를 합하여 원래 문제를 해결하는 것을 의미한다.



    퀵 정렬의 원리는 특정한 값을 기준으로 두 개의 비균등한 크기로 나누고

    나눈 부분리스트를 정렬한 뒤 다시 합하여 정렬된 리스트를 만들어내는 정렬이다.

    여기서 특정한 기준이 되는 값을 피벗(Pivot)이라고 부른다.



    이제 그 과정을 한번 살펴보도록 하겠다.



    1 4 10 8 6 9 2 7 3 5 

    위와 같은 숫자들이 있다고 하고 이를 퀵 정렬을 이용하여 정렬해보겠다.

    퀵정렬을 할 때 일반적으로 제일 앞에 있는 수를 피벗 값으로 잡는다.



    1 4 10 8 6 9 2 7 3 5 

    '왼큰오작'로 진행된다!!

    1보다 큰 숫자를 왼쪽에서 부터 찾고 1보다 작은 숫자를 오른쪽에서 부터 찾는다.

    10이라는 숫자를 찾을 수 있었지만 1보다 작은 수는 찾을 수 없었다.

    이렇게되면 자기자신을 작은 값으로 고르게 되므로 작은 값은 1이된다.

    작은수 1이 큰 수 10보다 왼쪽에 있으므로 이는 엇갈렸다고 말할 수 있다.

    그러므로 피벗과 작은값 즉, 1과 1을 바꾸게된다.

    여기서는 자기자신끼리 바꾼 것이므로 당연히 변화가 없다. 

     

    그러므로 아무런 변화가 없으며 이 때는 피벗 값인 1의 왼쪽에는 1보다 작은 값들이

    존재하는 것이며 오른쪽에는 1보다 큰 값들이 존재하게 된다.


    왼쪽에는 아무것도 없으므로 무시하고 1을 기준으로 오른쪽 배열의 퀵정렬을 진행하면 된다.

    이제 다시 왼쪽과 오른쪽에서 퀵 정렬을 순환적으로 진행하게 된다.


    1 4 10 8 6 9 2 7 3 5

    오른쪽 배열에서의 피벗값은 4가된다. 이제 4보다 큰 값을 왼쪽에서부터 찾고 작은 값을 오른쪽에서부터 찾는다.

    큰 값으로 10을 찾을 수 있엇고 작은 값으로 3을 찾을 수 있었다.

    찾은 두 수의 자리를 바꾸어준다. 


    1 4 3 8 6 9 210 5

    이제 다시 4보다 큰값을 왼쪽에서부터 찾고 작은 값을 오른쪽에서 부터 찾는다.

    큰 값으로 8,  작은값으로 2를 찾았고 이 둘을 바꾸어준다.


    1 4 3 2 6 9 8 7 10 5

    역시 아까의 과정을 반복한다. 하지만 아까와 다른 점이 생겼다. 

    보통 작은 값은 오른쪽에 큰값은 왼쪽에 있었는데

    지금은 그 둘이 엇갈리게 되었다. 

    이렇게 엇갈리게되는 경우 작은 값과 피벗 값을 바꾸어주면된다.


    1 2 3 4 6 9 8 7 10 5

    이제 이렇게 되면 아까 제일 위의 1에서 처럼

    4를 기준으로 왼쪽으로는 4보다 작은 수들이 배열되어있고

    오른쪽으로는 4보다 큰 수들이 배열되어있게된다.

    이제 4를 기준으로 왼쪽의 피벗은 2 오른쪽 피벗은 6으로 정렬을 진행하면 정렬이 완성된다.



    1 2 3 4 6 9 8 10 5

    피벗이 2인 배열부터 진행해보면 왼쪽부터 큰 것을 찾고 오른쪽부터 작은 것을 찾는다.

    왼쪽부터 큰 값은 3인데 작은 값은 없다. 그러므로 자기자신을 작은 값2로 고르게 되므로 2와 2를 바꾸게 된다.


    1 2 3 4 6 9 8 7 10 5

    위와 마찬가지의 이유로 3 또한 그대로가 된다.



    1 2 3 4 6 9 8 10 5

    오른쪽의 배열을 정렬해보자

    왼쪽에서 큰 값이 9 오른쪽에서 작은 값이 5이므로 둘의 자리를 바꾼다.


    1 2 3 4 6 5 8 7 10 9

    이번에는 큰 값이 8 작은 값이 5인데 엇갈려버렸으므로 작은 값 5와 피벗 값을 바꾼다.


    1 2 3 4 5 6 8 7 10 9

    역시 작은 값과 바꾼 피벗 값 6을 기준으로 왼쪽은 6보다 작은 수들이

    오른쪽엔 6보다 큰 수들이 존재한다. 역시나 피벗 값을 잡고 다시 정렬을 진행하면 된다.


    왼쪽의 1 2 3 4 5의 경우 이미 정렬이 되어있으나 빼놓고 할 수는 없으므로

    다시 정렬을 시도한다. 하지만 이미 정렬이 되어있으므로 비교 시 항상 엇갈려

    작은 수는 피벗 자기 자신이 될 것이고 결국 작은 수와 피벗의 교환이므로 변화는 없다.

    .

    .

    .

    .


    1 2 3 4 5 6 7 8 9 10

    위와 같은 진행을 반복하면 정렬이 완성된다.




    이러한 정렬이 빠른 이유는 쉽게 생각해볼 수 있다.


    1 4 10 8 6 9 2 7 3 5 

    10개의 숫자를 정렬하려고 했을 때 이전에 배운 선택이나 버블, 삽입정렬의  경우 평균적으로 

    N^2 = 10*10 = 100 



    하지만 퀵정렬의 경우 분할하기 때문에

    1 4 10 8 6 = 5^5 = 25

    9 2 7 3 5 = 5^5 = 25

    25 + 25 = 50 

    50 밖에 되지 않는다.


    위와 같은 원리로 각자 정리 후 더한다고 생각해보면 당연히 훨씬 더 빠르다는 것을 알 수 있다.




    하지만 이러한 퀵정렬은 이미 거의 다 정렬된 경우에는 분할 정렬의 이점을 살릴 수가 없다.

    최악의 경우 시간복잡도가 O(N^2)가 된다.



     1 2 3 4 5 6 7 8 

    위와 같은 숫자들이 있다면 1을 피벗으로 잡고 진행하더라도 큰 수는 찾을 수 있으나

    작은 수는 없으므로 자기자신이 되어 엇갈리게된다. 그러므로 1만 정렬이 될 것이고

    고작 1 하나만 정렬이 되고 큰 값만 7개가 남는다. 역시나 다음으로 2를 진행하더라도

    2만 정렬될 뿐 큰 값만 6개가 남게되므로 분할 정렬의 이점을 살릴 수 없는 예시가 된다.


    '알고리즘 > 알고리즘 개념 및 정리' 카테고리의 다른 글

    퀵 정렬 Quick Sort  (0) 2019.03.09
    삽입정렬 Insert Sort  (0) 2019.03.07
    버블 정렬 Bubble Sort  (0) 2019.03.07
    선택정렬 Selection Sort  (0) 2019.03.07
    AES 복호화 (Rijndael 알고리즘)  (3) 2018.01.26
    AES암호화 (Rijndael 알고리즘)  (3) 2018.01.25

    댓글 0

Designed by Tistory.