Basic sorting algoritm

이번 Posting에서는 기본적인 sorting들에 대하여 정리를 할 것이다.


  • Bubble sort(버블 정렬)
  • Insertion sort(삽입 정렬)
  • Selection sort(선택 정렬)
  • Heap sort(힙 정렬)
  • Quick sort(퀵 정렬)
  • merge sort(병합 정렬)


1. Bubble sort(버블 정렬)

 거품 정렬은 정렬을 처음 배울 때 나오는 녀석이다. 가장 직관적이고 이해하기 쉽기 때문에 처음에 배우는 것이라고 생각한다. 이 녀석의 시간 복잡도는 O(N^2) 즉 for문 2개로 정렬을 할 수가 있다. 쉽지만 퍼포먼스가 떨어지기 때문에 잘 사용하지 않는다.

버블 정렬 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class BubbleSort {
    static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
    public static void main(String[] args) {
        bubbleSort();
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]);
            if (i < data.length - 1) System.out.print(" ");
        }
    }
    public static void bubbleSort() {
        for (int i = 0; i < data.length; i++) {
            for (int j = 1; j < data.length - i; j++) {
                if (data[j] < data[j - 1]) {
                    int tmp = data[j - 1];
                    data[j - 1] = data[j];
                    data[j] =  tmp;
                }
            }
        }
    }
}




여담이지만 버블 정렬이 왜 버블 정렬인지 생각해본적이 있나?
위 이미지를 왼쪽으로 90도 회전시키면 위로 올라가는 모양이 된다 그래서 거품이 올라가는 형상같다고하여 버블 소트라고 이름이 붙은 것이다.



2. Insertion sort(삽입 정렬)

 삽입 정렬은 간단하게 말해서 앞에서부터 정렬을 하는데 현재 index의 크기를 판단해서 적절한 위치에 삽입을 하는 로직이다. 삽입 정렬은 이미 정렬이 되어있다면 O(N)의 복잡도를 갖는다. 왜냐하면 배열을 보면서 바꿔줄 녀석이 없으면 삽입하는 loop를 돌지 않아도 되기 때문이다. 하지만 보통의 경우 Bic-O O(N^2)의 복잡도를 갖는다.

삽입 정렬 코드


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class InsertionSort {
    static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
    public static void main(String[] args) {
        insertionSort();
        for (int i = 0; i < data.length; i++) {
            System.out.print(data[i]);
            if (i < data.length - 1) System.out.print(" ");
        }
    }
    public static void insertionSort() {
        for (int i = 1; i < data.length; i++) {
            int tmp = data[i], here = i - 1;
            for (int j = i - 1; j > -1; j--) {
                if (data[j] > tmp) {
                    data[j + 1] = data[j];
                }else {
                    here = j + 1;break;
                }
            }
            data[here] = tmp;
        }
    }
}






3. selection sort(선택 정렬)

 선택 정렬도 버블 정렬과 마찬가지로 가장 이해하기 쉬운 로직으로 구현된 정렬 방식이다.
구현이 간단하다. 시간 복잡도는 O(N^2)으로 좋은 퍼포먼스를 가진 것은 아니다.

선택 정렬 코드


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
public class SelectionSort {
    static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
    public static void main(String[] args) {
        selectionSort();
        for (int i = 0; i &lt; data.length; i++) {
            System.out.print(data[i]);
            if (i &lt; data.length - 1) System.out.print(" ");
        }
    }
    public static void selectionSort() {
        for (int i = 0; i &lt; data.length - 1; i++) {
            for (int j = i + 1; j &lt; data.length; j++) {
                if (data[i] &gt; data[j]) {
                    int tmp = data[i];
                    data[i] = data[j];
                    data[j] = tmp;
                }
            }
        }
    }
}





4. Heap sort(힙 정렬)

  힙 정렬은 자료구조인 heap을 이용하여 정렬을 하는 것으로 자세한 내용은 data structure 탭에 있다. 다음 코드는 heap으로 구현된 우선순위 큐를 활용한 방법이다.

힙 정렬 코드


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import java.util.PriorityQueue;
import java.util.Queue;

public class HeapSort {
    static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
    static Queue priorityQueue = new PriorityQueue();
    public static void main(String[] args) {
        for (int i = 0; i &lt; data.length; i++) {
            priorityQueue.add(data[i]);
        }
        heapSort();
    }
    public static void heapSort() {
        while (!priorityQueue.isEmpty()) System.out.print(priorityQueue.poll() + " ");
    }
}


5. Quick sort(퀵 정렬)

 퀵 정렬은 흔하게 사용하는 정렬 알고리즘으로 어떤 pivot 값을 정하고 왼쪽과 오른쪽에 각각 작은 것과 큰것을 배치시킨다. 이러한 로직을 왼쪽 오른쪽으로 분할하여 정렬한다.

 최악의 경우 O(N^2)의 복잡도를 갖지만 일반적으로는 O(NlogN)의 복잡도를 갖는다.
위에서 언급한 최악의 경우는 정렬이 되어있는 배열을 정렬하려고할 때 발생한다. 그 이유는 첫번 째 인덱스의 값을 pivot으로 결정한 경우, 분할되지 못하고 한번의 라운드에 n번의 비교를 해야하기 때문이다.

퀵 정렬 코드


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
public class QuickSort {
    static int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
    public static void main(String[] args) {
        quickSort(data, 0, data.length - 1);
        for (int i = 0; i &lt; data.length; i++) {
            System.out.print(data[i]);
            if (i &lt; data.length - 1) System.out.print(" ");
        }
    }
    public static void quickSort(int[] arr, int l, int r) {
        int left = l, right = r;
        int pivot = arr[(l + r) / 2];
        do{
            while (arr[left] &lt; pivot) left++;  // find index that higher than pivot
            while (arr[right] &gt; pivot) right--;// find index that lower than pivot
            if (left &lt;= right) {
                int tmp = arr[left];
                arr[left] = arr[right];
                arr[right] = tmp;
                left++;right--;
            }
        }while (left &lt;= right);
        if (l &lt; right) quickSort(arr, l, right);
        if (r &gt; left) quickSort(arr, left, r);
    }
}





6. merge sort(병합 정렬)

 병합 정렬은 정렬할 배열을 반으로 쪼개면서 좌우 배열을 계속해서 분할한 후 각 배열 내에서 정렬을 한 후 다시 합치는 과정을 통해 정렬하는 알고리즘이다. 시간 복잡도는 O(NlogN)을 보장한다. 하지만 단점은 배열을 2개 쓰기 때문에 공간 복잡도가 올라긴다.

병합 정렬 코드


 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class MergeSort {
    static int[] sortedArray = new int[11];
    public static void main(String[] args) {
        int[] data = {14, 6, 45, 43, 41, 28, 38, 36, 49, 16, 34};
        mergeSort(data, 0, data.length - 1);
        for (int i = 0; i < sortedArray.length; i++) {
            System.out.print(sortedArray[i]);
            if (i < sortedArray.length - 1) System.out.print(" ");
        }
    }
    public static void mergeSort(int[] arr, int m, int n) {
        int mid;
        if (m < n) {
            mid = (m + n) >> 1;
            mergeSort(arr, m, mid);
            mergeSort(arr, mid + 1, n);
            merge(arr, m, mid, n);
        }
    }
    public static void merge(int[] arr, int m, int mid, int n) {
        int i = m, j = mid + 1, k = m;
        while (i <= mid && j <= n) {
            sortedArray[k] = (arr[i] <= arr[j]) ? arr[i++] : arr[j++];
            k++;
        }
        int start = (i > mid) ? j : i, end = (i > mid) ? n : mid;
        for (int t = start; t <=  end; t++, k++) {
            sortedArray[k] = arr[t];
        }
        for (int t = m; t <= n; t++) {
            arr[t] = sortedArray[t];
        }

    }
}




이상으로 Posting을 마친다. (위의 그림의 출처: https://cdn-images-1.medium.com )

이 블로그의 인기 게시물

웹툰 무료로 볼 수 있는 사이트

출근하는 지하철 안이나 버스 등 대중교통을 이용하면서 짬 내서 보거나 시간 때우기용으로 좋은 게 웹툰만 한 게 있을까 합니다. 또 웹툰을 자주 즐겨보는 사람들에겐 어디하나 마음놓고 이용할 수 있는 곳을 찾고 싶겠지만, 집중력 강하고 정주행을 하고 싶은 유저들 입장에서 무료 웹툰 사이트 추천을 해보겠습니다. 하지만 무료로 미리보기를 제공하는 사이트들의 경우 대부분 법에 문제가 있거나 불법적으로 운영되는 사이트들이 대부분입니다. 그래서 추천할만한 블로그 글 두 가지를 가지고 나왔습니다. 1.  무료웹툰   2.  툰코 이곳에 상당히 많은 수의 웹툰 사이트들이 있습니다, 몰랐는데 새로운 사이트들이 굉장히 많더군요. 적어도 30개의 웹툰 사이트들이 있습니다. 이곳을 방문해서 재미있는 웹툰을 골라서 보는 것도 참 좋을 것 같습니다. 뿐만 아니라 무료 사이트들도 추천해 놓았습니다. 무료 사이트의 경우 주소가 자주 바뀌는 특성을 가지고 있는데요, 이 블로그는 주기적으로 업데이트를 하기 때문에 즐겨찾기해 놓으면 나중에 지속적으로 이용이 가능할 것 같습니다. 또한 웹툰 사이트별로 특징도 소개되어있어 자신에게 맞는 사이트를 골라서 입장하면 될 것 같습니다. 이상으로 웹툰 무료로 볼 수 있는 사이트들에 대한 링크를 제공하였습니다. 감사합니다.
자세한 내용 보기

BackJoon 1011, Fly me to the alpha centauri, 규칙 찾기 문제

오랜만에 글을 올리게 되네요. https://www.acmicpc.net/problem/1011 위 링크에서 문제 확인 가능합니다. 이 문제는 최소로 공간이동 장치를 사용해서 이동할 수 있는데, 마지막에는 꼭 1로 이동을 해야한다는 조건이 있어서 조금 까다롭습니다. 즉, 보면 다음과 같이 이동이 가능합니다. 1 11 = 2 121    = 4 1221  = 6 1211  = 7 12321   = 9 123321 123221 .... 이런 식인데 대충 알아 냈겠지만 규칙이 존재합니다. 바로  자리수를 기준으로 나누는 겁니다. 2자리의 경우 11이 최대이고 3자리의 경우 121, 4자리는 1221, 5자리는 12321 ... 쭉 생깁니다. 예를 들어 이동하려는 거리가  7 이면 7보다 작거나 같은 곳의 인덱스를 찾으면 됩니다. 바이너리 서치를 통하면 더욱 빠르게 접근할 수 있습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 import java.io.* ; import java.util.Arrays ; public class B1011 { static int T, x, y, ans, e; static long [] md = new long [ 100000 ]; static long pos; static String in; public static void main (String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System. in )); ...
자세한 내용 보기

BaekJoon 6591, 이항 쇼다운 조합문제

조합의 수를 구하는 알고리즘을 짜면 되는 심플한 문제입니다. https://www.acmicpc.net/problem/1011 일단 팩토리얼을 구해서 곱하고 나누고 하는 문제가 아니라, 중간 과정에서 나눠 주는 것이 포인트입니다. 안그러면  int 범위를 벗어나서 값이 이상해집니다. 저는 gcd를 이용해서 값을 나눠주면서 계산을 했습니다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 import java.io.* ; public class B6591 { static int N, M; static int [] a = new int [ 101 ]; static int [] b = new int [ 101 ]; static String in; public static void main (String[] args) throws IOException { BufferedReader br = new BufferedReader( new InputStreamReader(System. in )); BufferedWriter bw = new BufferedWriter( new OutputStreamWriter(System. out )); while (!(in = br. readLine ()). equals ( "0 0" )) { N = Integer. parseInt (in. split ( " " )[ 0 ]); M = Integer. parseInt (in. s...
자세한 내용 보기