[c#] 선택 정렬, 퀵 정렬, 버블 정렬, 병합 정렬 구현하기

선택 정렬

재귀함수를 이용해서 앞에서 부터 하나씩 비교하면서 가장 작은 수를 찾고 바꿔주는 형식

	public int[] solution_selectSort(int[] numbers)
        {
            solution_selectSort(numbers, 0);
            return numbers;
        }

        public void solution_selectSort(int[] numbers, int startIndex)
        {
            if (startIndex >= numbers.Length) return;

            // 가장 작은 수 찾기
            var minIndex = startIndex;
            for (int i = startIndex + 1; i < numbers.Length; i++)
            {
                if (numbers[minIndex] > numbers[i])
                {
                    minIndex = i;
                }
            }

            // 가장 작은 수와 바꿔줌.
            int temp = numbers[startIndex];
            numbers[startIndex] = numbers[minIndex];
            numbers[minIndex] = temp;

            // 다음 위치에서 정렬을 위해 재귀함수
            solution_selectSort(numbers, startIndex + 1);
        }

 

퀵정렬

가운데 인덱스를 기준으로 잡고 기준보다 작으면 기준보다 앞으로 크면 뒤로 스왑.

기준으로 나눈 그룹안에서 다시 재귀 함수로 가운데 인덱스로 기준을 잡고 정렬하는 방법

 

        public void quickSort(int[] numbers)
        {
            quickSort(numbers, 0, numbers.Length-1);
        }

        public void quickSort(int[] numbers, int start, int end)
        {
            int part2 = partition(numbers, start, end);
            if( start < part2-1)
            {
                quickSort(numbers, 0, part2-1);
            }
            if (part2 < end)
            {
                quickSort(numbers, part2, end);
            }
        }

        public int partition(int[] numbers, int start, int end)
        {
            int pivot = numbers[(start + end) / 2];
            while(start <= end)
            {
                while (pivot > numbers[start]) start++;
                while (pivot < numbers[end]) end--;

                if(start <= end)
                {
                    int temp = numbers[start];
                    numbers[start] = numbers[end];
                    numbers[end] = temp;

                    start++;
                    end--;
                }
            }
            return start;
        }

 

 

버블 정렬

앞에서 부터 바로 뒤에 있는 것과 비교해서 정렬하는 방법.

한번 정렬되면 마지막에 있는것만 정렬되므로 다시 앞에서 부터 마지막 정렬된것 바로 앞까지 다시 정렬하는 방법

한번 정렬 될때 마다 끝자리 수가 하나씩 정렬 되는 방식이다.

 

 

       public void bubbleSort(int[] numbers, int last)
        {
            for (int i = 0; i < last; i++)
            {
                if (numbers[i] > numbers[i+1])
                {
                    int temp = numbers[i];
                    numbers[i] = numbers[i+1];
                    numbers[i+1] = temp;
                }
            }

            if (last > 1)
            {
                bubbleSort(numbers, last - 1);
            }
        }

      

병합 정렬

퀵정렬과 비슷한 형태로 피벗을 정해서 나눈 후 두 배열중 가장 작은 수를 찾아서 앞에 채워넣는 형식

메모리가 따로 필요하므로 메모리를 따로 넣지 못하는 경우는 퀵정렬로 사용

 

        public void mergeSort(int[] numbers, int[] temp, int start, int end)
        {
            if (start >= end) return;
            int mid = (start + end) / 2;

            mergeSort(numbers, temp, start, mid);
            mergeSort(numbers, temp, mid+1, end);

            merge(numbers, temp, start, end, mid);
        }

        public void merge(int[] numbers, int[] temp, int start, int end, int mid)
        {
            for(int i = 0; i < numbers.Length; i++)
            {
                temp[i] = numbers[i];
            }

            int index1 = start;
            int index2 = mid + 1;

            int index = start;

            while(index1 <= mid && index2 <= end)
            {
                if (temp[index1] <= temp[index2])
                {
                    numbers[index] = temp[index1];
                    index1++;
                }
                else
                {
                    numbers[index] = temp[index2];
                    index2++;
                }
                index++;
            }

            for(int i = 0; i <= mid - index1; i++)
            {
                numbers[index + i] = temp[index1 + i];
            }
        }