선택정렬과 버블정렬은 제자리 정렬 알고리즘이다.
알고리즘이 단순하며, 메모리가 제한적인 경우 성능 상의 이점이 있다.
선택정렬: 주어진 리스트 중에 최소값을 찾고, 그 값을 맨 앞에 위치한 값과 교체한다. 이후 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다.
(출처: 위키피디아)
선택정렬은 정렬을 위해 비교하는 횟수는 많으나, 교환 횟수는 상당히 적다. 따라서 교환이 많이 이루어져야 하는 역순 정렬같은 자료 상태에서 가장 효율적으로 사용할 수 있는 정렬 방식이다.
버블정렬: 주어진 리스트 중에 인접한 두 원소를 검사하여, 앞의 원소값이 뒤의 원소값보다 클 경우 값을 서로 교체한다. 맨 처음 위치부터 마지막 위치로 값이 정렬될 때까지 작동한다.
버블정렬은 n개의 원소에 대해 n개의 메모리를 사용한다. 따라서 데이터를 하나씩 정밀하게 비교할 수 있는 점은 장점이나, 비교횟수가 많아져 비효율적인 성능을 가지는 점은 단점이다.
코드카타로 선택정렬과 버블정렬 문제를 풀었다.
둘을 같은 알고리즘으로 풀었는데 패스가 된 것에 의문이 생겨, 내 알고리즘과 Model Solution을 비교하고자 이 글을 작성한다.
선택정렬 (Selection Sort)
- 내가 푼 알고리즘
let nums = [ 11, 22, 12, 64, 25 ]
const selectionSort = (nums) => {
for (let i = 0; i < nums.length-1; i++) {
let minIdx = i;
for (let j = i+1; j < nums.length; j++) {
if (nums[j] < nums[minIdx]) {
minIdx = j;
}
}
if (i !== minIdx) {
let temp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = temp;
}
}
return nums
};
selectionSort(nums)
// Output: [ 11, 12, 22, 25, 64 ]- Model Solution
const selectionSort = (nums) => {
for (let i = 0; i < nums.length; i++) {
let minIdx = i;
for (let j = i+1; j < nums.length; j++) {
if (nums[minIdx] > nums[j]) {
minIdx = j;
}
}
let temp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = temp;
}
return nums;
}내가 푼 알고리즘와 모델 솔루션 중 다른 점은 첫번째 for loop 내의 if 문이다.
나는 i 인덱스와 minIdx 인덱스가 다를 경우에만 서로의 값을 변경해주는 것이 더 효율적이라고 생각했기 때문에 두 값을 비교하는 if 문을 넣어주었는데, 모델 솔루션에서는 모든 경우에서 값을 재할당할 수 있도록 했다. (물론, 앞의 값이 뒤의 값보다 작을 경우, 실제로 값의 변경은 이루어지지 않는다.)
버블정렬 (Bubble Sort)
- 내가 푼 알고리즘
const bubbleSort = nums => {
for (let i=0; i<nums.length-1; i++) {
let minIdx = i;
for (let j=i+1; j<nums.length; j++) {
if (nums[j] < nums[minIdx]) {
minIdx = j;
}
}
if (i !== minIdx) {
let temp = nums[i];
nums[i] = nums[minIdx];
nums[minIdx] = temp;
}
}
return nums;
};
let nums = [ 6, 5, 3, 2, 8 ];
bubbleSort(nums);
// Output: [ 2, 3, 5, 6, 8 ]- Model Solution
const bubbleSort = nums => {
for (let i = 0; i < nums.length; i++) {
for (let j = 0; j < nums.length-i-1; j++) {
if (nums[j] > nums[j+1]) {
let temp = nums[j+1];
nums[j+1] = nums[j];
nums[j] = temp;
}
}
}
return nums;
}
console.log(bubbleSort([2,1]))왜 버블정렬 알고리즘에서는 j와 j+1을 비교해서 그 값으로만 재할당을 진행할까 고민해보니, 둘의 Model Solution이 다른 이유가 이해되었다.
=> 선택정렬에서는 i를 최소인덱스값의 기준으로 두고, 그 안에서 j를 계속해서 비교하는 for loop을 돌렸다.
따라서 i와 j는 인접한 관계가 아닌, 맨 처음 위치와 최소값의 관계인 것이다.
반면, 버블정렬에서는 j를 최소인덱스값의 기준으로 두고, 이를 j+1를 계속해서 비교하는 for loop을 돌렸다.
따라서 j와 j+1는 인접한 관계인 것이다.
정렬 알고리즘은 데이터를 다루는 것 뿐만 아니라, 컴퓨터에서 이진 탐색이 가능한 데이터를 만들어 내는 데 중요하게 사용된다.
버블 정렬, 힙 정렬, 선택 정렬, 빠른 정렬, 삽입 정렬, 병합 정렬, 쉘 정렬, 기수 정렬, 카운팅 정렬 등 다양한 장단점을 가진 정렬 알고리즘이 있기에 적재적소에 사용해서 원하는 방식으로 데이터를 운용할 수 있다.
코드카타를 하나하나 풀어가면서 얻는 지식이 늘어가고 있는데, 이 지식들을 잘 조합해서 세상에 도움되는 것을 만들 수 있도록 문서화하여 잘 정리해두어야겠다.
