[내배캠] 본캠 17일차. 알고리즘, 정렬알고리즘, 선형 탐색알고리즘

알고리즘이란?

알고리즘: 문제를 해결하기위한 명확한 절차나 방법.
알고리즘을 푼다: 입력을 받아 원하는 출력을 생성하기 위한 절차.

문제푸는절차 즉,
예를들면 집에가는방법도 알고리즘이될수있음.
방나간다 -> 엘베탄다 -> 지하철역간다 -> 집앞에서내린다
무엇을, 어떤순서로 얼마나 해야하는지 단계별로 적어놓은것.
근데 효율성을 따진다.
조금이라도 더 빠르고 메모리를 덜 사용하는 방법으로 동작하길 원함.

왜?
입력이 작을때는 느려도 큰 문제가안되지만
입력량이 늘어나면 시간이 엄청 오래걸릴 수 있음
쇼핑목록 1가지 : 1분
쇼핑목록 100가지 : 100분 -> 너무 비효율아닌가?
그래서 알고리즘이 얼마나 빨리 또는 얼마나 작은메모리를 쓰는지 비교하는 방법이 필요함.

여기서 
Big O 표기법이란게 등장.

알고리즘의 효율성을 나타내는 표기법
알고리즘이 얼마나 많은 시간이나 공간을 필요로 하는지 설명
알고리즘의 속도(시간) 또는 메모리 사용량(공간)이 
입력크기(n)에 따라 어떻게 늘어나는지 아주 간단하게 표시하는 방법.


표기법의 예:
O(1) : 상수시간, 입력의 크기에 상관없이 항상 일정한 시간이 걸린다.
비유- 정수 하나를 계산기에서 꺼내 더함.
O(n) : 선형 시간. 입력의 크기n에 비례하여 시간이 걸립니다. 100번 입력 -> 1000번출력처럼
비유 - 학생 명단 n 명에게 한사람씩 과자 나눠주는것
O(n^2) : 제곱에 비례하게 시간이 걸린다. n명이면 nxn 만큼 시간증가
비유 - n명끼리 짝지어 인사시키기 (한사람당 n번 인사)
O(log n) : 로그시간. 입력의 크기의 로그에 비례하여 시간이 걸린다. 입력크기가 커져도 조금씩만
늘어날수있음.
비유- 책을 반으로 계속 나눠가며(이진탐색) 원하는 단어 찾기.

각 표기법의 감을 잡아보자.
o(1) 
똑같이 빠르다.
친구 한명에게만 문자보내기. 친구가 1명이든 100명이든 , 메세지 버튼 한번 누르는것은 똑같음.

o(n)
입력 수 n만큼 시간이 늘어남.
10명에게 이메일 보내면 10번 클릭, 100명에게 보내면 100번클릭

o(n^2)
두겹의 반복
10명 중 누가 누구와 인사를 했는지 기록하려면 10x10(100번) 비교해야함.
100명이되어버리면 10000번 비교해야함.

o(log n)
반으로 쪼개
전화번호부에서 '김'으로 시작하는 이름을 찾으려면 한줄씩 찾는게아니야.
책을 (예를들어 반으로)필요한 영역만큼 나눠가며 찾으면 빠르다.
입력이 1,000쪽이든 1,000,000 쪽이든 반으로 쪼개는 횟수는 크게 늘어나지않음.



빅오 계산법 정리:
1. 상수값 버림. 
상수인 (5, 100)은 무시한다.
2. 최고 차수 항목만 남김
빠르게 늘어나는 (차수가높은) 항만 남기는것.
예) 3n^2 + 5n + 10 -> n^2 부분이 제일 영향이 크니 O(n^2)

3. 다항식의 경우 최고 차수항목만 고려
반복문이 하나면 O(n) 중척(안에 또 반복)이면 O(n^2)~ O(n^3) ...

4. 이진 탐색처럼 반씩 줄이면 O(log n)

결론: 왜 배우는데?
데이터 입력값이 작을땐 상관없지만
수만, 수십만, 수백만 개씩 다룰때는
O(n^2) 알고리즘은 터질만큼 느려지고
O(log n)이나 O(n) 알고리즘은 속도 차이가 하늘과 땅이라고한다.
그래서 코드를 짤때 어떤 방법이 더 빠른지 비교하려고 선택하는것임.


시간복잡도:
시간복잡도란 알고리즘이 문제를 해결하는데 걸리는 시간을 나타내는 척도

예제
int Sum(int n)
{
 int sum = 0;
 for ( int i = 0; i <= n; i++)
{

 sum += i;
}

}

for 루프가 0 부터 n까지 순회하며 합계를 계산한다.
따라서 n+1회의 연산이 필요한데, 상수들을 버리고 따지니 시간복잡도는 O(n)이 된다.
n이 5일때 6번덧셈 -> 6번 연산
n이 10일때 11번 덧셈 -> 11번 연산
거의 n번 연산하므로 O(n)

예제

void PrintPairs(int n)
{

 for( int i = 0; i <= n; i++)
{
 for ( int j = 0; j <= n; j++)
{
 Console.WriteLine( i + ", " + j);
}
}
}

두개의 중첩된 for 루프를 포함한 반복이 있음
전체 연산 횟수는 n^2 이므로 시간복잡도는 O(n^2) 이다.
i 루프가 n+1번
그안의 j루프도 n+1번
총 (n+1) x (n+1) 번 출력
n이 2일때 3x3 = 9번출력
n이 5일때 6x6이면 36번 출력
대략적으로 n제곱에 비례하므로 O(n^2)인것


예제
피보나치

int Fibonacci(int n)
{

  if ( n<=1)
{
 return n;
}
else 
{
 return Fibonacci(n-1) + Fibonacci(n-2);
}

재귀적으로 피보나치 수열을 계산하는 함수다.
이 함수는 각 호출마다 두번의 재귀호출을 수행한다.

F(n)을 부를때마다 F(n-1)과 F(n-2)를 다시 호출한다.
호출 트리를 그려보면 가지가 두개로 계속 갈라져내려간다.

n=1 -> 1번호출

n=2 일때 3번 호출 (F(2), F(1), F(0))

n=3 일때 5번 호출 (F(3), F(2) F(1), F(1), F(0))...
...
이 증가폭은 2^n 과 가깝다.
호출횟수는 입력크기에 따라 지수적으로 늘어나므로 O(2^n) 이다.
실습해보면 n이 30만 되어도, 컴퓨터가 못끝낼 만큼 느려질수있다.

시간 복잡도는 O(2^n)
이는 매우 비효율적인 방법이므로 실제 문제 해결에서는 동적 프로그래밍 등의 
기법을 사용해 효율성을 높이는 것이 중요하다.


공간복잡도:
코드의 메모리 사용량을 실제 메모리 크기로 측정하는것이아니라
입력크기에 따라 필요한 저장 공간의 양을 측정하는 이유를 설명함.

Bio-O 표기법을 사용하여 표시한다.

예제: 최대값을 찾는데 시간복잡도 O(n)인경우
int FindMax(int[] arr)
{
    int max = arr[0];

    for (int i = 1; i < arr.Length; i++)
    {
        if (arr[i] > max)
        {
            max = arr[i];
        }
    }

    return max;
}

예제: 시간복잡도 O(n^2) 인경우 최대값찾기
int FindMax2(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        bool isMax = true;

        for (int j = 0; j < arr.Length; j++)
        {
            if (arr[j] > arr[i])
            {
                isMax = false;
                break;
            }
        }

        if (isMax)
        {
            return arr[i];
        }
    }

    return -1;
}

int[] arr = new int[] { 1, 2, 3, 4, 5 };

//FindMax2 의경우 쭉 순회돌아서  뒤에나오는애가 앞에것보다 크면 break
하고 다시 검사하는데... 그러다 결구 뒤에나오는애가 앞에것보다 클일이없어지면
if문을 통과못하니까 그냥 내부 for문을 다돌고 빠져나오고.. 5를 리턴함. 
처음 정해진것이 무조건 가장 클때 리턴값이 나오는상황. 아니라면 그냥 재검사함.

// FindMax 메서드의 시간 복잡도: O(n), 공간 복잡도: O(1)
int max = FindMax(arr);
추가적인 메모리 공간을 사용안하니까 공간복잡도는 O(1)

// FindMax2 메서드의 시간 복잡도: O(n^2), 공간 복잡도: O(1)
int max2 = FindMax2(arr);
추가적인 메모리 공간을 마찬가지로 사용안하니까 공간복잡도는 O(1)

그다음예제는 조금다르다.
public static int[] RemoveDuplicates(int[] array)
{
    List<int> distinctList = new List<int>();

    foreach (int num in array)
    {
        if (!distinctList.Contains(num))
        {
            distinctList.Add(num);
        }
    }

    return distinctList.ToArray();
}

시간복잡도와 공간복잡도 모두 O(n)이다
배열을 만들고, 배열을 순회하면서 n번만큼 더한다.
그러므로 시간도 O(n)이 되고 
공간자체도 할당하는 값들이 배열의 크기만큼 되므로 O(n)이라고 할 수 있다.


-------

정렬 알고리즘


주어진 데이터가 있을때 데이터 세트를 특정 순서로 배열하는 방법을 제공
(대게 숫자 오름차순, 내림차순, 문자열의 사전식순서)

선택정렬
삽입정렬
퀵정렬
병합정렬

이있는데.

먼저 선택정렬이다

            int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

            for ( int i = 0; i < arr.Length; i++)
            {
                int minIndex = i;
                for(int j = i+1; j < arr.Length; j++) // 비교대상이 자신일필요없으니 i+1
                {
                    if (arr[j] < arr[minIndex])
                    {
                        minIndex = j;
                    }
                }

                int temp = arr[i]; // 이전 인덱스값 임시저장
                arr[i] = arr[minIndex]; // 이전 인덱스에 i+1 부터 순회돌아서 찾은 작은값 저장
                arr[minIndex] = temp; // 해당 작은값이었던 인덱스에 임시저장값 할당
            }

            foreach(int num in arr)
            {
                Console.Write(num);
            }

시뮬레이션 돌려보자.
만일 0번째 값이 5면, 
우선 int minIndex = 0
그리고 이중 for문에서 1번째부터 5번째까지 순회하며
arr[1]< arr[0] 과 비교해보자니
조건식 2 < 5 성립,
minIndex = 1;
arr[2] < arr[1] 과 비교해보자니
조건식 
4 < 2 성립안함
minIndex = 1; 유지
arr[3] < arr[1] 과 비교해보자니
6<2 성립안함
minIndex = 1; 유지
arr[4] < arr[1] 과 비교해보자니
1<2 성립
minIndex = 4;
arr[5] < arr[4] 과 비교해보자니
3< 1 성립안함
minIndex= 4; 유지

int temp = arr[0] // 값 5 할당 , 임시저장
arr[0] = arr[4] // 값 1 할당
arr[4] = temp; // 임시저장한 값 5 할당
이를 통해 한번순회했을때 최소값에 해당했던 인덱스값을 찾아서 첫번째 인덱스값이랑
교환해줘버림.
1,5 값들이 위치 교환되어서
{1,2,4,6,5,3} 
요컨데 우선, 가장 최소값 인덱스를 첫번째 인덱스로 지정해주고
첫번째 인덱스가 가진 값과 비교할때 더 작은 값을 가진 인덱스가 나온다면
그 인덱스를 가장 최소값을 가진 인덱스라고 바꿔준다.
이렇게해서 찾은 가장 최소값을 가진 인덱스를 알고있으니 그 인덱스의 값을
첫번째 인덱스에 할당해주면된다. 그러는과정에서 첫번째 인덱스에 있던 값은
반대로 이전에 최소값을 지녔었던 인덱스위치에 바꿔서 할당해줘버리면
이제 첫번째 인덱스가 가진 값이 최소값이된다.
그리하여 우선 arr[0]번째 값에 가장 최소한 값이 위치해질 수 있었다.

{1 은픽스, 2 , 4 , 6 , 5 ,3} 에서
그다음은 arr[1]에 들어갈 수 있는 최소값을 찾아보자

 다음 외부 for문 순회하여 1번째 인덱스부터 또 찾는다.
int minIndex = 1;
2부터 5번째 인덱스까지 내부 for문으로 검사해보자.
arr[2] < arr[1] 과 비교해보자니
4<2 성립안함
int minIndex = 1; 유지
arr[3] < arr[1] 과 비교해보자니
6< 2 성립안함
int minIndex = 1; 유지
arr[4] < arr[1] 과 비교해보자니
5< 2 성립안함 
int minIndex = 1; 유지
arr[5] < arr[1]과 비교해보자니
3< 2 성립안함.
그렇다면
int temp = arr[1] // 2
arr[1] = arr[1] // 2
arr[1] = 2
그냥 바뀐부분은없다
{1은 픽스, 2도 픽스, 4, 6 ,5 ,3}
다음 한번더 돌아보자 외부 for문이 2번째 인덱스부터 또 찾는다.
int minIndex = 2; // 값은 4
3부터 5까지 인덱스 순회하며

arr[3] < arr[2] 과 비교해보자니
6<4 성립안함
int minIndex = 2; 유지
arr[4] < arr[2] 비교
5< 4 성립안함
int minIndex = 2; 유지
arr[5] <arr[2] 비교해보니
3< 4 성립함
따라서
int minIndex = 5;

int  temp = arr[2] // 4 임시저장
arr[2] = arr[5] // 3 할당
arr[5] = temp; //4 할당
따라서
{1 ,2 ,3 픽스,6,5,4교환}

{1,2,3,6,5,4} 까지왔고
나머지도 전부 순회하면 

결국 모든 인덱스에 최소값이 들어가지면서 순회 횟수가 줄어들며
{1,2,3,4,5,6} 가 된다.

정리하자면,
최소값 인덱스를 임의로 첫번째로 지정하고
다음 인덱스들과 비교하다가 기존 최소값보다 작은 값을 가진 인덱스가
나타나면
해당 인덱스를 최소값인덱스라고 지정한다.
그리고
기존의 최소값인덱스였던 값은 temp에 저장해두고
기존의 첫 최소값인덱스 위치에 발견한 새 최소값인덱스의 값을 넣어준다.
그리고 그 발견한 최소값을 가지고있던 인덱스에는 temp에 저장된 첫번째 인덱스 값을 할당하는
swap 방식으로 가장 최소한 값을 더 앞의 인덱스로 정렬해주고
다음번순회는 그다음 인덱스부터 또 검사해서 같은방식으로 최소값을 검사시작한
첫번째 인덱스값에 할당해주는 방식으로 전체 순회를 돌리는 메커니즘이다.
이렇게 선택정렬에 대해서 공부해봤다.

전체순환을 돌기때문에 성능이 아주 빠르지는 않다.
O(n^2) 의 시간복잡도를 가지고있으며 공간복잡도는 O(1)이다 상수크기의 추가공간이
필요로하진 않는다.



다음은 삽입정렬이다.
삽입 정렬은 정렬되지않은 부분에서 요소를 가져와 정렬된 부분에 적절한
위치에 삽입하는 방법이다.

시간복잡도 : 최악의 경우 O(n^2), 하지만 정렬되어있는 경우에는 O(n)
공간 복잡도 : O(1) 상수크기의 추가공간이 필요없다.

마찬가지로 예제를 보자 
int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

for (int i = 1; i < arr.Length; i++)
{
    int j = i - 1;
    int key = arr[i];

    while (j >= 0 && arr[j] > key)
    {
        arr[j + 1] = arr[j];
        j--;
    }

    arr[j + 1] = key;
}

foreach (int num in arr)
{
    Console.WriteLine(num);
}

마찬가지로
{1,2,3,4,5,6} 으로 정렬된다.
그런데 방식이 좀 다르며 선택정렬보다 좀더 가볍다.
왜냐하면 정렬이 되어있다면 while문이 더 돌지않기 때문이다.

마찬가지로 시뮬레이션을 돌려보자.
{5,2,4,6,1,3} 에서
먼저, i는 1번째 인덱스부터 시작한다.
외부 for문은 1번째부터 ~5번째까지 순회한다.
대신에
int j = 1-1, 즉 0번째 인덱스값을 할당한다. 
int j = 5다.
int key = arr[1] 1번째 인덱스값을 key에 할당한다, for문의 시작값이며, 
int key = 2다.

while( j >= 0 && arr[j] > key) 
0는 0보다 크거나 같다, 그리고 arr[0]인 5는 key값인 2보다 크니까 성립
arr[1] = arr[0] // 5 즉
arr[1]에 5를 할당해줘서
{5,5,4,6,1,3} 인상태,
j -- 증감자를 뒤에 붙여서, 다시 while문을 시작하면
j= -1인상태이고 while 조건식을 성립안하니 빠져나온다

arr[-1 + 1] = key; 여기서 key 값은 2였다.
즉 arr[0] = 2
{2,5,4,6,1,3} 이다.
첫 순회에서 5와 2가 교환된 상태다.
그다음 순회는
i는 2번째 인덱스다.
int j = 2-1 // 1이다. 매번 i번째 인덱스를 돌때 -1 된상태로 j 인덱스가 지정됌
int key = arr[2] // 4다.
여기서 중요한점은 key 값도 매번 검사시작인 i번째 인덱스값으로 갱신된다.
while문 조건대로 우선
1 >= 0이고 arr[1]인 5 > key인 4 도 성립하므로
내부 실행문
arr[2] = arr[1] 로 할당되어 arr[2]는 5다
{2,5,5,6,1,3}
j -- 증감자에의해,
j= 0일때
while 문 조건
0 >=0 성립이고 arr[0]인 2> key인 4를 성립하지 못하니 빠져나와서

arr[0+1] = key 값인 4가된다
따라서
{2,4,5,6,1,3}
key값은 버려지지않고 킵된상태, while 조건문을 거짓으로 깨고 나올때는 어떻게든
j는 i보다 -2인 상태로 나온다. 
while문 안에서는
검사시작한 인덱스값 전단계인 인덱스값에서 +1하므로
해당 검사시작한 인덱스값에 전단계인덱스의 값을 한칸 밀어서 다음 인덱스의 값으로 할당해버리고
-1 감소한 j값에 대해서 다시 검사했을때도 while문을 통과한다면
또다시 이전인덱스값을 다음인덱스값에 할당하는식으로 한칸씩 옆으로 밀어버린다.

조건이틀리는경우
빠져나왔을때
검사 시작한 인덱스값을 감소를 겪은 만큼 줄어든곳에 할당해버려서
더 작은 값이 앞 인덱스번호로 가게된다. 
이전 인덱스 값과 검사시작 인덱스 값을 비교해서 이전 인덱스 값이 더크면
이전인덱스의 값을 검사시작인덱스 값에 넣어주는 메커니즘은 비슷하다.

몇번더 순회를 돌아보면 더 확실히 알수있는데,
{2,4,5,6,1,3}인 상황에서
i는 3번째 인덱스
int j = 2
int key = 6
2 > = 0 , 5> 6 성립안하니까 빠져나와서
arr[3] = 6 

그다음 순회때는
i는 4번째 인덱스
int j = 3
int key = 1
3>=0이고 6> 1 성립하므로
arr[4] = 6
{2,4,5,6,6,3}
2>=0이고 5> 1 성립하므로
arr[3] = 5
{2,4,5,5,6,3}
1>=0 이고 4> 1 성립하므로
arr[2] = 4
{2,4,4,5,6,3}
0>=0이고 2>1 성립하므로
arr[1] = 2
{2,2,4,5,6,3}
-1 >=0 성립안하므로 빠져나와서
arr[-1+1] = 1
{1,2,4,5,6,3}

그다음 순회때는
i는 5번째 인덱스  //값 3
int j = 4
int key = 3
4>=0 이고 6>3 성립하므로
arr[5] = 6
{1,2,4,5,6,6}
3>=0이고 5>3 성립하므로 
arr[4] = 5
{1,2,4,5,5,6}
2>=0이고 4>3 성립하므로
arr[3] = 4
{1,2,4,4,5,6}
1>=0이고 2>3 성립안하므로 빠져나와서
arr[2] = 3이되면서
{1,2,3,4,5,6} 이 된다.

j인덱스는 반대로 줄어들면서 순회하면서, 큰인덱스쪽으로 자신의 값을 복사해주고
그러다가 순회시작한 j값보다 1 위인 인덱스값인 key값보다 작은값을 발견한다면
그 작은값 앞 인덱스에다가 key 값을 넣어준다.
인덱스가 큰 쪽(오른쪽)으로는 큰값들을 밀어주고
key로 지정한값은 그 값보다 작은값의 필터에 걸리면, 그 뒤에(오른쪽)에 넣어주는 모양새다.

조금 어려워서 보완필요하다.
카드를 비교해서 큰애들은 오른쪽으로 한칸씩 미는 상상을해보자.



다음은 퀵정렬이다.
퀵정렬은 피벗을 기준으로 작은 요소들은 왼쪽, 큰요소들은 오른쪽으로 분할하고
이를 재귀적으로 정렬하는 방법.
시간복잡도: 최악의 경우 O(n^2) , 평균적으로는 O(nlogn)
공간복잡도: 평균적으로 O(log n), 최악의 경우 O(n) (재귀호출에 필요한 스택공간)

주어진 예제는 아래와같다.
void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, right);

    return i + 1;
}

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

QuickSort(arr, 0, arr.Length - 1);

foreach (int num in arr)
{
    Console.WriteLine(num);
}


분할정복 전략으로
큰문제(정렬할 전체)를 작은문제(반절로 나눈 그룹정렬)로 나눠서 처리한뒤 합치는 방식이다.
문제는 예제인 코드를 보았을때 한번에 이해가 잘안되었다.

따라서 문제를 제시하고, 해결하기위해 의식의 흐름기법, 즉 절차적인 사고로 풀어보겠다.

우선 우리는
정수배열 arr를 오름차순으로 정렬하는 quick sort 알고리즘을 구현하는게 목적이다.
즉 {5,2,1,4,3,6} 이런식이라면 해당 quick sort 알고리즘에 의해
{1,2,3,4,5,6}으로 만들어줘야한다.

그러니 먼저 정렬할 배열을  만들어보자.
int[ ] arr = new int [ ] { 5,2,4,6,1,3}  

QuckSort(arr, 0 , arrr.Length -1); 이라는 함수를 만들어야 돌아가겠다라고 생각하고
매개변수로 만드배열넣기, 시작인덱스인 0 , 해당 배열의 길이-1 를 인자로받아보게한다.
그럼 뭔가 0번째부터 5번째 인덱스까지 6개의 배열에 대해서 작용할것이라 예측한다.

foreach(int num  in arr)
Console.WriteLine(num); 을 하여서 출력도 준비한다.

QuickSort라는 함수 내부에서 뭔가 인덱스의 위치를 바꿔야 할 필요가있고
swap의 가장 기본적인 원리를 들고와 보자.

static void Swap(int[] arr, int i , int j )
{
 int temp = arr[i];
 arr[i] = arr[j];
 arr[j] = temp;
}
해서 앞의 인덱스 값에 뒤에 인덱스값을 할당,
 뒤의인덱스에는 임시저장한 앞의인덱스값을 할당
하는 기본 swap 함수 제작한다.

그다음엔 퀵정렬의 핵심인 피벗 기준 분할을 담당하는 분할 함수
Partition을 만들어보자. 피벗을 기준으로 분할을 시키는것이 주요 핵심이다.
먼저 개념적으로 약속을 짚고넘어간다.
pivot = 기준이 되는 숫자
퀵정렬에선 보통 편의상 맨 끝 요소를 피벗으로 쓰는데,편의상 한 약속이다.
맨끝 인덱스 값을 피봇으로 정해두면,
분할 루프시에 pivot과 비교할때 pivot을 제외한 바로 전단계 인덱스까지 검사하면되고
따라서 기준점이라는 피봇이 꼭 끝일필요는없이 중간인덱스값이어도 되긴한다.일단은넘어가자
pivot을 기준으로 나머지요소들에대해서
작으면 작은구역, 크거나 같으면 큰구역으로 넣어줄 예정이다.
그리고 마지막으로 피벗을 작은 구역과 큰구역 사이에 딱 넣으면 
피벗 왼쪽으로 모두 더 작고, 피벗 오른쪽으로는 모두 더 크거나 같은 정렬된 형태의 절반이되는것이다.
작은 구역: pivot 인 숫자보다 작은 숫자들이 모이는 자리
i는 작은 구역의 끝 인덱스를 가리킨다. 즉 pivot보다 작은값들이 몰려있는 마지막인덱스라고
지정한다. 
처음엔 작은구역에 뭘 넣은적이없으니 그냥 비어있다는 표시로 0번째 인덱스 -1 이라고 표기해서
배열 바깥으로 내보내버린다.

우리는 pivot에 할당된 값보다 작은 숫자들은 왼쪽에 모아두고싶다.
예를들어 {5,2,4,6,1,3} 에서 pivot이 3이라면
작은 숫자 2, 1만 모아서 
{2,1,...3,...} 의 형태로 만들고싶다.
그래서 그냥 0번째 인덱스를 left라고 편의상 말하고
배열의 끝번째를 right라고 편의상 말하자.

j는 배열을 훑으면서 pivot보다 작은지 검사하는 인덱스다.
어떻게 쓰냐면

if (arr[j] < pivot) 
{
 i ++;
 Swap(arr, i , j ); 
}
앞서서 swap은 i번째에 j번째 값을 할당하고 j번째에 i번째 값을 할당해버리는 함수다.
직역하자면,
j번째 인덱스 값이 pivot 값보다 작다면
i를 1 증가시키고
i에 대해서는 j번째 인덱스값을 넣어주고, j에대해서는 i의 값을 넣어주는것인데,,
바로 숫자값들을 넣어보며 확인해보자
j가 0이라 치자,
5 <3 이면 틀리니 실행을 안한다.
j가 1일때는
2<3 이므로
i++ -> i가 -1 > 0으로 바뀐다.
이제 작은 구역은 인덱스 0하나를 차지할 준비가되었다.
Swap(arr, i , j) 는 Swap(arr, 0 ,1)이므로
교환전인
arr[0] =5 , arr [1] =2
에서
교환후
arr[0] =2 , arr[1]= 5 가된다.
그 결과
arr = { 2, 5, 4, 6,1 3}
작은 구역 인덱스 0 에대해선 2가 값이고
i = 0 인상태
2라는 작은값을 작은 구역 최전선(작은구역의 가장 오른쪽)에 집어넣고 swap을 이용해서
그자리에 있던 값 5는 j위치인 인덱스1의 위치로 밀어낸것이다.
즉 pivot의 값보다 작은 값이 튀어나온다면 해당 값의 인덱스를 확인하고
작은구역의 가장 최전선(오른쪽) 인덱스에 있는 값과 교환해주어서 
pivot보다 작은값이 어떻게든 pivot의 오른쪽에 위치할 수 있는 포석을 깔아주는것이다.
아직 pivot 값자체는 특정 활동을 안했으니 여전히 가장 끝인덱스에 있긴 하지만
추후 정렬이 끝나면 중간에 끼워넣어줄 예정이다. 
i가 작은구역최전선인덱스이니, 그것보다 하나큰 i+1에 pivot 인덱스를 끼워넣어주면
작은 구역 - 피봇 - 큰구역 이런 그림이 나올예정이다.

우선은
작은구역의 최전선 인덱스값은 0이고
j는 1까지 진행된상태,
정렬은
{2,5,4,6,1,3} 인상태

j=2일때는
arr[2] < pivot // 4 <3 조건 만족안함

j=3일때는
arr[3] < pivot // 6 < 3 조건 만족안함

j=4일때
arr[4] < pivot // 1< 3 조건만족하니까
i++ 해줘서 i = 1인상태고,
i인 작은구역은 1인덱스까지 확장된 상태다.
거기서
Swap을 등장시켜서
교환전
arr[1]= 5, arr[4] = 1인상태에서
교환 후 
arr[1] = 1, arr[4] = 5로 교환해준다.

그 결과
arr = [2,1,4,6,5,3]
작은구역 (인덱스 0 1 ) : [ 2, 1]
i= 1 인상태

즉 정리하자면, if(arr[j] < pivot) 이라는 
조건은 pivot보다 작은값들을 작은구역에 넣기위한 조건

i++ 로 작은구역을 인덱스를 1 확장해주고
확장해준 상태의 최전선 인덱스 i와 pivot보다 작은값을 가진 j인덱스의 값 두개를 swap해주면
arr[j]의 작은값이 작은구역의 끝 i 로 옮겨지는 샘이다.

마지막으로 피벗을 작은구역 최전선인 i의 바로 한칸더 칸 i+1 인덱스에 넣어주는 swap을 
시행하면
Swap(arr, i+1, right); 
해주면 앞서말햇듯, 
[2,1,3,6,5,4] 가 된다.
 
이걸 기준으로 Partition함수를 완성시켜보자면

static int Partition(int [] arr, int left, int right)
{
 int pivot = arr[right];
 int i = left -1;

  for (int j = left; j < right; j++) // right인덱스는 pivot자신이니 검사안함
  {
   if ( arr[j] < pivot)
   { 
     i++;
     Swap(arr, i , j); 
   }
  }

Swap(arr, i+1, right); // 피봇 작은구역 바로 오른쪽칸에 끼워넣기
return i+1; // 피봇 최종 인덱스 리턴해준다.
}

이런식으로 파티션을 만든다.

그런데 아직 완전히 오름차순 배열이 된상태는아니다.
단지 하나의 기준값으로 작은 구역과 큰구역이 나눠졌을뿐이다.
[2,1,3,6,5,4] 상태이다.

그렇다면 몇번이고 반복하다보면 정렬이 될수있다.
이 분할을 반복해서 전체를 정렬해줘야하니까
그것을 구현하는 재귀함수 QuickSort를 구현해야한다.
이것은 재귀함수를 이용하는데
자기 자신을 다시 부르는 함수를 재귀함수라고 하며
호출때마다 인자로 다른값을 넘겨서 문제를 점점 작게만들어 나눠처리한다.
끝내야할 조건이 있어야만 무한반복을 막는다.

quicksort 함수 구조를 따져보면

void QuickSort( int [] arr, int left, int right)
{
  if ( left< right)
   {
     int pivotIndex = Partition(arr, left, right);
     QuickSort(arr, left, pivotIndex -1 );
     QuickSort(arr, pivotIndex +1, right); 
   }
}

이런식이다.

left와 right 매개변수 파라매터에 들어가는 인자들은 인덱스지, 값은아니다.
파티션에서도 인덱스였다.

if( left< right)
left == right 이면 구간길이가 1 -> 이미 정렬된 상태
left > right 이면 구간길이가 0 정렬할게 없음.
풀이해보면,
left와 right는 현재 정렬하려는 부분배열의 시작(left)과 끝(right) 인덱스다.
예를 들어 QuickSort(arr, 2, 4) 라면 인덱스 2 ,3 ,4 (3개의 요소)만 보고 정렬하겠다는 뜻이다.
부분 배열의 길이 = right - left + 1이다. 
여기서 left< right의 의미는
일단은 길이가 최소한 2개이상 있다는 뜻이다.
예를들어
2<3 이어도 길이는 2다. 2,3 두개의 인덱스로 구성된 길이 2의 배열이니까..
3-2 +1 해도 된다.
그러니까 left<right 상태라면 두개의 인덱스를 정렬할 가치가 있다고 판단한다
둘중에 하나가 크거나 작다라는 뜻이니까. (물론 같은 값일수도있다.)

left == right는 요소 한개있는 길이 1짜리 배열인상태를 뜻하고
이미 뭐 따질게없는 상태라서 quicksort로 정렬해줄 필요가없다.
left > right라면 
부분배열의 길이가 0보다 작거나같은 빈구간이다. 
마찬가지로 따질게없는 상태다. 비교할 요소가없다.

근데 인자로 들어가는 파라매터의 left는 앞선인덱스, right는 후에올 인덱스로 더 높은수일텐데
left< right 를 따질 필요가 애초에 있나? 라는 의문이 들었다.
그것은 Partition뒤에 리턴된 pivotIndex 가 left와 같을때 
left > right 가 될수있으므로 조건으로 걸어주는게 맞다라는 결론에 다다르는데,
이는 더 전개해가보면서 이해해보자.

일단은 if( left< right) 에서 구간크기가 최소 2이상일때만 (인덱스가 두개이상) 나눠서 정렬하는 조건을
걸었다고 생각하자
내부의 내용을 보면

int pivotIndex = Partition(arr, left, right);

한번 복습하자면 앞서 Partition 함수는 right 인덱스를 피봇삼아, (i) 작은구역을 정렬해주고,
작은구역의 바로 앞단 ( i +1)에 right인덱스인 피봇값을 스왑해서 집어넣어주고
i+1 인덱스를 반환해줬었다.
아까의 배열대로라면 작은구역 i까지 확장된건 arr[1]까지 확장된거고
right였던 arr[5]의 3이 i+1, 즉 arr[2]위치로 가서
[2,1,3,6,5,4] 상태다. 그리고 피봇값을 가르키는 인덱스 2를 리턴했다.

즉 int pivotIndex 에는 피봇이되는 중간 인덱스인 2가 할당되어있다.
int pivotIndex = 2;
Partition 함수가 피벗이되는 값을 기준으로 작은구역을 정렬해주고
피벗을 딱 중앙위치에 놓아준것까지 수행한상태.
값은,
왼쪽에는 모두 피벗값보다 작고, 오른쪽에는 모두 피벗값보다 큰상태

이상태에서
왼쪽부분을 재귀한다.
QuickSort(arr, left, pivotIndex-1);
pivotIndex가 2이므로, left~1까지의 2개의 요소를 정렬해야한다.

아까 QuickSort 함수의 if 조건을 따져보면
0 < 1 조건을 성립하니까
int pivotIndex = Partition( arr, 0, 1) 이되는데,,
[2, 1] 에 대해서 정렬하면, 
right은 1이고....
따라서
int pivot = arr[right] //arr[1]//  1;
int i = arr[0] -1 이니 어김없이 -1 
for ( int j= 0 ; j<right , j ++) 
{
 if ( arr[j] < pivot)
i++;
Swap ( arr, i , j);
 }
을 하면 
arr[0] < arr[1] 
2<1 
는 성립안하기때문에 for문안의 나머지는 계산없이 나온다.
Swap( arr, i+1, right) 을 실행하면
arr[0]과 arr[1]을 바꿔주는데, 
정렬은 [1,2]가되고.. return으로는 i+1인 인덱스 0을 리턴해준다.
재귀함수 내부적으로 pivotIndex 값은 인덱스0이다.
내부적으로 다음 QuickSort를 시행해야하는데,
QuickSort(arr,left,pivotIndex-1) -> QuickSort(arr, 0, 0-1)
으로 들어가면, left< right 를 성립안하니까 그냥 빠져나온다.
QuickSort(arr, pivotIndex+1, right) -> QuickSort(arr, 1, 0) 
으로 들어가도 left< right를 성립안하니까 그냥 빠져나온다. 
그렇게 왼쪽부분 재귀하는 실행문은 모든 역할을 마치고 빠져나와진다.

그다음엔 
오른쪽부분도 재귀해주는데
QuickSort(arr, pivotIndex+1, right);
앞서서 처음에 Partition함수 실행을 통해 얻은 pivotIndex가 2였으니 
3번째 그러니까 피벗 바로 오른쪽칸을 시작으로 오른쪽구간 끝 right까지 quicksort를 진행하는데
[6,5,4] 에 대해서 진행하는것이다.
여기서도 같은 매커니즘을 통해
[4,5,6]이라는 값을 얻고 오른쪽 재귀실행문도 빠져나올것이다.

여기서 재귀함수를 탈출하는 조건은 left<right가 거짓이 되는 순간이라는 점을 알 수 있다.

순서대로, Swap 기본 함수,
Partition이라는 pivot값을 리턴해주고, 그 앞의 내용들을 정렬해주는 함수

그리고 그것을 재귀호출로 계속해서 피벗 기준 앞과 뒤를 더 정렬해주는 함수

이렇게 세개의 함수를 통해
배열을 오름차순으로 정렬을 가능하게 한다.

void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);

        QuickSort(arr, left, pivot - 1);
        QuickSort(arr, pivot + 1, right);
    }
}

int Partition(int[] arr, int left, int right)
{
    int pivot = arr[right];
    int i = left - 1;

    for (int j = left; j < right; j++)
    {
        if (arr[j] < pivot)
        {
            i++;
            Swap(arr, i, j);
        }
    }

    Swap(arr, i + 1, right);

    return i + 1;
}

void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };

QuickSort(arr, 0, arr.Length - 1); // 해당함수에 배열의 시작과 끝 인덱스를 넣어준다고 생각

foreach (int num in arr)
{
    Console.Write(num);
}

// 출력 123456

시간복잡도는 최악의경우 O(n^2) 평균적으로는 O(n log n)
공간 복잡도는 평균적으로 O(log n) 최악의 경우 O(n) 



다음은 병합정렬이다.
비슷한 느낌이지만 더 뜯어서 정렬하는 느낌이다.
시간복잡도는 모든 경우에 대해 O(n log n)
공간 복잡도는 O(n) 이 된다.

....
C#에서는 이미 Sort라는 메서드를 던져주니 실제로 이상태로 구현할일은 드물다.
Sort 메서드는 배열이나 리스트의 요소들을 정렬하는  메서드로
정렬은 오름차순으로 수행되며, 요소들의 자료형에 따라 다양한 정렬기준을 사용할 수 있습니다.
Sort 메서드는 원래의 배열이나 리스트를 직접 수정하므로 반환값이 없다.

// 정수 배열 정렬 예제
int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };
Array.Sort(numbers); // Array라는 class 에 sort를 요청해야함.
Console.WriteLine(string.Join(", ", numbers));

// 문자열 리스트 정렬 예제
List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };
names.Sort(); // List는 내부에 이미 준비되어있음.
Console.WriteLine(string.Join(", ", names));

String.Join은 Split으로 내용들을 나눠주는것과 비슷한원리로 연결해주는데,
앞의 인자를 기준으로 뒤의 인자들을 나열해준다.
Console.WriteLine(string.Join("," , numbers)) 라면 
1, 2, 3, 4, 5, 6, 7, 8 이런식으로 출력가능하다.

내림차순을 요구하려면 
Array.Reverse라는 메서드에 다시 한번 Sort한 매개변수에 넣어서 만들수있다.

Array.Sort(arr);
Array.Reverse(arr); 를 순차적으로 실행하면된다.

List에도 해당 메서드는 똑같이 존재하는데....
LINQ를 이용할수도있긴하다.

var desc = list.OrderByDescending(x => x).ToList();


정렬알고리즘은 이정도로 마치고
---------

탐색알고리즘이다.

탐색알고리즘은 주어진 데이터 집합에서 특정 항목을 찾는 방법을 제공한다.
여기서는 가장 일반적인 탐색 알고리즘을 몇가지 살펴본다.

1. 선형탐색
선형탐색이 가장 단순한 탐색 알고리즘이다. 배열의 각 요소를 하나씩 차례대로 검사하여
원하는 항목을 찾는다.
시간 복잡도: 최악의 경우 O(n)

예제
int SequentialSearch(int[] arr, int target)
{
    for (int i = 0; i < arr.Length; i++)
    {
        if (arr[i] == target)
        {
            return i;
        }
    }

    return -1;
}


2. 이진탐색
정렬이 된 배열에서 빠르게 원하는 항목을 찾는 방법이다.
중간값을 찾고, 찾고자하는 값이 중간값과 비교하여 작은경우 왼쪽을, 큰경우 오른쪽을
탐색한다.

int BinarySearch(int[] arr, int target)
{
    int left = 0;
    int right = arr.Length - 1;

    while (left <= right) // 탐색영역이 존재할때,
    {
        int mid = (left + right) / 2;

        if (arr[mid] == target) // 딱 중간값이 타깃이라면 중간값을 반환한다.
        {
            return mid;
        }
        else if (arr[mid] < target) // 중간값보다 타깃이 크다면, 탐색의 스타트지점을 중간기준 한칸 늘린다.
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1; // 중간값보다 타깃이 작다면, 탐색의 엔드지점을 중간기준 한칸 줄여준다.
        }
    }

    return -1;
}

중간기준으로 지점을 늘리고 줄이는 모든행위가 탐색영역을 줄여준다.

선형적인것에대해선 이렇게 가능하다.

3. 그래프에서는 또 좀 다르다.
그래프란
정점(vertex)와 간선(edge)로 이루어진 자료구조 , A ---- B 여기서 점은 A,B 간선은 ----
방향 그래프와 무방향 그래프로나뉜다.  방향그래프는 ---> 이렇게 화살표가 존재하고
이쪽방향으로만 갈수있음, 무방향은 ------, 양쪽다 왔다갔다할수있음.
가중치 그래프는 간선에 가중치가 있다.
비유하자면 도로마다 거라(km)나 통행료(cost)를 표시한것

A ---5 ----B 라 하면 A<--->B 사이의 거리가 5
방향 가중치 그래프라면
A-->B(5), B-->A(7) 처럼 서로 다른 값도 가능하다.



그래프 탐색방법에는
3-1 깊이우선탐색 DFS
루트에서 시작해서 가능한 깊이 들어가서 노드를 탐색하고 더이상 방문할 노드가없으면
이전 노드로 돌아가는 방식이다.
3-2 너비우선탐색 BFS 
루트에서 시작하여 가까운 노드부터 방문하고 그 다음 레벨의 노드를 방문하는 방식이다.

두가지 탐색방법이 위와 같이 존재한다.