[알고리즘] 버블, 선택, 삽입, 셸, 힙, 병합, 퀵 정렬 총정리

[알고리즘] 버블, 선택, 삽입, 셸, 힙, 병합, 퀵 정렬 총정리

이번시간에는 정렬(Sorting)알고리즘의 가장 대표적인 7가지 정렬 방법에 대해 총정리를 해보는 시간을 갖도록 하자.

반응형

 

---

1. 각 정렬별 특징 및 처리속도

위 표에서 아래로 내려갈수록 빠른 처리속도를 갖는다. (시간복잡도와 실제 처리시간이 다소 다르다.)

 

  1) 제자리정렬이란 위치이동을 위해 추가적인 메모리 할당이 필요없는 정렬을 의미한다.

  2) 안정정렬이란 동일한 값에 대한 기존의 순서가 유지되는 정렬을 의미한다.

  3) 불안정정렬이란 동일한 값에 대한 기존의 순서가 유지되지 않는 정렬을 의미한다.

  4) 공간복잡도가 클수록 위치이동에 필요한 메모리 할당이 크다는 뜻이다.

  5) 시간복잡도가 클수록 한 사이클을 도는데 걸리는 시간이 오래걸린다는 뜻이다.

  6) 퀵정렬은 현존하는 가장 빠른 정렬 알고리즘으로 사실상 퀵정렬만 알고있으면 된다.

      (worst에서는 n²의 복잡도이나, 최악이 나오는 경우는 극히 드물어 무시해도 무방하다.)

 

 

로그계산기 링크도 함께 첨부한다.

<로그계산기 바로가기>

---

2. 버블정렬 (Bubble Sort)

 - 바로 옆과 비교 (양 옆의 값 A <-> B를 하나의 "버블"로 비교한다.)

 

반응형

 

---

3. 선택정렬 (Selection Sort)

 - 모든 배열을 검색하여 최소값을 만나면 자리 Swap (전체를 스캔하여 하나의 최소값을 "선택"한다.)

 

 

---

4. 삽입정렬 (Insertion Sort)

 - 자신과 왼쪽을 비교 (왼쪽보다 작은 위치로 "삽입"한다.)

 

반응형

 

---

5. 병합정렬 (Merge Sort)

 - 2,4,8... X2배끼리 그룹을 "병합"하여 삽입정렬 수행

 

  ex) 6 5 3 1 8 7 2 4 

   1 pass : (6 5) (3 1) (8 7) (2 4) → (5 6) (1 3) (7 8) (2 4)

   2 pass : {5 6 1 3} {7 8 2 4} → {1 3 5 6} {2 4 7 8}

   3 pass : [1 3 5 6 2 4 7 8] → [1 2 3 4 5 6 7 8]

 

---

6. 힙정렬 (Heap Sort)

 - 완전이진트리 root와 말단노드끼리 swap (단, 부모는 자식보다 큰 수여야 한다.)

 

---

7. 셸정렬 (Shell Sort)

 - 행렬("쉘")을 만들어 같은 행끼리 삽입정렬하여 비교한다.

쉘 정렬의 예제

반응형

 

10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16이 저장되어 있다고 가정하고 자료를 오름차순으로 정렬해 보자.

 

 - k값은 n÷2 후 짝수이면 +1하여 홀수화, 소수점이면 소수점은 버린다.

  ex) n(정렬할 값의 수) = 13일 경우,

       1 pass : n = 13 → k = 13/2 = 6.5  ∴ k = 7 (소수점 버림, +1하여 홀수화)

       2 pass : n = 7  → k = 7/2 = 3.5 ∴ k = 3 (소수점 버림)

       3 pass : n = 3 → k = 3/2 = 1.5  ∴ k = 1 (소수점 버림)

 

반응형

 

---

8. 퀵정렬 (Quick Sort)

 - 가운데 값을 기준(피봇)으로 잡고 두 그룹으로 나눠 비교

 

---

9. 정렬별 소스코드

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <ctime>

using namespace std;
#define parent(x) (x-1)/2
int myrandom(int i);
vector<int> randGenerator(int n);
void bubbleSort(vector<int> v);
void selectionSort(vector<int> v);
void insertionSort(vector<int> v);
void merge(vector<int>& v2, int s, int e, int m);
void mergeSort(vector<int>& v2, int s, int e);
void downheap(vector<int>& v3, int cur, int k);
void heapify(vector<int>& v3, int n);
void heap(vector<int>& v3);
void shell_sort(vector<int>& v4, int s, int e);
void qsort(vector<int>& v5, int s, int e);

int main() {
    clock_t start, end;
    int n;// 숫자 갯수
    printf("랜덤 숫자 범위(1~n) : ");
    scanf_s("%d", &n);
    vector<int> v = randGenerator(n);
    //printf("정렬 전 : ");
    //for (int i = 0; i < n; i++)
    //    printf("%d ", v[i]);
    //printf("\n");

    printf("\n");

    start = clock();
    bubbleSort(v);
    end = clock();
    printf("버블 정렬 수행시간 : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);

    start = clock();
    selectionSort(v);
    end = clock();
    printf("선택 정렬 수행시간 : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);

    start = clock();
    insertionSort(v);
    end = clock();
    printf("삽입 정렬 수행시간 : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);



    vector<int> v2 = v;
    vector<int> v3 = v;
    vector<int> v4 = v;
    vector<int> v5 = v;

    start = clock();
    mergeSort(v2, 0, v2.size() - 1);
    end = clock();
    //  printf("--병합 정렬 결과--\n");
    //  for(int i=0;i<v2.size();i++)
    //      printf("%d ",v2[i]);
    //  printf("\n\n"); 
    printf("병합 정렬 수행시간 : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);

    start = clock();
    heap(v3);
    end = clock();
    //printf("--힙 정렬 결과--\n");
    //  for(int i=0;i<v3.size();i++)
    //      printf("%d ",v3[i]);
    //  printf("\n"); 
    printf("힙 정렬 수행시간   : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);


    start = clock();
    shell_sort(v4, 0, v4.size() - 1);
    end = clock();
    //printf("--쉘 정렬 결과--\n");
    //  for(int i=0;i<v4.size();i++)
    //      printf("%d ",v4[i]);
    //  printf("\n"); 
    printf("쉘 정렬 수행시간   : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);


    start = clock();
    qsort(v5, 0, v5.size() - 1);
    end = clock();
    //  printf("--퀵 정렬 결과--\n");
    //  for(int i=0;i<v5.size();i++)
    //      printf("%d ",v5[i]);
    //  printf("\n"); 
    printf("퀵 정렬 수행시간   : %lf\n", (double)(end - start) / CLOCKS_PER_SEC);



}

//난수 생성기 
int myrandom(int i) { return rand() % i; }
vector<int> randGenerator(int n) {
    vector<int> v;
    srand(time(NULL));
    for (int i = 0; i <= n; i++) {
        v.push_back(i);
    }
    random_shuffle(v.begin(), v.end(), myrandom);
    return v;
}

//버블 정렬 
void bubbleSort(vector<int> v) {
    for (int i = 0; i < v.size() - 1; i++) {
        for (int j = 1; j < v.size() - i; j++)
            if (v[j - 1] > v[j])
                swap(v[j - 1], v[j]);
    }
    //  printf("--버블 정렬 결과--\n");
    //  for(int i = 0; i<v.size();i++)
    //      printf("%d ",v[i]);
    //  printf("\n\n");
}

//선택 정렬 
void selectionSort(vector<int> v) {
    for (int i = 0; i < v.size() - 1; i++) {
        for (int j = i + 1; j < v.size(); j++)
            if (v[i] >= v[j])
                swap(v[i], v[j]);
    }
    //printf("--선택 정렬 결과--\n");
    //for(int i = 0; i<v.size();i++)
    //    printf("%d ",v[i]);
    //printf("\n");
}

// 삽입 정렬 
void insertionSort(vector<int> v) {
    for (int i = 1; i < v.size(); i++) {
        int key = v[i], j = i - 1;
        while (j >= 0 && key < v[j]) {
            swap(v[j], v[j + 1]);
            j--;
        }
        v[j + 1] = key;
    }
    //  printf("--삽입 정렬 결과--\n");
    //  for(int i = 0; i<v.size();i++)
    //      printf("%d ",v[i]); 
    //  printf("\n\n");
}

//병합 정렬 
void merge(vector<int>& v2, int s, int e, int m) {
    vector<int> ret;
    int i = s, j = m + 1, copy = 0;

    //결과를 저장할 배열에 하나씩 비교하여 저장한다. 
    while (i <= m && j <= e) {
        if (v2[i] < v2[j])ret.push_back(v2[i++]);
        else if (v2[i] > v2[j])ret.push_back(v2[j++]);
    }

    //남은 값들을 뒤에 채워넣어준다. 
    while (i <= m)  ret.push_back(v2[i++]);
    while (j <= e)  ret.push_back(v2[j++]);

    //원래 배열에 복사해준다. 
    for (int k = s; k <= e; k++) {
        v2[k] = ret[copy++];
    }
}

void mergeSort(vector<int>& v2, int s, int e) {
    if (s < e) {
        int m = (s + e) / 2;
        /*divide, 분할*/
        mergeSort(v2, s, m);//s부터 m까지
        mergeSort(v2, m + 1, e); //m+1부터 e까지 
        /*conquer, 병합*/
        merge(v2, s, e, m);
    }
}

//힙정렬
void downheap(vector<int>& v3, int cur, int k)
{
    int left, right, p;
    while (cur < k) {
        left = cur * 2 + 1;
        right = cur * 2 + 2;

        if (left >= k && right >= k) break;

        p = cur;
        if (left < k && v3[p] < v3[left]) {
            p = left;
        }
        if (right < k && v3[p] < v3[right]) {
            p = right;
        }
        if (p == cur) break;

        swap(v3[cur], v3[p]);
        cur = p;
    }
}

void heapify(vector<int>& v3, int n)
{
    int i, p;
    for (i = parent(n); i >= 0; i--) {
        downheap(v3, i, n);
    }
    //for(i=0;i<size;++i)printf("%d ",v3[i]);
    //printf("\n");
}

void heap(vector<int>& v3)
{
    int k;
    heapify(v3, v3.size());
    for (k = v3.size() - 1; k > 0; ) {
        swap(v3[0], v3[k]);
        //k--;
        downheap(v3, 0, k);
        k--;
    }
}

//셸 정렬
void inc_insertion_sort(vector<int>& v4, int s, int gap) {
    int j, key;
    for (int i = s; i < v4.size(); i = i + gap) {
        //printf("i값 :%d\n", i);
        key = v4[i]; // 현재 삽입될 숫자인 i번째 정수를 key 변수로 복사

        // 현재 정렬된 배열은 i-gap까지이므로 i-gap번째부터 역순으로 조사한다.
        // j 값은 s 이상이어야 하고
        // key 값보다 정렬된 배열에 있는 값이 크면 j번째를 j+gap번째로 이동
        for (j = i - gap; j >= s && v4[j] > key; j = j - gap) {
            v4[j + gap] = v4[j]; // 레코드를 gap만큼 오른쪽으로 이동
        }

        v4[j + gap] = key;
    }
}

void shell_sort(vector<int>& v4, int s, int e) {
    int gap;
    for (gap = e / 2; gap > 0; gap = gap / 2) {
        if ((gap % 2) == 0) {
            gap++; // gap을 홀수로 만든다.
        }
        //printf("number of gap : %d\n", gap);

            // 부분 리스트의 개수는 gap과 같다.
        for (int j = s; j < gap; j++) { //gap - 1 번 삽입정렬 수행
            // 부분 리스트에 대한 삽입 정렬 수행
            //printf("start/gap : %d/%d\n", j, gap);
            inc_insertion_sort(v4, j, gap);
        }

    }
}

//퀵 정렬 
void qsort(vector<int>& v5, int s, int e) {
    int pivot = v5[s];
    int bs = s, be = e;
    while (s < e) {
        while (pivot <= v5[e] && s < e) e--;
        if (s > e) break;
        while (pivot >= v5[s] && s < e) s++;
        if (s > e) break;
        std::swap(v5[s], v5[e]);
    }
    std::swap(v5[bs], v5[s]);
    if (bs < s)
        qsort(v5, bs, s - 1);
    if (be > e)
        qsort(v5, s + 1, be);

}

반응형

 

출력 결과