정렬은 기본적으로 데이터를 특정 순서로 정렬하는 것을 의미하므로 해당 데이터를 사용하기가 더 쉽습니다. 이 게시물에서는 몇 가지 기본적인 정렬 알고리즘에 대해 이야기하겠습니다. 버블정렬, 선택정렬, 삽입정렬.


정렬 알고리즘과 복잡성



연산
복잡성


버블 정렬
오(n2)

선택 정렬
오(n2)

삽입 정렬
오(n2)

쉘 정렬
오(n2)

빠른 정렬
오(n2)

기수 정렬
오(nk)

힙 정렬
O(nlog(n))

병합 정렬
O(nlog(n))


주요 콘텐츠로 이동하기 전에 이러한 모든 정렬 알고리즘이 작동하는 방식을 시각화하는 데 도움이 되는 website을 추천하고 싶습니다. (P.S. 해시 테이블, 바이너리 힙 시각화 등과 같은 다른 작업에도 도움이 됩니다.) 그리고this one도 도움이 됩니다!

버블 정렬

버블 정렬에서는 한 번에 2개의 항목을 비교하고 교환하거나 다음 쌍을 비교하기 위해 이동합니다. 악명 높게 느리지만 개념적으로 가장 간단한 정렬 알고리즘입니다.


크기가 n인 배열을 정렬하는 방법에 대한 유사 코드

1. Repeat i) to ii) for n times
    i) Compare the leftmost element in array with the next element
        a. If the leftmost element is bigger, swap them
        b. Else, go to 2.
    ii) Move to next position, set that element to be the leftmost element. Is there next element?
        a. Yes, go back to i)
        b. No, go back to 1.
2. Done

그리고 여기 버블 정렬의 자바 코드가 있습니다.

public void bubbleSort() {
    int out, in, temp;
    int[] a = new int[nElems];      // nElems is the number of elements we'll input later ^^||
    for(out=nElems-1; out>1; out--) {  
        for(in=0; in<out; in++) {
            if( a[in] > a[in+1] ) { // out of order?
                temp = a[in];       // swap them
                a[in] = a[in+1];
                a[in+1] = temp;
            }
        }
    }
}

버블 정렬의 효율성

비교 작업:

for N items: (N-1) + (N-2) + (N-3) + ... + 1
= N*(N-1)/2
≈ N²/2

교환 작업:

usually less than comparison operations
≈ N²/4

이는 복잡성 ≈ O(N2)를 의미하며 상당히 느림

선택 정렬

선택 정렬에서는 데이터를 따라 이동하면서 가장 작은 항목을 선택하고 선택한 항목을 위치 0으로 바꾸는 등의 작업을 수행합니다.

크기 n의 배열에 대한 의사 코드

1. Repeat i) to ii) for (n-1) rounds
    i) Go through every unsorted element
    ii) Pick the smallest one and swap with element at the first position (but next to those already been sorted)
2. Done 

선택 정렬을 위한 자바 코드

public void selectionSort() {
    int out, in, min, temp;
    int[] a = new int[nElems];        // nElems is the number of elements we'll input later ^^||
    for(out=0; out<nElems-1; out++) {
        min = out;
        for(in = out+1; in<nElems; in++) {
            if(a[in] < a[min]) {      // if min is greater,
                min = in;             // we have a new min
                temp = a[out];        // swap 'em
                a[out] = a[min];
                a[min] = temp;
            }
        }
    }
}

선택 정렬의 효율성

비교 작업:

the same as bubble sort
≈ N²/2

교환 작업:

usually less than N

따라서 우리는 O(N2)를 얻습니다. 느린 :/

삽입 정렬

데이터를 2개의 목록(정렬된 목록과 정렬되지 않은 목록)으로 나눕니다. 각 반복에서 정렬되지 않은 목록의 첫 번째 요소가 정렬된 목록의 적절한 위치에 삽입됩니다.

의사 코드

1. Repeat i) and ii) for (n-1) rounds
    i) insert the first unsorted element, to the sorted
    ii) compare the newly inserted element to all the sorted, and put it in place
2. Done

자바 코드!

public void insertionSort() {
    int in, out;
    int[] a = new int[nElems];         // nElems is the number of elements we'll input later ^^||
    for(out=1; out<nElems; out++) {    // out is dividing line
        long temp = a[out];            // remove marked item
        in = out;                      // start shifts at out
        while(in>0 && a[in-1]>=temp) { // until one is smaller,
            a[in] = a[in-1];           // shift item to right
            --in;                      // go left one position
        }
        a[in] = temp; // insert marked item
    }
} 

선택 정렬의 효율성

비교 작업:

N*(N-1)/4
≈ N²/4

복사 작업:

usually similar to comparison operations

복잡성 ≈ O(N2); 여전히 느리다..

데이터가 정렬되면 알고리즘이 거의 O(N)에서 실행됩니다.

데이터가 역순이면 버블 정렬처럼 상당히 느리게 실행됩니다

.

3가지 단순 정렬 ​​비교

초기 데이터 배열과 약간의 추가 메모리만 필요하지만 모든 알고리즘은 O(N2) 시간에 실행됩니다.

버블 정렬은 단순하지만 효율성이 가장 낮습니다. 데이터 양이 적은 경우 실용적임

선택 정렬은 스왑 수를 최소화하지만
비교 횟수가 여전히 높습니다

.

삽입 정렬은 세 가지 중에서 가장 다재다능하며 다음과 같습니다.
데이터 양이 적거나 데이터가 거의 정렬되었다고 가정하면 대부분의 상황에서 가장 좋습니다.