sorting / 기수 정렬, 계수 정렬

[WonYong-Jang]

Selection Sort

정렬되지 않은 전체 자료중에서 해당 위치에 맞는 자료를 선택하여 위치를 교환하는 방식

for(int i = 0; i < N-1; i++)
{
    int min = i;  
    for(int j = i + 1; j < N; j++)
    {
          if(data[min] > data[j]) min = j; // 가장 작은 값 찾아가기
    }
    int temp = data[min];  // 두번째 for 문이 끝난 후 가장 작은 값과 i 를 swap
    data[min] = data[i];
    data[i] = temp;
}

• 연산 및 이동 연산 횟수가 고정된 값 ( N^2) 이므로 최악의 연산 횟수의 경우나 평균 연산 횟수 값이나 정렬의 효율성은 N^2 ( 두개의 for문 종료 후 반드시 교환 연산이 이루어지므로 최선, 최악 의미 X)
• 같은 값의 인덱스끼리도 교환 연산 발생 가능성

Insertion Sort

자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 자신의 위치를 찾아 삽입

int j=0;
for(int i=1; i< N; i++) // 두번째 인덱스 부터 시작 
{
    j= i -1;
    int target = data[i]; // 삽입할 숫자 
    while(j >= 0 && data[j] > target) // target 위치 찾기 
    {
        data[j+1] = data[j]; // target 보다 큰 숫자 앞으로 한칸 씩 당기기 
        j--;
    }
    data[j+1] = target; // 자리 삽입 
}

• target 이전 인덱스의 배열은 이미 정렬되어 있고 그 배열에 target 숫자의 위치를 삽입
• 이미 정렬되어 있는 경우라면 while을 거치지 않으므로 비교 횟수 줄임 O(N)
• 선택, 버블 정렬보다 성능이 좋지만 평균 O(N^2) 시간 복잡도

Bubble Sort

인접한 두수를 비교해서 큰 수를 뒤로 보내는 정렬, 느리지만 코드가 코드가 단순

for(int i=0; i< N-1; i++)
{   
    for(int j = 0; j< N - i -1; j++)
    {
        if(data[j] > data[j+1])
        {
            int temp = data[j];
            data[j] = data[j+1];
            data[j+1] = temp;
        }
    }
}

• 한번 순회를 마칠때마다 비교대상이 하나씩 줄어듬! (맨 뒤 부터 큰수가 정렬)
• 이미 정렬되어있을때 자리 교환이 일어나지 않으므로 시간을 줄일 수 있지만 평균 O(N^2) 시간복잡도

Quick Sort

재귀를 이용한 분할 정복 알고리즘, 다른 NlogN 정렬 알고리즘 보다 속도가 빠르다(pivot을 적절하게 선택했을 때)

이유는 불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환 할뿐 아니라, 한번 결정된 기준은 추후 연산에서 제외되는 성질을 가지고 있기 때문!

• 평균 복잡도는 nlogn 최악의 경우 n^2
• 일반적인 퀵소트 O(N^2) // 빅오표기법은 최악의 경우를 표현하므로

• 하지만 pivot 개선을 통해서 O(NlogN) 가능

  • 분할 정복 : 큰 문제에서 작은 문제 단위로 쪼개면서 해결하는 방식

public class quickSort {
    static int N;
    static int[] data = new int[1000005];
    public static void main(String[] args) throws IOException {
        qSort(0, N-1);
    }
    public static void qSort(int left, int right)
    {
        if(left >= right) return;

        int pivot = partition(left, right);
        qSort(left, pivot-1);
        qSort(pivot+1, right);
    }
    public static int partition(int left, int right) // pivot 
    {
        int mid = (left + right) / 2;            ////////// 중요!!! 중간값과 처음값 swap
            swap(left, mid);                   ////////// 이 과정이 있어야 n^2 피할수 있다

        int j = left ; // 처음은 pivot 의 위치 ! 
        int pivot = data[left];
        for(int i= left+1; i<= right; i++)
        {
            if(data[i] < pivot) 
            {
                  j++; // 왼쪽에는 pivot 보다 작은 값들로 바뀌게 됨 !
                              swap(i, j);
            }
        }
                swap(j, left);

        return j;
    }
}

==> Devide

• 먼저 배열 중에 임의의 데이터 pivot으로 선택( 왼쪽, 오른쪽, 중간, 랜덤으로 선택 방식이 있다.) 에 따라 속도 달라짐
• 배열에 있는 데이터들의 pivot 보다 작은 데이터 그룹과 큰 데이터 그룹으로 나눈다.
• partition 이라고 부름

==> Conquer

• Pivot 을 중심으로 나누어진 두 그룹을 recursive 하게 반복
  • 평균 O(NlongN), 최악 시간복잡도는 O(N^2) 이므로 불안정

MergeSort

분할 정복 알고리즘 중 하나이며, O(NlogN) 안정정렬에 속함

1) Divide(분할) : 해결하고자 하는 문제를 작은 크기의 동일한 문제로 분할 2) Conquer(정복) : 각각의 문제를 해결한다 3) Merge(합병) : 작은 문제의 해를 합하여 원래의 문제에 대한 해를 구함

public class mergeSort {
    static int N;
    static int[] data = new int[1000005];
    static int[] temp = new int[1000005];
    public static void main(String[] args) throws IOException {
        mSort(0, N-1);
    }
    public static void mSort(int left, int right)
    {
        if(left == right) return;

        int mid = (left + right) / 2;
        mSort(left, mid);
        mSort(mid+1, right);
        merge(left, mid, right);
    }
    public static void merge(int left,int mid, int right)
    {
        for(int i= left; i<= right; i++)
            temp[i] = data[i];

        int i, j, k; 
        i = k = left; //temp 첫번째  시작 인덱스 i, data 시작 인덱스 k 
        j= mid+1; // temp 두번째 시작 인덱스 k

        while(i<= mid && j <= right)
        {
            if(temp[i] <= temp[j]) data[k++] = temp[i++];
            else data[k++] = temp[j++];
        }

        // 남은 배열은 그대로 넣기 
        while(i<= mid)
            data[k++] = temp[i++];
        while(j <= right)
            data[k++] = temp[j++];

    }
}

Heap Sort

Heap

힙은 완전 이진 트리( Complete binary tree ) 일종으로 우선 순위 큐를 위하여 만들어진 자료구조

여러 개의 값들 중에서 최대값, 최소값을 빠르게 찾는 장점

힙 속성

• heap order property : 각 노드의 값은 자신의 자식노드가 가진 값보다 크거나 같다 (Max heap) 각 노드의 값은 자신의 자식노드가 가진 값보다 작거나 같다 ( Min heap)
• heap shape property : 모양은 완전 이진 트리

Heap vs Binary Search Tree 구분 할 것!

• 힙은 각 노드의 값이 자식노드보다 큰 반면, 이진탐색트리는 왼쪽 자식노드가 제일 작고 부모노두가 그다음 크며 오른쪽 자식노두가 가장 큰 값을 가짐

  -힙은 우선순위 정렬 / 이진탐색트리는 탐색에 강점을 지닌 자료구조 !

힙의 삽입

1) 힙에 새로운 요소가 들어오면, 새로운 노드를 힙의 마지막 노드에 삽입 2) 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족 시킴

힙의 삭제

1) 최대 힙에서 최대값은 루트 노드이므로 루트 노드가 삭제됨 2) 삭제된 루트에는 힙의 마지막 노드를 가져옴 3) 힙을 재구성

public class heapSort {

    static int N;
    static int[] data = new int[1000005];
    public static void main(String[] args) throws IOException {
        hSort(N);
    }
    public static void hSort(int n)
    {
        for(int i = n/2; i >=1; i--) // 자식을 가진 부모를 뒤에서 부터 업데이트 ! ( 처음 힙 만들기 !)
        {
            heapify(n, i);
        }

        for(int i= n; i>=2 ; i--)
        {
            swap(1, i); // 정렬된 가장 큰 값을 맨뒤 요소와 swap 
            heapify(i-1, 1); // 1 번부터 다시 힙 정렬 / 이때 전체 n 범위를 하나씩 줄여나감 ! 
        }

    }
    public static void heapify(int n, int i) // 힙 속성에 맞게 구성 
    {
        int p, left, right;
        p = i; // 노드의 자식노드들 중 큰 값을 올리기 위한 부모노드 인덱스 설정 
        left = i*2; // 왼쪽 자식
        right = i*2 +1; // 오른쪽 자식

        if(left <= n && data[p] < data[left]) p = left; // 두 자식들 중 큰 값 찾기 
        if(right <= n && data[p] < data[right]) p = right;

        if(p != i) // 값이 다르다는 얘기는 두 자식들 중 부모노드보다 큰값이 있어서 업데이트 필요하단 얘기 
        {
            swap(p, i);
            heapify(n, p); // 바뀐 값 자식들도 내려가면서 확인하기 위해 재귀 
        }
    }
    public static void swap(int a, int b)
    {
        int temp = data[a];
        data[a] = data[b];
        data[b] = temp;

    }
}

안정 정렬과 불안정 정렬 설명

관련 링크 : http://mygumi.tistory.com/94 안정 정렬 : 삽입 정렬, 버블정렬, 합병 정렬 불안정 정렬 : 선택정렬, 퀵 정렬, 힙 정렬

[WonYong-Jang]

Merge Sort 응용

Counting Inversions

• 10090 counting inversions , 2517 달리기

• 문제 설명 배열 A는 1,2,3,...n 의 수가 무작위 순서로 들어 있다. 이 수들에서 두개의 무작위 수를 생각했을 때, 그 순서 대비 크기가 역전되어 있는 두 수의 쌍이 몇개가 되는 지를 구하시오. 예를 들어, A={2,3,6,4,1,7}일 때, 크기가 역전된 쌍은, (2,1), (3,1), (6,4), (6,1), (4,1)

따라서 Number of inversions = 5

분할정복에 의한 MergeSort를 응용

<img width="576" alt="2018-12-31 4 50 35" src="https://user-images.githubusercontent.com/26623547/50556414-3753e080-0d1c-11e9-9011-c2261b90bfb8.png">

두번째 그림에서 오른쪽 배열에 있는 j=4 의 값인 2와 i =1 의 값 3을 비교했을 때 
if(arr[i] > arr[j]) 이면 그 이후 arr[i] 의 값들은 전부 arr[j] 보다 큰 값이 된다 ( 소팅되어 있기때문 )
mergeSort 를 아래와 같이 카운팅 하는 소스만 추가해준다.

public static void merge(int left, int mid, int right) { for(int i=left; i<= right; i++) temp[i] = data[i];

int i=0, j=0, k=0;
i = k = left;
j = mid+1;

while(i <= mid && j <= right)
{
    if(temp[i] <= temp[j]) data[k++] = temp[i++];
    else // Inversions 발생 
    {
        data[k++] = temp[j++];
        result += ( mid-i+1 ); // inversion count 
    }
}

while(i <= mid) data[k++] = temp[i++];
while(j <= right) data[k++] = temp[j++];

}

[WonYong-Jang]

Counting Sort

• 정렬 알고리즘으로 O(n) 의 시간복잡도
• 비교 연산 없이 각각 요소가 몇번 등장했는지 세어줌 ex)

A : 2, 0, 1, 1, 0, 2 => 위와 같이 0, 1, 2로만 이루어 져있는 배열 A가 있다면 0,1,2 각각 몇번 등장하는지 세어주고 그 세우준 값 대로 차례대로 정렬하게 되면 O(n) 시간복잡도로 다른 정렬알고리즘에 비해 더 빠르게 정렬 가능 하지만, 배열의 최소값과 최대값 의 차이가 위의 예시와 다르게 차이가 크면 클수록 비효율적인 알고리즘

[WonYong-Jang]

링크드 리스트 Merge Sort

• leetcode 21, 148, 23

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // l1, l2 둘중 하나가 먼저 null이 나올 경우는 
        // l1 이 null이 나올 경우 l2를 연결해주게 return
        // l2는 정렬되어 있으므로 l1 뒤에 연결 해주면 끝 
        if(l1 == null) return l2;
        else if(l2 == null) return l1;
        else {
            if(l1.val <= l2.val) {
                l1.next = mergeTwoLists(l1.next, l2);
                return l1;
            }
            else {
                l2.next = mergeTwoLists(l1, l2.next);
                return l2;
            }
        }
    }
}