[C#] Lec 13 - 정렬

기초 자료 구조

배열의 기본 연산

• 대부분의 자료 구조는 네 가지 기본 동작 원래 가지며 이를 연산이라고 함
• 읽기 : 자료 구조 내 특정 위치를 찾는 것
• 검색 : 자료 구조 내 특정 값을 찾는 것
• 삽입 : 자료 구조 내 새로운 값을 추가하는 것
• 삭제 : 자료 구조 내에 특정 값을 제거하는 것
• 읽기 : Array[n] 접근하려면, (총 한 단계)
  1. 배열의 인덱스는 0부터 시작. Array[0]의 메모리 주소 get
  2. Array[0]의 메모리주소 + n 으로 이동.
• 검색 : “melon” 접근하려면, (최대 n단계)
  1. Array[0] 인덱스로 검색 → “apple”이므로 다음
  2. [1], [2], [3] 이동하며 확인
• 삽입 : “potato” 삽입하기 위해 (최대 n+1단계 필요)
  1. 추가 메모리 1개 할당
  2. 삽입할 index 뒤의 값들을 한칸씩 뒤로 옮김
  3. “potato”를 그 자리에 삽입
• 삭제 : “tomato” 삭제 하기 위해 (최대 n단계)
  1. “tomato”를 메모리에서 삭제
  2. 빈 공간 뒤쪽 값들을 한칸씩 앞으로 옮김
  3. 마지막에 빈 공간 할당 해제

정렬된 배열에서의 과정

• 검색 : 선형 검색 → 최대 N단계 / 이진 검색 → 최대 log_2 N 단계
• 삽입 : N단계

빅 오 표기법

• O(1) : 데이터가 아무리 많아도 단계 수가 상수로 유지
• O(N) 보다 O(1)알고리즘의 연산이 더 많을 수는 있으나, 특정 데이터 수부터 반드시 O(1)이 효율적인 점이 존재
• 선형검색 : O(N), but 최선의 시나리오 - O(1), 최악의 시나리오 : O(N)
• 최악의 시나리오에 알고리즘이 얼마나 비효율적인지 아는것이 중요
• O(log N) : 이진 검색 알고리즘.

정렬

버블, 선택, 삽입 정렬

using System;

namespace ConsoleApp2
{

    class Program
    {
        public static void Main(string[] args)
        {
            SortableArray a = new SortableArray(new int[] { 9, 32, 4, 6, 7, 1, 5 });
            Console.WriteLine(a);
            a.BubbleSort();
            Console.WriteLine(a);
        }
    }
    public class SortableArray
    {
        private int[] array;
        public SortableArray(int a )
        {
            array = new int[a];
        }
        public int this[int index]
        {
            get { return array[index]; }
            set
            {
                if(index > array.Length-1)
                {
                    throw new ArgumentOutOfRangeException();
                }
                array[index] = value;
            }
        }
        public int Length
        {
            get { return array.Length; }
        }
        public SortableArray (SortableArray arr)
        {
            array = new int[arr.Length];
            for (int i=0;i<arr.Length;i++)
            {
                array[i] = arr[i];
            }
        }
        public SortableArray(int[] arr)
        {
            array = new int[arr.Length];
            for (int i = 0;i<arr.Length;i++)
            {
                array[i] = arr[i];
            }
        }
        public override string ToString()
        {
            string s = "";
            foreach (var i in array)
            {
                s += i;
                s += " ";
            }
            return s;
        }
        public void BubbleSort()
        {
            for (int i = 0;i<this.Length-1;i++ )
            {
                for (int j = 0; j<this.Length-(i+1);j++)
                {
                    if (array[j]>array[j+1])
                    {
                        int tmp = array[j + 1];
                        array[j + 1] = array[j];
                        array[j] = tmp;
                    }
                }
            }
        }
        public void SelectionSort()
        {
            for (int i = 0;i<this.Length;i++)
            {
                int lowestNumIndex = i;
                for (int j = i+1; j<this.Length;j++)
                {
                    if (array[j] < array[lowestNumIndex])
                    {
                        lowestNumIndex = j;
                    }
                }
                if (lowestNumIndex!= i)
                {
                    int temp = array[i];
                    array[i] = array[lowestNumIndex];
                    array[lowestNumIndex] = temp;
                }
            }
        }
        public void InsertionSort()
        {
            for (int i = 1; i<array.Length;i++)
            {
                int position = i;
                int tempValue = array[i];
                while(position>0 && array[position-1]>tempValue)
                {
                    array[position] = array[position - 1];
                    position--;
                }
                array[position] = tempValue;
            }
        }
    }
}

• 퀵 정렬

using System;

namespace ConsoleApp2
{

    class Program
    {
        public static void Main(string[] args)
        {
        }
    }
    public class SortableArray
    {
        private int[] array;
        public SortableArray(int a )
        {
            array = new int[a];
        }
        public int this[int index]
        {
            get { return array[index]; }
            set
            {
                if(index > array.Length-1)
                {
                    throw new ArgumentOutOfRangeException();
                }
                array[index] = value;
            }
        }
        public int Length
        {
            get { return array.Length; }
        }
        public SortableArray (SortableArray arr)
        {
            array = new int[arr.Length];
            for (int i=0;i<arr.Length;i++)
            {
                array[i] = arr[i];
            }
        }
        public SortableArray(int[] arr)
        {
            array = new int[arr.Length];
            for (int i = 0;i<arr.Length;i++)
            {
                array[i] = arr[i];
            }
        }
        public override string ToString()
        {
            string s = "";
            foreach (var i in array)
            {
                s += i;
                s += " ";
            }
            return s;
        }
        public int Partition(int leftIndex, int rightIndex)
        {
            int pivotPos = rightIndex;
            int pivot = array[pivotPos];
            int rightPointer = rightIndex - 1;
            int leftPointer = leftIndex;
            while(true)
            {
                while (array[leftPointer] < pivot)
                    leftPointer++;
                while (array[rightPointer] > pivot)
                    rightPointer--;
                if (leftPointer >= rightPointer)
                    break;
                else
                {
                    Swap(leftPointer, rightPointer);
                }
                Swap(leftPointer, rightPointer);

            }
            return leftPointer;
        }
        public void Swap(int idx1, int idx2)
        {
            int tmp = array[idx1];
            array[idx1] = array[idx2];
            array[idx2] = tmp;
        }
        public void QuickSort(int leftIndex, int rightIndex)
        {
            if (rightIndex-leftIndex<=0)
            {
                return;
            }
            int pivotPos = Partition(leftIndex, rightIndex);
            QuickSort(leftIndex, pivotPos - 1);
            QuickSort(pivotPos + 1, rightIndex);
        }
    }
}

버블 정렬 :

1. 0th, 1st index 읽기
2. 우측이 더 작으면 교환
3. 1st, 2nd 읽기 …
4. 패스 스루 (1st 2nd 읽기 …)
   • O (N^2)
   • 이중 for, i=0~n-1, j=0~n-i-1

선택 정렬 :

1. 0th 1st 순차적 확인, 최솟값과 그 인덱스 저장
2. 최솟값과 0th 교환
3. 패스 스루 (1st) 부터 반복)
   • O(N^2)이지만 버블 정렬보다는 2배가량 빠름
   • 교환 연산이 패스 스루당 한번씩 수행
   • 이중 for, i=0~n, j=i+1~n

삽입 정렬 :

1. 1st를 따로 저장해둠
2. 1st보다 index 값과 비교해 작으면 그 작은 index를 공백에 shift
3. 따로 저장해둔 값을 생긴 공백에 채움
4. 0th까지 갔는데도 작지 않으면 원래자리에 돌려놓기
5. 패스 스루 (2nd 읽기 ..)
   • O(N^2)이지만 실제로는 N^2+2N-2번 일어남
   • 이미 정렬된 행렬은 삽입정렬 사용하는것이 효율적

퀵 정렬

1. 왼쪽 포인터를 배열의 가장 왼쪽, 오른쪽 포인터를 배열의 가장 오른쪽-1에 놓음 (맨 오른쪽 숫자 : pivot)
2. while () 왼쪽포인터의 index 값과 피벗값 비교, 피벗보다 더 작으면 이동, 크거나 같으면 멈춤
3. while() 오른쪽 포인터의 index 값과 피벗 값 비교, 피벗보다 더 크면 이동, 작거나 같으면 멈춤
4. 왼쪽 포인터의 index가 오른쪽 포인터의 index보다 크거나같으면 정렬 멈춤
5. 왼쪽 포인터가 현재 가리키고 있는 값을 피벗과 교환
6. 새로 구해진 피벗값을 기준으로 좌우 분할, (leftIndex, pivotPos-1) , (pivotPos+1, rightIndex) 왜냐면 pivotPos는 이미 그 위치가 결정되었기 때문.
7. 패스 스루 (재귀적으로)

정렬 별 효율성 (빅 오)

• 삽입, 선택 정렬은 최선, 평균, 최악의 경우 모두 O(N^2)
• 퀵 정렬은 최선, 평균의 경우 O(NlogN), 최악의 경우 O(N^2)