[정렬 알고리즘] 버블, 선택, 삽입 정렬 c++ 구현

단순한 정렬 알고리즘 3가지를 알아보고자 한다. 

아래 알고리즘 3개는 정말 단순하기 때문에 금방 이해하고 구현할 수 있다.

 

 

버블 정럴

버블 정렬은 인접한 두 개의 데이터를 비교해가면서 정렬을 진행하는 방식이다.

 

시간 복잡도

O(n^2)

 

코드 구현

#include <iostream>
using namespace std;

// 버블 정렬 함수
void bubbleSort(int arr[], int n) {
    for (int i = 0; i < n - 1; ++i) {
        for (int j = 0; j < n - i - 1; ++j) {
            // 현재 원소가 다음 원소보다 크면 교환
            if (arr[j] > arr[j + 1]) {
                int temp = arr[j];
                arr[j] = arr[j + 1];
                arr[j + 1] = temp;
            }
        }
    }
}

// 배열 출력 함수
void printArray(int arr[], int size) {
    for (int i = 0; i < size; ++i)
        cout << arr[i] << " ";
    cout << endl;
}

int main() {
    int arr[7] = {64, 34, 25, 12, 22, 11, 90};
    
    bubbleSort(arr, 7);
    printArray(arr, 7);
    
    return 0;
}

 

선택 정렬

정렬순서상 가장 앞서는 것을 선택해서 가장 왼쪽으로 이동시키고 원래 그 자리에 있던 데이터는

빈 자리에 가져다 놓는 정렬 방식

 

시간 복잡도

O(n^2)

 

코드 구현

#include<iostream>
#include<algorithm>

using namespace std;
//선택 정렬 함수
void Selsort(int arr[], int n) {
	int i, j, tmp, minvalue, minidx;

	for (i = 0; i < n; i++) {
		minidx = i;
		minvalue = arr[i];
		for (j = i; j < n; j++) {
			if (minvalue > arr[j]) {
				minvalue = arr[j];
				minidx = j;
			}

		}
		tmp = arr[minidx];
		arr[minidx] = arr[i];
		arr[i] = tmp;
	}
}

// 배열 출력 함수
void printArray(int arr[], int size) {
	for (int i = 0; i < size; ++i)
		cout << arr[i] << " ";
	cout << endl;
}


int main() {
	int arr[5] = { 3, 4, 2, 1, 5 };
	
	Selsort(arr, 5);
	printArray(arr, 5);


}

 

삽입 정렬

삽입 정렬은 정렬 대상을 두 부분으로 나눠서, 정렬 안 된 부분에 있는 데이터를 정렬된 부분의 특정

위치에 삽입해 가면서 정렬을 진행하는 알고리즘이다.

 

시간 복잡도

O(n^2)

 

코드 구현

#include<iostream>
#include<algorithm>

using namespace std;
//선택 정렬 함수
void Selsort(int arr[], int n) {
	int i, j, insert;

	for (i = 1; i < n; i++) {
		insert = arr[i];
		for (j = i-1; j >= 0; j--) {
			if (arr[j] > insert)
				arr[j + 1] = arr[j];
			else {
				break;
			}
		}
		arr[j + 1] = insert; // 이렇게 해야 인덱스가 0까지 가게됨
	}
	
}

// 배열 출력 함수
void printArray(int arr[], int size) {
	for (int i = 0; i < size; ++i)
		cout << arr[i] << " ";
	cout << endl;
}



int main() {
	int arr[5] = { 3, 4, 2, 1, 5 };
	
	Selsort(arr, 5);
	printArray(arr, 5);


}