25.02.05(수) - 본 캠프 TIL 13일차 (Today I Learned)

static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i]; arr[i] = arr[j];
    arr[j] = arr[j];
    arr[j] = temp;
} // 공간을 하나 더놓고 삼각형으로 정보 교환을한다

 

퀵 정렬 ( Quick Sort )

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

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

- arr.Length → 배열 요소 개수
- arr.Length - 1 → 배열의 마지막 인덱스
- QuickSort(arr, 0, arr.Length - 1) → 배열 전체를 정렬

 

arr.Length - 1 이 항상 배열 전체를 정렬 하는건 아니다

 

int[] arr = { 10, 20, 30, 40, 50 };

Console.WriteLine(arr[arr.Length - 1]); // 마지막 요소 출력

-  arr.Length - 1은 마지막 요소(50)를 가져오는 용도
- 정렬과는 관련 없음

 

static int Partition(int[] arr, int left, int right) // 배열중 left는 왼쪽끝의 인덱스번호 0 이며 right 는 마지막 번호 인덱스 5이다
{ // { 5, 2, 4, 6, 1, 3 }; 예시 배열들
    int pivot = arr[right]; // right = 3
    int i = left - 1; // left = 0 - 1 = - 1

    for (int j = left; j < right; j++) // 0번부터 5번자리가 오기전 즉 4번위치까지 비교
    {
        if (arr[j] < pivot) // pivot = 3 이 j 보다 작으면 i를 증가시켜라 > 5, 2, 4, 6, 1, 3 > 2,5,4,6,1,3(Swap) > 2,1,4,6,5,3(Swap) 반복끝
        { // Swap 이발생하면 j 의 위치는 Swap 이 발생한 그위치에서 재 비교
            i++; 
            Swap(arr, i, j);
        }
    }
    Swap(arr, i + 1, right);
    // 반복문이 종료시 i + 1을 해라(i는 -1 이였지만 스왑을 2번진행(i++로 인해 2증가 = 1), +1을 하면 2, 즉 2번자리 인덱스(4)와right 3의 자리를 바꿔라)
    return i + 1; // 그럼 2,1,3,6,5,4 , pivot 으로 기준은 잡은수 3을 기준으로 왼쪽은 기준보다 낮은수 오른쪽은 큰수로 빠르게 정렬 이게 파티션
}

 

C# Sort  // .Sort 메서드를 이용하여 정렬을 할수도 있다

int[] numbers = { 5, 2, 8, 3, 1, 9, 4, 6, 7 };

Array.Sort(numbers);

Console.WriteLine(string.Join(", ", numbers));

 

List<string> names = new List<string> { "John", "Alice", "Bob", "Eve", "David" };

names.Sort();

Console.WriteLine(string.Join(", ", names));

 

그래프 이해도 - 각 Vertex 숫자끼리 연결 되어있음