일구

퀵 정렬(Quick Sort)는 분할 정복 알고리즘으로 분류 되지만 정복 후 분할하는 알고리즘이다.

분할할때는 O(n)

합병 시 O(1)

분할 정복과 반대 이다.

퀵정렬은 피봇(pivot)이라는 배열의 원소(숫자)를 기준으로 피봇보다 작은 숫자들은 왼편, 피봇보다 큰 숫자들은 오른푠에 위치하도록 분할한다.

A[12] =ㅣ6ㅣ3ㅣ11ㅣ9ㅣ12ㅣ2ㅣ8ㅣ15ㅣ18ㅣ10ㅣ7ㅣ14ㅣ

피봇을 A[0]=6으로 선택했다고 해보자

ㅣ3ㅣ2ㅣ6ㅣ11ㅣ9ㅣ12ㅣ8ㅣ15ㅣ18ㅣ10ㅣ7ㅣ14ㅣ

피봇 6을 기준으로 6보다 작은것은 왼쪽에 , 6보다 큰것은 오른쪽에 가져다 놓았다.

분할 정복(Divide-and-Conquer)알고리즘이란 주어진 문제의 입력을 분할하여 문제를 해결(정복)하는 방식의 알고리즘이다.

ㅣ37 10 22 30 35 13 25 24ㅣ

                                          ↙                               ↘

                          ㅣ37 10 22 30ㅣ                       ㅣ35 13 25 24ㅣ

                              ↙                                                     ↘ 

                ㅣ37 10 22 30ㅣ                     분할              ㅣ35 13 25 24ㅣ

                 ↙          ↘                                                    ↙           ↘

       ㅣ37 10ㅣ     ㅣ22 30ㅣ                                        ㅣ35 13ㅣ   ㅣ25 24ㅣ

      ↙     ↘         ↙       ↘                                           ↙   ↘        ↙    ↘

ㅣ37ㅣ  ㅣ10ㅣ  ㅣ22ㅣ  ㅣ30ㅣ                                   ㅣ35ㅣㅣ13ㅣㅣ25ㅣㅣ24ㅣ          

    //설명    37 10 22 30 35 13 25 24  8개의 입력을 index가 1개가 남을때까지 분할 하였다.

                분할 할때는 f(a,(a+b)/2);

                                f((a+b)/2+1,b);

                나누기만 하면 되니깐 O(1)의 시간이 걸린다.

             이제 합병 즉, 잘개 쪼갠 index들을 합쳐야한다.

  ㅣ37ㅣ  ㅣ10ㅣ   ㅣ22ㅣ  ㅣ30ㅣ                    ㅣ35ㅣ   ㅣ13ㅣ   ㅣ25ㅣ   ㅣ24ㅣ                                 합병을 하기 위해서 위에 글을 이어서 가보자.

                      분할에서 보이듯이 index가 한개가 남을때까지 나눈 상태이다.

합병을 할때는 나눈것들 끼리 비교하면서 합쳐야한다.

 ㅣ37 10ㅣ을 ㅣ37ㅣ ㅣ10ㅣ으로 나누었다. 

만약 A와 B의 크기가 각각 n과 m이라면, 최대 비교 횟수는 (n+m-1)이다. 

합병 시에 2개의 숫자 즉 처음에는 37과 10 중에 '승자' 작은숫자가 탄생하게 되고 작은 숫자는 합병된 C라는 배열에 저장된다.  A,B의 모든 (n+m)개의 숫자들은 결국 배열 C에 저장 되지만 마지막에 저장되는 숫자는 비교 할 숫자가 없어서 최대 비교 횟수는 (n+m-1) 여기에서 -1은 다시 설명하자면 ㅣ37ㅣ  ㅣ10ㅣ   ㅣ22ㅣ  ㅣ30ㅣ을 합병해서 ㅣ10  37ㅣ ㅣ22 30ㅣ으로 합병 했다고 가정해보자 ㅣ10  37ㅣ은 n이다.  ㅣ22 30ㅣ은 m이다.

                      →n번                    →m번   (다시 돌아 갈 일 없다. 그래서 n+m)

다시 처음으로 돌아갈 필요 없이 n개도 n번만 보면 되고 m개→도 m번→만 보면 된다.

-1은 10 22 30 순으로 합병이 되고 마지막 남은 37은 비교 할 숫자가 없다. 그래서 -1 이 된다.

3층ㅣ37ㅣ  ㅣ10ㅣ   ㅣ22ㅣ  ㅣ30ㅣ               ㅣ35ㅣ   ㅣ13ㅣ   ㅣ25ㅣ   ㅣ24ㅣ n/8

        ↘    ↙             ↘    ↙             합병           ↘    ↙              ↘    ↙

2층 ㅣ10  37ㅣ         ㅣ22 30ㅣ                            ㅣ13 35ㅣ          ㅣ24 25ㅣ  n/4

            ↘                   ↙                                        ↘                   ↙

1층        ㅣ10   22   30   37ㅣ                                      ㅣ13  24  25  35ㅣ n/2

                          ↖                                                          ↗

                                    ㅣ10  13  22  24  25  30  35  37ㅣ  n개

층별로 모든 원소가 다 참여 하고 있으니깐 O(n)이다.

결과적으로 합병 정렬의 시간복잡도는 (층수)xO(n) =log2n*O(n) = O(nlogn)이다.

층수도 n에 관계가 있는 것을 확인 할 수 있다.

45, 20, 60, 35, 10, 55, 90, 85, 75, 25

 위에 숫자들은 카드에 적혀져 있는 숫자들이다. 

이 중에서 85라는 숫자를 우리는 찾고 싶다. 

우리는 85라는 숫자가 최대 숫자라는 것을 기억 하고 카드를 한장씩 차례대로 뒤집어 보면서  85가 적힌 카드를 찾는 다면 1-1에 기록한 순차 탐색을 이용 한 것이다.

만약에 10장에 카드가 쌓여 있고 맨위에 있는 카드가 10이라는 것만 보이는 경우에 85 라는 숫자를 찾고 싶을 때 10 20 25 35 45 55 60 75 85 90 중에 순차 탐색에 경우에는 8장의 카드를 확인 한 후에 85를 찾을 수 있다.

카드가  10 20 25 35 45 55 60 75 85 90 정렬이 되어 있는 것이 확실하다면 카드의 앞 부분인 10부터 확인 할 필요는 없다.

정렬이 되어 있다면 중간을 찾아서 비교하면 된다.

      10 20 25 35 45 55 60 75 85 90

      중간 카드 45 나 55 중에 한개를 선택하고 45보다 찾고자하는 카드 85가 크면 45 이전 카드는 볼 필요가 없다.

알고리즘

오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반은 또 반으로 나누면서 원하는 데이터를 찾는 탐색 알고리즘을 이진탐색(Binary Search)라고 한다.

45 60 90

20 55 85  75

35 10 25

위와 같은 카드 10장이 다음 그림과 같이 바닥에 펼쳐져 있다.

알고리즘

가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법일 것이다.

마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어 든다.

위와 같이 찾는 방법을 순차탐색이라 한다. -> 들어온 입력 데이터를 차례대로 뿐만 아니라 전부 다 본거다.