[알고리즘] 선택정렬, 삽입정렬 구현(C/C++)

📕 정렬 알고리즘

---

 

알고리즘 문제를 조금이라도 풀어봤다면, 정렬에 관한 문제가 많이 나오는 것을 알 수 있다.

정확히, 정렬을 활용해서 해결해야 하는 문제가 많이 출제된다.(기본 중의 기본)

 

데이터를 정렬하는 것은 효율적인 알고리즘에서의 중요한 단계로, 문제 해결을 효율적으로 할 수 있도록 도와준다.

 

우리는 정렬 알고리즘을 통해서 실수, 문자열, 파일 등을 손쉽게 정렬할 수 있게 된다.

 

이 문서에서는 정렬의 기본이라고 할 수 있는 선택 정렬과, 삽입 정렬을 다룰 예정이다.

 

 

📕 선택 정렬

---

선택 정렬은 가장 기본적인 알고리즘 중의 하나로,

사람이(보편적으로) 데이터를 보고 정렬하는 과정과 동일하다고 생각하면 편하다.

 

정렬 순서는 왼쪽에서 오른쪽으로 흘러가며, 최소값을 통해서 데이터의 대소 관계를 비교하고

교체(swap) 함수를 통해서 데이터의 위치를 바꾼다.

 

위와 같은 데이터가 배열에 있고, 위 데이터를 오름차순으로 정렬한다고 생각해보자.

(많이 학습된) 사람이라면 보자마자 1~10이겠거니 하지만, 컴퓨터는 한 눈에 정렬하지 못한다.

그렇기 때문에 컴퓨터는 좀 더 다른 방식인 최솟값을 통해서 비교하려 한다.

 

최솟값을 배열의 첫 번째 인덱스 값으로 설정하고 다음 인덱스의 값과 비교해서 최솟값보다 작으면

최소값과 위치를 변경하고, 최솟값보다 크면 그 자리에 둔다.

위와 같은 과정을 배열의 크기만큼 반복하면 정렬된 배열이 탄생한다.

 

아래의 C++ 코드를 보자.

 

#include <iostream>
#include <vector>

using namespace std;

int main() {
    vector<int> arr = {1,8,3,5,6,2,9,4,10,7};
    for(int i = 0; i < arr.size(); i++) {
        int min = arr[i];
        for(int j = i+1; j < arr.size(); j++) {
            if(min > arr[j]) {
                min = arr[j];
                swap(arr[i], arr[j]);
            }
        }
        cout << arr[i] << ' ';
    }
}

 

첫 번째 반복문 안에서 최솟값을 매번 갱신하면서 반복해준다.

그리고 최솟값보다 작은 값이 나왔을때 swap함수를 이용해서 인덱스를 바꿔준다.

(swap 함수는 c++의 컨테이너 내장함수이다.)

 

그러면 배열이 아주 아름답게 정렬된다.

 

 

선택정렬은 이처럼 간편하지만 실제로 문제를 해결할때는 잘 사용하지 않는다.

(실제로는 sort함수를 쓰는 경우가 99.9%이다)

 

그 이유는 성능이 아주 떨어지기 때문이다.

총 N^2/2 만큼의 비교를 진행하고, N번의 교환을 하기 떄문에

그 시간 복잡도는 O(n^2)이다.

 

upperbound가 O(n^2)이더라도 장점은 존재한다. 

바로 in place 정렬 알고리즘, 즉 다른 공간이 필요하지 않는 알고리즘이라는 점이다.

그리고 데이터의 이동이 최소한이다.

 

그럼에도 불구하고, Best Case, average case, worst case 모두 O(n^2)이기 때문에....(생략)

 

📕 삽입 정렬

---

삽입 정렬은 선택 정렬 다음으로 친숙한 정렬 알고리즘이다.

방식은 선택정렬과 유사하지만

비교 순서가 왼쪽에서 오른쪽이 아닌 오른쪽에서 왼쪽이라는 점이 다르다.

 

아래의 코드를 확인해보자.

#include <iostream>
#include <vector>

using namespace std;

int main() {

    vector<int> arr = {1, 8, 3, 5, 6, 2, 9, 4, 10, 7};

    for(int i = 1; i < arr.size(); i++) {
        for(int j = i; j > 0; j--) {
            if(arr[j] < arr[j-1]) {
                swap(arr[j],arr[j-1]);
            }
            else
                break;
        }
    }
    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << ' ';
    }
}

 

먼저 배열 arr을 선언하고 값을 할당해준다.

이후 for문을 통해서 배열을 순회하는데, 값을 오른쪽에서부터 비교한다.

i가 1일 경우 arr[1]과 arr[0]을 비교해서 arr[0]이 더 크다면 둘의 위치를 바꾸는 것이다.

i가 2일 경우에는 arr[2]과 arr[1]을 비교하고, 그 후 arr[1] 과 arr[0]을 비교한다.

 

이런식으로 i가 배열의 크기까지 커지면 반복문을 종료하면서

배열의 완벽하게 정렬된 상태가 된다.

 

삽입 정렬은 선택 정렬보다는 조금 나은 시간 복잡도를 가지고 있다.

Best case에서는 O(n)의 시간복잡도를, average case에서는 O(n^2), worst case에서는 O(n^2)의 시간복잡도를 가진다.

 

최선의 경우는 배열이 이미 정렬된 상태일때이다. 

배열이 이미 정렬된 상태라면 모든 arr[j] 의 값이 arr[j-1] 값보다 크거나 같을테니 위치를 변경하지 않을 것이다.

 

최악의 경우는 배열이 반대로 정렬된 상태일때다.

최선의 경우를 정확히 반대로 생각하면 된다.

 

삽입 정렬이 선택 정렬보다 나은 점이 분명 있지만....(할말하않)

 

다음 포스팅에서는 병합정렬과 퀵정렬을 다룰 예정이다.

(퀵정렬이 궁금하다면 구독 좋아요....)