×
Crocus
공부한 내용을 정리하는 블로그로 시작한
Crocus는 2014년 1월 14일 부터 시작하여
현재 월 6만명, 총 2,101,745명의 방문자 수를 기록하고 있습니다.
Donation
이제 많은 사용자들이 이용하는 만큼
더 다양한 서비스 개발/제공을 위해 후원금을 모금하고자 합니다.
후원을 해주시는 분들은 Donators 명단에 성명, 후원금을 기입해드리며
Crocus 블로그가 아닌 다른 곳에 정리해둔 저만의 내용을 공유해 드리고자 합니다.
Account
예금주 : 고관우
신한은행 : 110-334-866541
카카오뱅크 : 3333-01-7888060

👉 후원 페이지 바로가기 Donators
익명 : 5000원(Crocus응원합니다.)
busyhuman: 5000원(유용한 지식 감사합니다.)
익명 : 5000원(알고리즘 학습러)
반응형


삽입 정렬(Insertion Sort)


가장 기초적인 삽입 정렬에 대해서도 한번 알아보자.


시간 복잡도는 우선 아래 코드에서 보면 알 수 있지만 O(N^2)이다.

Insertion sort.gif


삽입정렬은 위의 두가지 방식처럼 움직인다.

즉, 현재 자신이 선택한 인덱스 k의 값을 key라 생각하고 

k~0까지 반복해 나가며 

k - 1의 값이 key보다 크면 k에 k -1 값을 넣고 k - 1에 key를 넣어주는 방식을 이용한다.


아래 코드를 보면 바로 이해를 할 수 있다.


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
#include <iostream>
#include <cstdio>
 
using namespace std;
 
int arr[] = { 5,123,2,};
int n = 6;
int cnt;
void print() {
    printf("[[ round :: %d ]]\n"++cnt);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    for (int i = 1; i < n; i++) {
        print();
        int key = arr[i];
        for (int j = i - 1; j >= 0; j--)
        {
            print(); // 지워도 되나 좀 더 정확한 순서를 파악 가능하다.
            if (arr[j] > key) {
                arr[j + 1= arr[j];
                arr[j] = key;
            }
            else
                break;
        }
    }
    print();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus



    for (int i = 1; i < n; i++) { // key를 순회
        int key = arr[i]; // 현재 자신이 선택한 인덱스 값을 key로 지정
        for (int j = i - 1; j >= 0; j--) // ~0까지 반복해나가며
        {
            if (arr[j] > key) { // 현재 값이 key보다 크면
                arr[j + 1= arr[j]; // j + 1에 j값을 넣고
                arr[j] = key; // j에 key 값을 넣는다.
            }
            else // 삽입 정렬은 앞이 무조건 정렬이 됨을 보장해주기에 else면 break;
                break;
        }
    }



결국 계속 설명하고자 했던 말이 위의 그림과 같은 말이다.

1을 처음에 key로 잡고 자신보다 큰값이면 swap해주는 방식이다.




선택 정렬(Selection Sort)


선택 정렬은 해당 인덱스를 기준으로 자신보다 작은 값이 있는 인덱스가 있다면 계속해서 메모해둔 뒤

마지막에 현재 시작 위치와 갱신된 인덱스의 값을 서로 swap해주면 된다.


시간 복잡도는 우선 아래 코드에서 보면 알 수 있지만 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
24
25
26
27
28
29
30
31
#include <iostream>
#include <cstdio>
 
#define SWAP(a, b){int t = a; a = b; b = t;}
using namespace std;
 
int arr[] = { 5,123,2,};
int n = 6;
int cnt;
void print() {
    printf("[[ round :: %d ]]\n"++cnt);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    for (int i = 0; i < n; i++) {
        print();
        int idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[idx] > arr[j])
                idx = j;
        }
        SWAP(arr[idx], arr[i]);
    }
    print();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus







버블 정렬(Bubble Sort)

버블 정렬은 현재 인덱스와 그다음 인덱스의 값을 비교하여 현재 인덱스 값이 더 크다면 swap해주는 방식을 이용한다.
이때 버블 정렬은 수가 n개 있으면 n - 1번만 하면 된다.
그 이유는 버블 정렬이 한 라운드 실행될 때 마다 가장 마지막 인덱스에는 가장 큰 수가 정렬되게 되기에 최종적으로는 n - 1번만 정렬해주면 된다.
그리고 2중 포문 내부에서는 n - i - 1까지만 돌리면 되는데 그 이유는 n - i - 1는 뒤에서 i번째까지는 정렬되어있으니 i를 빼고 그리고 인덱스가 0부터 시작이기에 -1을 빼주는 것이다. 


시간 복잡도는 우선 아래 코드에서 보면 알 수 있지만 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
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <algorithm>
 
#define SWAP(a, b){int t = a; a = b; b = t;}
using namespace std;
 
int arr[] = { 5,123,2,};
int n = 6;
int cnt;
void print() {
    printf("[[ round :: %d ]]\n"++cnt);
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
}
int main() {
    for (int i = 0; i < n - 1; i++) {
        print();
        for (int j = 0; j < (n - i) - 1; j++)
            if (arr[j] > arr[j + 1])
                SWAP(arr[j], arr[j + 1]);
    }
    print();
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus





반응형