2020.09.02 - 삽입 정렬(insertion Sort), 퀵 정렬(Quick Sort)

* 삽입 정렬 

 : 각 숫자를 적절한 위치에 삽입하는 방식이다. 다른 정렬 방식들은 무조건 위치를 바꾸지만 삽입 정렬은 '필요할 때만' 위치를 바꾸게 된다.

 

O(n^2) 이지만 선택, 버블 정렬에 비해 속도가 빠르다.

삽입 정렬은 기본적으로 왼쪽에 값들이 '정렬되어 있다는 가정'을 한다. 특정한 경우에 따라 매우 빠를 수도 있다. 

왼쪽의 숫자와 비교하여 더 작은 값을 앞으로 배치한다.

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

namespace Insertaion_Sort
{
    class Program
    {
        static void Main(string[] args)
        {
            int temp;
            int j;
            int[] array = new int[] { 10, 3, 4, 1, 2, 6, 8, 7, 9, 5 };

            for (int i = 0; i < array.Length; i++)
            {
                j = i;
                while (array[j] > array[j+1])
                {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    j--;
                }
            }

            foreach (var item in array)
            {
                Console.WriteLine(item);
            }
        }
    }
}

 

- 결과

배열이 거의 정렬된 상태라면 삽입 정렬이 가장 빠를 수 있다.

 

 

* 퀵 정렬(Quick Sort)

: 가장 빠른 정렬 알고리즘이다. 대표적인 '분할 정복' 알고리즘이다.

평균 속도가 O(N * logN)이다. (logN은 거의 상수라고 볼 수 있다.)

 

> 특정한 값을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤에 배열을 반으로 나눈다.

퀵 정렬에는 '기준 값'이 존재한다. 이를 피벗(Pivot)이라고 한다. 보통 첫번째 원소의 value를 피벗으로 설정한다.

 

 : 각 숫자를 적절한 위치에 삽입하는 방식이다. 다른 정렬 방식들은 무조건 위치를 바꾸지만 삽입 정렬은 '필요할 때만' 위치를 바꾸게 된다.