(선택그룹) 선택 정렬 / 버블 정렬 / 퀵 정렬

선택 정렬은 정렬되지 않은 전체 자료 중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 정렬 방식이다.

80, 50, 70, 10, 60, 20, 40, 30

위의 데이터 그룹이 있을때 그리고 오름차순 정렬이라면, 첫 번째 위치는 키 값이 가장 작은 자료의 위치이다.

이렇게 작동한다. 처음 인덱스에서 출발을 해서 자료의 전체 크기를 돌면서 가장 작은 자료를 찾아 첫번째 인덱스와 교환을 하고

다시 두번째인덱스부터 출발해서 가장 작은 값을 찾으면 두번째 인덱스와 교환해서 넣고..

반복하다가 위에 데이터 그룹을 기준으로 마지막 8번째라면 그건 그냥 가장 큰값이 될테니 추가적인 위치교환없이 정렬이 마무리 된다.

C#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace studycsharp

{

    class Program

    {

        public void SelectSort(int[] value, int count)

        {

            int i = 0;

            int j = 0;

            int min = 0;

            int temp = 0;

            for(i = 0; i < count - 1; i++)

            {

                min = i;    //최소값의 위치를 보관한다

                for(j = i + 1; j < count; ++j)

                {

                    if(value[j] < value[min])

                    {

                        min = j;

                    }

                }

                temp = value[i];

                value[i] = value[min];

                value[min] = temp;

                Console.WriteLine("Step - {0}", i);

                printArray(value);

            }

        }

        private void printArray(int [] value)

        {

            foreach(int Result in value)

            {

                Console.Write("{0} ", Result);

            }

        }

        static void Main(string[] args)

        {

            int[] value = { 80, 50, 70, 10, 60, 20, 40, 30 };

            Program test = new Program();

            test.SelectSort(value, 8);

        }

    }

}

두개의 루프를 돌면서 실행되는 비교연산의 전체 횟수는 O(n2)이다. 이때 실행되는 자료의 교환횟수는 바깥 루프의 횟수와 같으며

각 교환마다 3번의 이동이 필요하니까 이동연산의 횟수는 O(3(n-1)) = O(n)이다.. 

최선, 평균, 최악 : O(n^2 + n) = O(n^2) 이다..

무척 느린 알고리즘인데 다만 이동연산 횟수가 O(n)이니까 자료의 크기가 큰 정렬에는 유리하다. 최악이나 평균이나 정렬의 효율성은 n^2다..

정렬의 안정성을 만족하지 않는다는 단점이 있다..

---

버블 정렬 : 정렬되지 않은 전체 자료들을 대상으로 인접한 두 개 자료의 키 값을 비교하여 위치를 교환하는 정렬

교환 연산이 마치 공기방울이 물 위로 올라가듯이 위치 교환 연산을 차례로 수행한다.

또 위와 똑같이 데이터 그룹은 80, 50, 70, 10, 60, 20, 40, 30 즉 8개 정수이다.

그러니까 첫번쨰 인덱스부터 시작하는데..

인덱스 + 1과 비교를 계속하면서 오름차순을 예로 큰 값을 우측으로 옮기는거야 그럼 가장 마지막 인덱스에는 큰값이 저장되겠지...

C#

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace studycsharp

{

    class Program

    {

        public void SelectSort(int[] value, int count)

        {

            ////선택 정렬 O(n^2)

            //int i = 0;

            //int j = 0;

            //int min = 0;

            //int temp = 0;

            //for(i = 0; i < count - 1; i++)

            //{

            //    min = i;    //최소값의 위치를 보관한다

            //    for(j = i + 1; j < count; ++j)

            //    {

            //        if(value[j] < value[min])

            //        {

            //            min = j;

            //        }

            //    }

            //    temp = value[i];

            //    value[i] = value[min];

            //    value[min] = temp;

            //    Console.WriteLine("Step - {0}", i);

            //    printArray(value);

            //}

            int temp = 0;

            //전체 자료 갯수보다 1적은 횟수만큼 루프를 돈다

            //정렬의 마지막에 남은 자료는 최대 자료이기 때문에..

            for(int i = 0; i < count - 1; ++i)

            {

                for(int j = 0; j < count - 1 - i; ++j)    //이렇게 하면 하나씩 오른쪽에서 인덱스가 줄어든다..

                {

                    if(value[j] > value[j + 1])

                    {

                        temp = value[j];

                        value[j] = value[j + 1];

                        value[j + 1] = temp;

                    }

                }

                Console.WriteLine("Step - {0}", i);

                printArray(value);

            }

        }

        private void printArray(int [] value)

        {

            foreach(int Result in value)

            {

                Console.Write("{0} ", Result);

            }

        }

        static void Main(string[] args)

        {

            int[] value = { 80, 50, 70, 10, 60, 20, 40, 30 };

            Program test = new Program();

            test.SelectSort(value, 8);

        }

    }

}

버블 정렬은 정렬전 상태에 따라서 이동 연산의 횟수에 차이가 있다. 자료가 먼저 완전히 정렬되었다면 자료의 이동 연산은 0회 발생

역순이라면 i번째 정렬에서 n - i번 자료를 이동하니까..모두 n(n - 1) / 2회..

어쩄든 비교 연산과 이동연산의 합인데..

최선, 최악, 평균 : O(n^2)이다..

왜냐면..아무리 정렬전 자료의 상태에 따라 이동연산의 횟수가 차이가 있긴하지만..비교연산이 n2이라서 그렇다..그리고 이동 연산횟수도 n^2이니까

자료의 크기가 클때도 사용하면 안된다. 그러나 정렬의 안정성은 유지되기 때문에 ...

---

퀵 정렬은 중심값(피봇)을 기준으로 두 자료의 키 값을 비교하여 위치를 교환하는 정렬방식

피봇 기준의 위치 교환이 끝난 다음 피봇을 기준으로 2개 부분 집합으로 나누고 다시 퀵 정렬을 수행한다..분할정복이지..

데이터는 위의 입력 데이터와 같다 80, 50, 70, 10, 60, 20, 40, 30의 8개의 정수로 구성되어있다. 오름차순으로 정렬이 되고..

인접한 피봇을 기준으로 두 자료의 키 값을 비교하여 위치를 교환한다라..

가장 오른쪽 30을 피봇으로 놓는다면..(계속 가장 오른쪽을 기준으로 둔다) 그리고 자료 교환을 위해 왼쪽 끝에서 오른쪽으로 움직이면서

피봇보다 큰 자료를 찾는 Left와 오른쪽에서 왼쪽으로 움직이면서 피봇보다 작은 자료를 찾는 Right를 사용

(왜 Left가 피봇보다 큰 자료 Right가 피봇보다 작은자료냐면..오른차순이라 그렇다, 그리고 움직이는 순서는 Left가 먼저 이동함)

즉, Left으로는 피봇 값보다 큰 값을 찾고, Right으로는 피봇 값보다 작은 값을 찾는다. 그리고 Left는 Right까지 Right는 Left보다 더 왼쪽으로 이동은 불가하다는 조건이다..(어쨌든 둘이 만나야 끝난다)

그럼 위의 데이터를 예로 본다면 현재 Left는 80에서 시작해서 못움직임..(왜냐면 피봇 값보다 큰 값을 이미 시작부터 찾았으니까..)

Right는 30에서 이동해서 점차 왼쪽으로 가는데 20에서 멈춘다(왜냐면 피봇 값보다 작은 값을 만났으니까..) 그 다음에 둘다 만족하는 값을 찾았다면..

(Left는 80을 가리키고 Right는 20을 가리키는게 만족한 상태, 값을 찾은거다) 둘의 위치를 교환하고..

다시 이동을 시작하는데..우선 이동전에

교환뒤의 데이터는

20, 50, 70, 10, 60, 80, 40, 30 이렇게 된다..현재 Left는 20의 위치에 Right는 80의 위치에 있다..자 이제 다시 이동시작이다..

Left는 50으로 이동했는데..또 바로 멈추고..Rigts는 60을 지나서 10에서 멈춘다. 또 두 위치를 교환하고..

20, 10, 70, 50, 60, 80, 40, 30 이렇게 데이터가 정렬되고..

다시 이동을 시작하는데 이때 위치는 Left는 10에 Right는 50에 있다..

Left는 이동했는데 70에서 또 바로 멈추고...Right는 이동하다보니..70에서 Left를 만나서 더이상 이동못하고..결국 마지막으로 Left와 Right가 서로 가리키는 70과 피봇키인 30을 위치교환하게 된다.

일단 첫번째 정렬이 끝난뒤에 상태는..

20, 10, 30, 50, 60, 80, 40, 70의 데이터 상태가 되고

그리고 이제 부분 집합으로 나뉜상태에서 분할정복을 시행한다..어떻게?

변경된 30피봇을 기준으로 20, 10이 왼쪽 부분집합 50, 60, 80, 40, 70 이 오른쪽 부분집합이고 각각 퀵 정렬을 수행하면 된다.

잠깐 왼쪽 부분집합을 더 보면..

피봇을 오른쪽 10으로 두고보면 Left는 자료 20을 Right는 10을 가리키고 이동하면

Left는 가리킴과 동시에 멈추고 Right는 더 작은 값을 찾다가 Left를 만나서 멈추고..결국 둘다 10에서 멈춘상태..

Left와 Right가 동시에 가리키는 값과 피봇값을 교환하니 10, 20, 30, 50, 60, 80, 40, 70 상태가 되고..

피봇10을 기준으로 더 이상 부분 집합이 될 수 없으니까..기존 30을 기준으로 나뉜 오른쪽 부분 집합에 대해서 퀵 정렬을 하게 된다..

그런데 여기서..항상 피봇을 오른쪽으로 하게 된다면 최악의 경우...오른쪽 부분집합만 생기는 경우가 있다...

이렇게 되면..최악의 경우 

왼쪽부분 집합은 한번에 끝나게 되고..왼쪽 오른쪽 균형있게 되려면..중앙값을 피봇값으로 해야한다..

• 

  최악의 경우, 다음 그림과 같이 매 재귀 호출마다 데이터 집합의 분할이 1 : n-1로 이루어진다.

  

  이렇게 되면 재귀 호출의 깊이는 n-1이 되고, 재귀 호출마다 정렬 대상의 범위도 1씩 줄어든다

• 평균의 경우

  

  

퀵 정렬은 피봇을 기준으로 두개 부분 집합으로 나누어 자료의 위치를 교환하기 때문에  n개의 자료를 평균 O(nlog2n)번 만에 정렬하는 효율성을 가진다. 

한쪽으로 쏠리면 O(n^2)효율성을 가진다..안정성이 유지되지 않음..

어쨌든 위의 이야기를 보면 피봇의 값을 중앙값으로 해야한다는것인데.. 중앙값은 삼중앙 알고리즘으로 구하면 된다.

이 삼중앙 알고리즘은 첫번째 중간, 마지막 색인의 값을 취해서 그 셋중 가운데 값을 기준값으로 사용하는것..

게임프로그래머를 위한 자료구조에서의 퀵 정렬은 위와 조금 다르다.

피봇값은 삼중앙 알고리즘으로 중앙값으로 찾고, 피봇이라는 변수에 그 중앙값을 넣고

중앙값에 배열의 가장 (부분또는 전체겠지..)앞의 값을 넣는다. 

그러면 배열의 첫번째 칸은 빈칸이 되고..이 빈칸이 계속 옮겨진다..

어떻게? 일단 위에서는 Left가 먼저였지만, 이 책에선 Right가 먼저다..기준 값보다 작은 값을 발견하면 멈추고....그 값을 아까 위에서 만든 첫번째

빈칸으로 옮기고(그러면 Right가 멈춘곳이 빈칸이 되는것이다)..이제 Left 이동이 시작된다..큰 값을 만나면..멈추고 그 값을 아까 Right가 멈춘 빈칸에

넣는다..이런식으로 작동한다..(Right색인과 Left색인에 서로 값을 넣고 넣고..이동하는듯한 모습이 나오게 된다)

그런데 넣은다음에 넣는곳을 가리키는 색인을 한단계 이동해야할위치로 이동시킨다.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace studycsharp

{

    class Program

    {

        int FindMedianOfThree(int[] value, int iFirst, int iSize)

        {

            int last = iFirst + iSize - 1;

            int mid = iFirst + (iSize / 2);

            if (value[iFirst] < value[mid] &&

                value[iFirst] < value[last])

            {

                if (value[mid] < value[last])

                    return mid;

                else

                    return last;

            }

            if(value[mid] < value[iFirst] && 

                value[mid] < value[last])

            {

                if (value[iFirst] < value[last])

                    return iFirst;

                else

                    return last;

            }

            if (value[mid] < value[iFirst])

                return mid;

            else

                return iFirst;

        }

        void QuickSort(int[] value, int iFirst, int iSize)

        {

            int iPivot; //기준값

            //현재의 부분 배열의 마지막 칸 색인

            int iLast = iFirst + iSize - 1;

            int iMid;

            int iLower = iFirst;

            int iHigher = iLast;

            //칸이 하나이면 배열을 정렬할 필요가 없다

            if(iSize > 1)

            {

                iMid = FindMedianOfThree(value, iFirst, iSize);

                iPivot = value[iMid];

                

                value[iMid] = value[iFirst];

                //하한 색인이 상한 색인보다 작을때..왼쪽에 있을때..

                while(iLower < iHigher)

                {

                    while (iPivot < value[iHigher] && iLower < iHigher)

                        --iHigher;

                    if(iHigher != iLower)

                    {

                        value[iLower] = value[iHigher];

                        ++iLower;   //왜 1씩 증가시키냐면..

                    }

                    while (iPivot > value[iLower] && iLower < iHigher)

                        ++iLower;

                    if(iHigher != iLower)

                    {

                        value[iHigher] = value[iLower];

                        --iHigher;  //왜 1을 감소시키냐면..

                        //위와 같은 이유인데 값을 넣게 되면..

                        //안해도 상관은 없는데 어차피 넣는 값은 여기서는 피봇보다 큰 값일테니까

                        //비교에서 제외하는거임..위에는 어차피 넣는 값이 피봇보다 작은 값일테니까..

                    }

                }

                //이떄는 1차적 퀵 정렬이 종료되고 좌우로 분할이 되는 과정이다.

                value[iLower] = iPivot;

                ShowSortResult(value);

                //iLower와 iHigher가 만났을때 종료가 된다.

                QuickSort(value, iFirst, iLower - iFirst);

                QuickSort(value, iLower + 1, iLast - iLower);

            }

        }

        public void ShowSortResult(int [] value)

        {

            foreach(int iValue in value)

            {

                Console.Write("{0} ", iValue);

            }

            Console.WriteLine(" ");

        }

        static void Main(string[] args)

        {

            int[] value = { 80, 50, 70, 10, 60, 20, 40, 30 };

            Program test = new Program();

            test.QuickSort(value, 0, 8);

        }

    }

}