컴퓨터 과학에서 정렬 알고리즘은 데이터를 효율적으로 정돈하는 핵심적인 작업이다. 이러한 알고리즘은 데이터의 크기와 유형에 관계없이 사용될 수 있으며, 다양한 응용 분야에서 중요한 역할을 맡는다. 버블 정렬, 선택 정렬, 삽입 정렬에 대해 알아보고, 각각 C언어와 Javascript로 나타내어 보았다.
버블 정렬(Bubble Sort)
버블 정렬은 주어진 배열, 리스트에서 인접한 두 개의 값을 비교하여 그 크기에 따라 위치를 서로 교환하는 정렬 방식이다. 앞의 값이 뒤의 값보다 클 경우, 서로의 위치를 바꾸는 교환이 발생한다. 배열의 끝까지 비교가 완료되면 다시 처음으로 돌아와 이를 반복한다. 따라서 이 알고리즘은 배열을 한 번 통째로 살펴보면서 가장 큰 원소를 배열의 끝으로 이동시키는 과정을 반복하여 정렬을 수행한다.
진행 흐름을 나타내 본다면 위 그림과 같을 것이다.
위의 6, 5, 3, 1, 8, 7, 2, 4 배열을 버블 정렬하는 코드를 C언어를 통해 작성해 보았다.
// C 버블 정렬 코드
#include <stdio.h>
void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)
{
// 한 번의 루프에서 가장 큰 수를 맨 끝으로 보내기 위한 루프
for (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)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}지정된 배열을 버블 정렬 알고리즘을 사용하여 정렬한다. bubbleSort() 함수는 배열을 받아서 버블 정렬을 수행하고, printArray() 함수는 배열의 요소를 출력한다. main() 함수에서는 주어진 배열을 초기화하고 정렬 후 결과를 출력한다.
Javascript로 작성하는 버블 정렬 코드는 정해진 배열을 주지 않고, 정렬할 데이터의 개수를 입력하고 정렬에 걸리는 시간을 측정하여 보았다.
// Javascript 버블 정렬 코드
function bubbleSort(arr) {
var len = arr.length
var swapped
do {
swapped = false
for (var i = 0; i < len - 1; i++) {
if (arr[i] > arr[i + 1]) {
var temp = arr[i]
arr[i] = arr[i + 1]
arr[i + 1] = temp
swapped = true
}
}
} while (swapped)
}
// 함수 실행 시간 측정 함수
function measureTimeTaken(callback) {
var startTime = performance.now()
callback()
var endTime = performance.now()
return (endTime - startTime) / 1000 // 밀리초를 초로 변환
}
// 사용자 입력 및 실행
var readline = require("readline")
var rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
})
rl.question("Input : ", function (n) {
n = parseInt(n)
var min = 1 // 랜덤 수의 최솟값
var max = 1000 // 랜덤 수의 최댓값
// 랜덤 수 생성
var randomArray = []
for (var i = 0; i < n; i++) {
randomArray.push(Math.floor(Math.random() * (max - min + 1)) + min)
}
// 버블 정렬 실행 및 실행 시간 측정
var timeTaken = measureTimeTaken(function () {
bubbleSort(randomArray)
})
// 결과 출력
console.log("Result : ", timeTaken.toFixed(2), "seconds")
rl.close()
})
10000, 20000, 40000, 80000으로 입력 개수를 2배씩 증가시켜 보았다. 버블 정렬의 시간 복잡도는 O(N²)으로, 데이터의 양이 증가함에 따라 실행 시간이 제곱으로 증가한다. 하지만 정확한 제곱을 뜻하는 것은 아니고, 데이터의 크기가 2배로 증가하면 걸리는 시간은 일반적으로 4배가 아닌 4배보다 더 많이 증가한다고 보면 된다. 위의 실행 결과처럼.
선택 정렬(Selection Sort)
선택 정렬은 n 개의 값 중에서 최소값을 찾아 첫 번째 위치에 놓고, 나머지 n-1 개 중에서 다시 최소값을 찾아 두 번째 위치에 놓는 방식을 반복하여 정렬하는 방식이다.
선택 정렬의 동작은 다음과 같다.
- 주어진 배열에서 최솟값(또는 최댓값) 찾기
- 최솟값(또는 최댓값)을 배열의 맨 앞 원소와 교환
- 위 과정을 반복하여 배열의 정렬이 완료될 때까지 진행
// C 선택 정렬 코드
#include <stdio.h>
void selectionSort(int arr[], int n)
{
int i, j, min_idx;
// 배열의 모든 요소에 대해 반복
for (i = 0; i < n - 1; i++)
{
// 현재 위치부터 끝까지 가장 작은 요소의 인덱스를 찾음
min_idx = i;
for (j = i + 1; j < n; j++)
{
if (arr[j] < arr[min_idx])
min_idx = j;
}
// 현재 위치와 가장 작은 요소의 위치를 교환
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main()
{
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}// Javascript 선택 정렬 코드
function selectionSort(arr) {
var len = arr.length
for (var i = 0; i < len - 1; i++) {
var minIndex = i
// 현재 위치부터 끝까지 가장 작은 요소의 인덱스를 찾음
for (var j = i + 1; j < len; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j
}
}
// 현재 위치와 가장 작은 요소의 위치를 교환
if (minIndex !== i) {
var temp = arr[i]
arr[i] = arr[minIndex]
arr[minIndex] = temp
}
}
}
function measureTimeTaken(callback) {
var startTime = performance.now()
callback()
var endTime = performance.now()
return (endTime - startTime) / 1000
}
var readline = require("readline")
var rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
})
rl.question("Input : ", function (n) {
n = parseInt(n)
var min = 1
var max = 1000
var randomArray = []
for (var i = 0; i < n; i++) {
randomArray.push(Math.floor(Math.random() * (max - min + 1)) + min)
}
// 선택 정렬 실행 및 실행 시간 측정
var timeTaken = measureTimeTaken(function () {
selectionSort(randomArray)
})
console.log("Result : ", timeTaken.toFixed(2), "seconds")
rl.close()
})
선택 정렬 또한 마찬가지로 버블 정렬과 동일한 O(N²)의 시간복잡도를 갖는다. 하지만 버블 정렬보다 약 두 배 가량 빠른 것을 볼 수 있다.
삽입 정렬(Insertion Sort)
삽입 정렬은 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 값를 순서에 맞게 삽입시켜 정렬하는 방식이다. 선택 정렬과 함께 인간에게 뭔가를 정렬하라고 하면 무의식적으로 사용하는 대표적인 알고리즘이다.
삽입 정렬은 배열이 작을 경우 상당히 효율적으로, 일반적으로 빠르다고 알려진 알고리즘이라 할지라도 배열이 작다면 대부분 삽입 정렬이 성능에서 우위를 점한다. 따라서 고성능 알고리즘들 중에서는 배열의 사이즈가 클때는 O(nlogn) 알고리즘을 쓰다가 정렬해야 할 부분이 작을 때는 삽입 정렬로 전환하는 경우도 있다.
마찬가지로 C와 Javascript로 구현해 보았다.
// C 삽입 정렬 코드
#include <stdio.h>
void insertionSort(int arr[], int n) {
int i, key, j;
// 배열의 각 요소에 대해 반복
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// key보다 큰 요소들을 오른쪽으로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
void printArray(int arr[], int size) {
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = {6, 5, 3, 1, 8, 7, 2, 4};
int n = sizeof(arr) / sizeof(arr[0]);
printf("Original array: \n");
printArray(arr, n);
insertionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}// Javascript 삽입 정렬 코드
function insertionSort(arr) {
var len = arr.length
for (var i = 1; i < len; i++) {
var key = arr[i]
var j = i - 1
// key보다 큰 요소들을 오른쪽으로 이동
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j]
j = j - 1
}
arr[j + 1] = key
}
}
function measureTimeTaken(callback) {
var startTime = performance.now()
callback()
var endTime = performance.now()
return (endTime - startTime) / 1000
}
var readline = require("readline")
var rl = readline.createInterface({
input: process.stdin,
output: process.stdout,
})
rl.question("Input : ", function (n) {
n = parseInt(n)
var min = 1
var max = 1000
var randomArray = []
for (var i = 0; i < n; i++) {
randomArray.push(Math.floor(Math.random() * (max - min + 1)) + min)
}
// 삽입 정렬 실행 및 실행 시간 측정
var timeTaken = measureTimeTaken(function () {
insertionSort(randomArray)
})
console.log("Result : ", timeTaken.toFixed(2), "seconds")
rl.close()
})
삽입 정렬 또한 O(N²)의 시간복잡도를 갖는다. 역시 O(N²)들 중 빠른 편에 속하는 삽입 정렬 답게 포스트에서 다룬 알고리즘들 중 가장 빠른 결과값이 나왔다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있기 때문이다. 하지만 입력 데이터가 역순으로 정렬되어 있다면 결국 최악의 성능이 나온다.
