Study : Quick Sort

<퀵 정렬>

  :: 간략 정보

    - 가장 빠른 정렬 알고리즘

    - 자기 자신을 불러 쪼개서 정렬을 함

    - 수학적으로 이해해야 해서 더럽게 어려움

  :: 구조

    - 완벽하게 이해 못해서 못쓰겠음

 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Study33_QuickSort
{
    public class App
    {
        public App()
        {
            // :: Testing Value
            int[] arr = new int[10] { 4, 8, 7, 6, 9, 1, 3, 2, 0, 5 };
            this.ShowArray(arr);

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

            this.ShowArray(arr);

        }

        public void QuickSort(int[] arr, int indexStart, int indexEnd)
        {
            // :: Null Break;
            if (indexStart >= arr.Length)
                return;

            int target = arr[indexStart];
            int left = indexStart + 1;
            int right = indexEnd;

            while(left <= right)
            {
                // :: When target is bigger than Left Value : Skip
                while(arr[left] < target)
                {
                    left += 1;

                    // :: Null Break;
                    if (left >= arr.Length)
                        break;
                }
                // :: When target is smaller than Right Value : Skip
                while (arr[right] > target)
                {
                    right -= 1;

                    // :: Null Break;
                    if (right < 0)
                        break;
                }

                // :: I didn't understand this yet.
                if(left <= right)
                {
                    SwapArray(arr, left, right);
                }
            }            

            // :: I didn't understand this yet.
            // :: Until Start index is same End index : It means dividing is one now.
            if(indexStart < indexEnd)
            {
                // :: Swap target and Right Value
                SwapArray(arr, indexStart, right);

                QuickSort(arr, indexStart, right - 1); // :: Front
                QuickSort(arr, right + 1, indexEnd); // :: End
            }

            return;
        }

        public void SwapArray(int[] arr, int a, int b)
        {
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }

        public void ShowArray(int[] arr)
        {
            foreach(var itm in arr)
            {
                Console.Write("[{0}]", itm);
            }
            Console.WriteLine("");
        }

        public void Today()
        {
            DateTime today = new DateTime(2020, 10, 26);
            Console.WriteLine(today.ToString("yyyy-MM-dd") + " : THINK");
        }
    }
}

 

글 업데이트 : 2020-10-26

 

참고 사이트 :

blockdmask.tistory.com/177