본문 바로가기
Programming/Algorithm

[algorithm] 기초적인 정렬 : 선택 정렬, 삽입 정렬

by kghworks 2023. 12. 28.

목차

  • 선택 정렬
  • 삽입 정렬
  • 삽입정렬 vs 선택정렬
  • 셸 정렬

선택정렬 (Selection sorting)

길이 N의 배열이 주어졌을 때,

  1. 배열의 가장 작은 항목을 찾아 [0]와 교환
  2. 그다음으로 작은 항목을 찾아 [1]와 교환
  3. ...
  4. 그 다음으로 작은 항목을 찾아 [N-1]과 교환

와 같이 모든 배열이 정렬될 때까지 (N-1) 번을 교환하는 방법이다.

public class Selection {

    // a[]를 오름차순으로 정렬
    public static void sort(Comparable[] a) {

        int N = a.length;

        for (int i = 0; i < N; i++) {
            // a[i]를 a[i+1..N] 중에서 가장 작은 원소와 교환
            int idxMin = i;

            for (int j = i + 1; j < N; j++) {
                if (less(a[j], a[idxMin])) idxMin = j;
            }
            exch(a, i, idxMin);
        }
    }

    public static void main(String[] args) {
        String[] a = new String[]{"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        sort(a);
        assert isSorted(a);
        show(a);

        Integer[] b = new Integer[]{8, 2, 4, 9, 3, 6, 1, 5, 7, 0};
        sort(b);
        assert isSorted(b);
        show(b);
    }
    
}

선택 정렬 전개

단점 : 실행 시간이 입력 크기에 비례한다

 무조건 배열의 크기 (N-1)만큼의 비교 연산이 필요하다. 최악의 경우, 완전히 정렬된 배열을 input으로 넣어도 배열의 크기만큼 비교연산을 해야 한다. 즉, 배열의 정렬 정도와 실행 시간은 무관하고 완전히 정렬된 배열과 완전히 정렬되지 않은 배열의 실행 시간이 동일하다.

삽입 정렬 (Insertion sorting)

브리지 게임을 할 때를 생각해보자. 손에 정렬된 카드가 있고, 새로운 카드를 쥐었다면 손에 쥔 이미 정렬된 카드의 적절한 위치에 삽입한다. 컴퓨터 알고리즘으로 구현할 때에는 적절한 위치에 삽입할 때 오른쪽 카드를 전부 오른쪽으로 한 칸씩 밀어주어야 한다. 원소를 앞에서부터 순회하며 왼편을 정렬된 상태로 만들지만, 언제든지 새로운 원소가 왼쪽 적합한 위치에 삽입될 수 있다.

 

public class Insertion {

    // a[]를 오름차순으로 정렬
    public static void sort(Comparable[] a) {

        int N = a.length;

        for (int i = 1; i < N; i++) {
            // a[i]를 [i-1], [i-2], ... 에서 적절한 위치에 삽입
            for (int j = i; j > 0 && less(a[j], a[j - 1]); j--) {
                exch(a, j, j - 1);
            }
        }
    }

    public static void main(String[] args) {
        // Read strings from standard input, sort them, and print.
        String[] a = new String[]{"S", "O", "R", "T", "E", "X", "A", "M", "P", "L", "E"};
        sort(a);
        assert isSorted(a);
        show(a);
    }
}

삽입 정렬 전개

장점 : input 배열의 정렬 상태에 의존한다

 input이 정렬되어있을 수록 실행시간이 빨라진다. 따라서 정렬정도가 높은 배열일수록 삽입정렬을 사용하는 것이 적합하다. 

정렬 정도가 높은 배열이란 아래와 같은 경우다

  • 원소의 위치가 최종 위치에서 멀지 않을수록
  • 정렬된 큰 배열에 작은 배열을 이어 붙인 경우
  • 정렬 위치에서 벗어난 원소의 수가 적을수록

삽입정렬 vs 선택정렬

삽입 정렬 (좌) vs 선택 정렬 (우)

 

평군적으로 삽입정렬의 비교횟수가 더 적다. 삽입 정렬은 input이 정렬되어 있을수록 비교연산 횟수가 적어진다. 마치 정렬된 카드를 손에 쥐고 있고, 새로운 카드를 뽑았을 때와 같다. (우측부터 차례대로 탐색해 가며 적절한 위치를 찾아 카드를 넣을 것이다)

 

아래와 같이 JMH로 성능 테스트를 진행해보았다. 

import java.util.concurrent.TimeUnit;

@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MICROSECONDS)
public class CompareSorting {

    private Double[] generateRandomArray(int i) {
        Double[] arr = new Double[i];
        for (int j = 0; j < i; j++) {
            arr[j] = Math.random();
        }
        return arr;
    }

    @Benchmark
    public void sorting_insertion() {
        Double[] arr = generateRandomArray(10000);
        Insertion.sort(arr);
    }

    @Benchmark
    public void sorting_insertion_ordered() {
        Double[] arr = new Double[]{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9};
        Insertion.sort(arr);
    }


    @Benchmark
    public void sorting_selection() {
        Double[] arr = generateRandomArray(10000);
        Selection.sort(arr);
    }

    @Benchmark
    public void sorting_selection_ordered() {
        Double[] arr = new Double[]{0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9};
        Selection.sort(arr);
    }
}
Benchmark                                 Mode  Cnt      Score     Error  Units
CompareSorting.sorting_insertion          avgt   15  52888.982 ± 326.451  us/op
CompareSorting.sorting_selection          avgt   15  51688.885 ± 356.165  us/op
CompareSorting.sorting_selection_ordered  avgt   15      0.112 ±   0.037  us/op
CompareSorting.sorting_insertion_ordered  avgt   15      0.020 ±   0.001  us/op

 

 벤치마크 결과 일반적인 삽입정렬이 선택정렬보다 더 오래 걸리는 걸 볼 수 있다. 사전에 정렬된 배열에 대해 정렬을 수행하면 삽입정렬이 

82% 빠른 것을 알 수 있다. 삽입정렬이 선택정렬보다 조금 더 오래 걸리는 것이 의아한데, Alogrithm 4th edition (March 24, 2011)에 의하면 OS, 자바 런타임 등 모든 요소들이 기계어 코드에 영향을 미치기 때문에 이러한 요인들로 인해 알고리즘 성능의 작은 차이들은 인지하기 어렵다고 한다.

초심자라면 이러한 의문이 들 수도 있다. ...(생략) 운영체제도 다르고 자바 런타임도 다르고 여러 가지가 다르다. 이 모든 차이들이 알고리즘의 기계어 코드에 영향을 미친다. 같은 컴퓨터에서의 실행 간에 차이가 나는 것은 매 실행 시점마다 다른 프로그램들이 영향을 미치거나 기타 다른 조건들이 발생하기 때문이다....(생략)

출처 : Algorithm 4th edition (Q&A 320p)

 

삽입정렬의 한계 : 가장 작은 원소가 오른쪽 끝에 있다면?

 삽입정렬은 인접 원소 간에만 교환이 일어난다. 우연히 input의 가장 작은 원소가 가장 오른쪽에 있다면, 해당 원소를 제자리에 가져다 놓기 위해 (N-1) 번의 교환 연산이 필요하다. 즉 운나쁘게 배열이 정렬되어 있고, 그 크기가 크면 클수록 정렬 실행시간이 느려진다.

셀 정렬 (Shell sorting)

 삽입 정렬에 기반을 둔 빠른 알고리즘이다. h(gap)라는 개념이 나오는데, h는 말 그대로 간격이다. 이미 정렬된 배열은 아래와 같이 특정 h(간격) 별로 정렬된 독립된 배열 (시퀀스)를 가지게 된다.

정렬된 배열은 특정 h(gap) 별로 정렬된 독립된 시퀀스들로 이루어진다

 

 따라서 배열을 정렬할 때 특정 h별로 독립된 시퀀스에 대해 삽입 정렬을 재귀적으로 해나간다는 것이 주요 발상이다. 이렇게 하면 기존에 삽입 정렬이 가지고 있던 큰 단점 (원소가 제자리로부터 가장 멀리 있을 때 N-1번의 교환 연산이 필요)을 해결할 수 있다. 

 h 값은 큰 값부터 시작하여 1이 될 때까지 재귀벅으로 정렬을 수행하는데, (N/3) 이상이면서 가장 작은 수로 시작해 1까지 줄여나간다. 

/*
 * Copyright © 2000–2019, Robert Sedgewick and Kevin Wayne.
 * Last updated: Thu Aug 11 09:04:20 EDT 2022.
 */

/**
 * The {@code Shell} class provides static methods for sorting an
 * array using <em>Shellsort</em> with
 * <a href = "https://oeis.org/A003462"> Knuth's increment sequence</a>
 * (1, 4, 13, 40, ...). In the worst case, this implementation makes
 * &Theta;(<em>n</em><sup>3/2</sup>) compares and exchanges to sort
 * an array of length <em>n</em>.
 * <p>
 * This sorting algorithm is not stable.
 * It uses &Theta;(1) extra memory (not including the input array).
 * <p>
 * For additional documentation, see
 * <a href="https://algs4.cs.princeton.edu/21elementary">Section 2.1</a> of
 * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne.
 *
 * @author Robert Sedgewick
 * @author Kevin Wayne
 */
public class Shell {

    // This class should not be instantiated.
    private Shell() {
    }

    /**
     * Rearranges the array in ascending order, using the natural order.
     *
     * @param a the array to be sorted
     */
    public static void sort(Comparable[] a) {
        int n = a.length;

        // 3x+1 increment sequence:  1, 4, 13, 40, 121, 364, 1093, ...
        int h = 1;
        while (h < n / 3) h = 3 * h + 1;

        while (h >= 1) {
            // h-sort the array
            for (int i = h; i < n; i++) {
                for (int j = i; j >= h && less(a[j], a[j - h]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            assert isHsorted(a, h);
            h /= 3;
        }
        assert isSorted(a);
    }


    /***************************************************************************
     *  Helper sorting functions.
     ***************************************************************************/

    // is v < w ?
    private static boolean less(Comparable v, Comparable w) {
        return v.compareTo(w) < 0;
    }

    // exchange a[i] and a[j]
    private static void exch(Object[] a, int i, int j) {
        Object swap = a[i];
        a[i] = a[j];
        a[j] = swap;
    }


    /***************************************************************************
     *  Check if array is sorted - useful for debugging.
     ***************************************************************************/
    private static boolean isSorted(Comparable[] a) {
        for (int i = 1; i < a.length; i++)
            if (less(a[i], a[i - 1])) return false;
        return true;
    }

    // is the array h-sorted?
    private static boolean isHsorted(Comparable[] a, int h) {
        for (int i = h; i < a.length; i++)
            if (less(a[i], a[i - h])) return false;
        return true;
    }

    // print array to standard output
    private static void show(Comparable[] a) {
        for (int i = 0; i < a.length; i++) {
            StdOut.println(a[i]);
        }
    }

    /**
     * Reads in a sequence of strings from standard input; Shellsorts them;
     * and prints them to standard output in ascending order.
     *
     * @param args the command-line arguments
     */
    public static void main(String[] args) {
        String[] a = StdIn.readAllStrings();
        Shell.sort(a);
        show(a);
    }

}

 

셸 정렬 전개

 

셸 정렬의 성능

셸 정렬의 성능은 아직까지 충분히 연구가 이루어지지 않았다고 한다. 그러나 꽤 큰 배열에서도 적절한 성능을 보여준다고 한다. 참고로 내 pc에서의 벤치마크 성능은 아래와 같다.

Benchmark                                 Mode  Cnt    Score     Error  Units
CompareSorting.sorting_insertion          avgt    5  536.830 ± 427.914  us/op
CompareSorting.sorting_selection          avgt    5  495.480 ± 266.059  us/op
CompareSorting.sorting_shell              avgt    5   94.268 ±  11.203  us/op

 

셸 정렬이 다른 정렬보다 최소 81% 이상 빠른 성능을 보여줬다.

참고

https://product.kyobobook.co.kr/detail/S000001792777

 

알고리즘 | 로버트 세지윅 - 교보문고

알고리즘 | 알고리즘과 자료 구조의 핵심을 담은 고전 클래식 레퍼런스 로버트 세지윅 베스트셀러의 최신 버전. 지난 수십년 동안 발전한 알고리즘과 자료 구조에 대한 내용을 한 권에 담았다.

product.kyobobook.co.kr

 

저작자표시 비영리 변경금지

'Programming > Algorithm' 카테고리의 다른 글

[algorithm] 정렬 4. 정리 및 응용  (0) 2024.06.22
[algorithm] 정렬 3. 우선순위 큐 (Priority Queues)  (2) 2024.04.19
[algorithm] 정렬 2. 퀵 정렬  (2) 2024.02.04
[algorithm] 정렬 1. 병합 정렬  (1) 2024.01.07

관련글

댓글

티스토리툴바