[알고리즘] 01. 정렬(선택 정렬, 버블 정렬, 삽입 정렬)

<본 포스팅은 개인 공부 목적으로 작성되었습니다.>

✅정렬 알고리즘

정렬은 어떤 데이터들이 주어졌을 때 정해진 순서대로 데이터들을 나열하는 것으로 프로그램 작성 시 빈번하게 필요하다. 선택 정렬, 버블 정렬, 삽입 정렬은 쉽지만 비효율적인 정렬 알고리즘이다.

 

✔선택 정렬(selection sort)

선택 정렬(selection sort)은 index 0번 데이터부터 시작하여 0번을 제외한 나머지 정렬되지 않은 데이터들 중 가장 작은(내림차순이라면 큰) 데이터를 찾아 바꾸고, 그다음 index를 1 증가시켜 동일한 방법으로 정렬하는 알고리즘이다. 그러므로 선택 정렬은 앞에서부터 정렬이 이루어진다.

 

출처 - https://en.wikipedia.org/wiki/Selection_sort

 

이렇게 index가 0인 맨 첫번째 데이터부터 시작하여 뒤에 남은 나머지 데이터 중에 가장 작은 데이터와 swap을 시키면서 정렬하고 동일한 방식으로 나머지 데이터들도 정렬하는 알고리즘이다.

코드

int n = 5, idx, tmp;
int arr[5] = {15, 11, 1, 3, 8}

for(int i = 0; i < n - 1; i++){
    idx = i;
    for(int j = i + 1; j < n; j++){
        if(arr[idx] > arr[j]){
            idx = j;
       }
    }
    tmp = arr[i];
    arr[i] = arr[idx];
    arr[idx] = tmp;
}

이중 for문을 돌면서 가장 작은 값의 index값을 저장해 두고 for문이 끝나면 값을 바꿔주면 된다.

장단점

 

장점

• 알고리즘이 단순하고 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간이 필요하지 않는다.

단점

• for문을 두 번 돌기 때문에 시간복잡도가 O(N^2)이다.
• 불안정 정렬이다.

✔버블 정렬(Bubble sort)

버블 정렬(Bubble sort)는 인접한 두 데이터를 비교하여 정렬을 하는 알고리즘으로 뒤에서부터 정렬되는 알고리즘이다.

출처 - https://en.wikipedia.org/wiki/Bubble_sort

 

이렇게 앞에서부터 인접한 두 수를 계속 비교하면서 총 n-1번을 반복해주면 정렬이 된다.

코드

int n = 8;
int arr[8] = {6, 5, 3, 1, 8, 7, 2, 4};
bool sw = false;

for(int i = 0; i < n-1; i++){
    for(int j = 0; j < n-1-i; j++){
        if(arr[j] > arr[j+1]){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = arr[j];
            sw = true;
        }
    }
    if(sw) break;
}

버블 정렬도 마찬가지로 이중 for문을 돌면서 인접한 두 데이터를 비교하여 정렬해주었다. n-1-i인 이유는 j+1과 비교를 해 주어야하기 때문에 -1을 해줘야 한다. 또 만약 swap이 한 번도 일어나지 않았다면 이미 완전 정렬이 되어있다는 뜻이다. 그러므로 sw변수를 활용하여 for문을 끝내는 코드를 작성하였다.

장단점

 

장점

• 구현이 간단하고 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간이 필요하지 않는다.
• 이미 정렬된 데이터를 정렬할 때 빠르다.
• 안정정렬이다.

단점

• 시간 복잡도가 O(N^2)이다.
• 다른 정렬에 비해 속도가 느리고 교환 횟수가 많다.
• 역순 배열을 정렬할 때, 가장 느리다.

✔삽입 정렬(Bubble sort)

삽입 정렬(insertion sort)은 이미 정렬된 데이터에 올바른 자리를 찾아 데이터를 삽입하여 정렬하는 알고리즘으로 2번째 index부터 시작한다. 해당 index 바로 앞에 데이터부터 시작하여 만약 해당 index 데이터 값보다 크면 데이터를 뒤로 옮기고 알맞은 위치에 데이터를 삽입한다. 그러면 앞에는 무조건 정렬된 상태로 유지가 된다.

출처 - https://en.wikipedia.org/wiki/Insertion_sort

 

이런 식으로 앞에 정렬된 데이터 중 알맞은 위치에 삽입을 하며 정렬해 나가면 된다.

코드

int n = 8, j;
int arr[8] = {6, 5, 3, 1, 8, 7, 2, 4};

for(int i = 1; i < n; i++){
    tmp = arr[i];
    for(j = i - 1; j >= 0; j--){
        if(tmp < arr[j]) arr[j + 1] = arr[j]; 
        else break; 
    }
    arr[j + 1] = tmp;
}

마찬가지로 이중 for문으로 구현해주었고, tmp보다 값이 크면 뒤로 한 칸씩 밀어주고 작거나 같으면 break를 통해 나온 뒤 그 위치에 tmp를 넣어주었다.

장단점

 

장점

• 알고리즘이 단순하고 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간이 필요하지 않는다.
• 대부분의 원소가 이미 정렬되어있을 경우, 효율적일 수 있다.
• 선택이나 버블 정렬에 비하면 빠를 수 있다.

단점

• 비교적 많은 수의 이동이 필요하다.
• 비교할 수가 많고 크기가 클 경우에 적합하지 않다.
• 시간 복잡도가 O(N^2)이다.

참고자료

https://github.com/WooVictory/Ready-For-Tech-Interview/tree/master/Algorithm