08/10

퀵 정렬

• 분할 합병 방식을 이용하여 정렬을 수행하는 방식이다.
• 기준값을 설정하여 이 값을 기준으로 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 옮기는 방식으로 정려를 진행한다. (오름차순 기준)
• 반복하여 분할된 배열의 크기가 1이 되면 배열이 모두 정렬된 것이다.

기본 로직

1. 기준 배열 값을 정한다. 맨 앞이나 맨 뒤 또는 중간값이나 랜덤 위치로 정한다.

2. 분할을 진행하기에 앞서 비교를 진행하기 위해 가장 왼쪽의 배열 인덱스를 저장하는 변수와 가장 오른쪽의 배열을 저장하는 변수를 생성한다.

3. 오른쪽 인덱스 값 비교를 진행한다. 비교는 오른쪽 인덱스가 왼쪽 인덱스보다 클 경우만 비교한다. 비교한 값이 기준값보다 크면 오른쪽 인덱스를 감소시키고 비교를 반복한다. 기준값보다 작은 배열값을 찾으면 반복을 중지한다.

4. 왼쪽 인덱스 값 비교를 진행한다. 오른쪽 인덱스가 왼쪽 인덱스보다 클 경우에만 비교한다. 비교한 값이 기준 값보다 작으면 왼족 인덱스를 하나 증가시키고 반복한다. 기준 값보다 큰 배열 값을 찾으면 반복을 중지한다.

5. 왼쪽 인덱스 값과 오른쪽 인덱스 값을 바꿔준다.

6. 3, 4, 5번 과정을 왼쪽 인덱스가 오른쪽 인덱스보다 작을 때까지 반복한다.

7. 위 과정이 끝나면 왼쪽 변수와 기준값을 바꿔준다.

8. 맨 왼쪽부터 왼쪽 변수 -1까지, 왼쪽변수 + 1부터 맨 오른쪽까지로 나눠 퀵 정렬을 반복한다.

#region [퀵 정렬 내 코드]
public static void QuickSort(int?[] numbers, int?[] result = default(int?[]), bool ascending = true)
{
	if(result == default(int?[]))
	{
		result = new int?[numbers.Length];
    }

    int standIdx, leftIdx, rightIdx;

    // leftIdx와 rightIdx가 만날 때까지 숫자를 바꿔가며 반복
    SwapUntilBlock(numbers, result, out leftIdx, out rightIdx, out standIdx, ascending);

    // 만나면 leftIdx 의 값과 standIdx 의 값을 변경
    Swap(numbers, leftIdx, standIdx);
	SetResult(numbers, result, leftIdx, (int)numbers[leftIdx]);

	bool isEnd = true;
	foreach (int? item in result)
	{
		if(item == null)
		{
			isEnd = false;
		}
	}

	if(isEnd == false)
	{
        QuickSort(numbers, result, ascending);
    }
}

static void SwapUntilBlock(int?[] numbers, int?[] result, out int leftIdx, out int rightIdx, out int standIdx, bool ascending = true)
{
    standIdx = leftIdx = 0;
    rightIdx = numbers.Length - 1;
    while (numbers[standIdx] == null && standIdx < numbers.Length - 1)
    {
        standIdx++;
    }
    while (numbers[leftIdx] == null && leftIdx < numbers.Length - 1)
    {
        leftIdx++;
    }
    while (numbers[rightIdx] == null && rightIdx > 0)
    {
        rightIdx--;
    }

    if(ascending == true)
	{
        while (numbers[rightIdx] == null || (numbers[standIdx] <= numbers[rightIdx] && rightIdx > leftIdx))
        {
            rightIdx--;
        }

        while (numbers[leftIdx] == null || (numbers[standIdx] >= numbers[leftIdx] && rightIdx > leftIdx))
        {
            leftIdx++;
        }
    }
	else
	{
        while (numbers[rightIdx] == null || (numbers[standIdx] >= numbers[rightIdx] && rightIdx > leftIdx))
        {
            rightIdx--;
        }

        while (numbers[leftIdx] == null || (numbers[standIdx] <= numbers[leftIdx] && rightIdx > leftIdx))
        {
            leftIdx++;
        }
    }

    if (leftIdx < rightIdx)
    {
        Swap(numbers, leftIdx, rightIdx);
        SwapUntilBlock(numbers, result, out leftIdx, out rightIdx, out standIdx, ascending);
    }
}

static void Swap(int?[] list, int idx1, int idx2)
{
    int? tmp = list[idx1];
    list[idx1] = list[idx2];
    list[idx2] = tmp;
}

static void SetResult(int?[] numbers, int?[] result, int idx, int value)
{
	result[idx] = value;
	numbers[idx] = null;

}
#endregion [퀵 정렬 내 코드]

#region [퀵 정렬 챗 GTP 코드]
public static void GPT_QuickSort(int[] arr, int low, int high, bool flag = true)
{
    if (low < high)
    {
        int pivotIndex = Partition(arr, low, high, flag);

        GPT_QuickSort(arr, low, pivotIndex - 1, flag);
        GPT_QuickSort(arr, pivotIndex + 1, high, flag);
    }
}

static int Partition(int[] arr, int low, int high, bool flag = true)
{
    int pivot = arr[high];
    int i = low - 1;

    if (flag == true)
    {
        for (int j = low; j < high; j++)
        {
            if (arr[j] < pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }
    }
    else
    {
        for (int j = low; j < high; j++)
        {
            if (arr[j] > pivot)
            {
                i++;
                Swap(arr, i, j);
            }
        }
    }

    Swap(arr, i + 1, high);
    return i + 1;
}

static void Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
#endregion [퀵 정렬 챗 GTP 코드]

static void Main(string[] args)
{
	string output;

	int[] values = { 35, 96, 1, 77, 305, 27, 5, 100, 3 };
	Console.WriteLine("====== 숫자들 ======");
	output = string.Empty;
	int count = values.Length;
	for (int i = 0; i < count; i++)
	{
		output += values[i] + ", ";
	}
	Console.WriteLine(output.TrimEnd(' ').TrimEnd(','));

  	#region [퀵 정렬]
    int?[] result;

    Console.WriteLine("====== 오름차순 ======");
    int?[] values2 = new int?[values.Length];
    Array.ConvertAll(values, item => (int?)item).CopyTo(values2, 0);
    result = new int?[values2.Length];
    SortClass.QuickSort(values2, result);
    output = string.Empty;
    int ascendCount = result.Length;
    for (int i = 0; i < ascendCount; i++)
    {
        output += result[i] + ", ";
    }
    Console.WriteLine(output.TrimEnd(' ').TrimEnd(','));

    Console.WriteLine("====== 내림차순 ======");
    int?[] values3 = new int?[values.Length]; ;
    Array.ConvertAll(values, item => (int?)item).CopyTo(values3, 0);
    result = new int?[values.Length];
    SortClass.QuickSort(values3, result, false);
    output = string.Empty;
    int descendCount = result.Length;
    for (int i = 0; i < descendCount; i++)
    {
        output += result[i] + ", ";
    }
    Console.WriteLine(output.TrimEnd(' ').TrimEnd(','));
    #endregion [퀵 정렬]

    Console.ReadKey();
}