선택정렬
0번째 인덱스에 있는 값과 그 다음 값들을 비교하여 가장 작은 값과 0번째 인덱스의 값과 자리를 바꾼다.
1번 과정을 1번째, 2번째 ... n-1번째 인덱스(길이가 n인 배열)까지 반복한다.
// 선택 정렬 예시
function selectionSort(array) {
for(let i = 0; i < array.length - 1; i++) {
let lowestNumberIndex = i;
for(let j = i + 1; j < array.length; j++) {
if(array[j] < array[lowestNumberIndex]) {
lowestNumberIndex = j;
}
}
if(lowestNumberIndex != i) {
let temp = array[i];
array[i] = array[lowestNumberIndex];
array[lowestNumberIndex] = temp;
}
}
return array;
}
빅 오는 데이터가 늘어날때 알고리즘 단계 수가 장기적으로 어떤 궤적을 그리는지가 중요하기 때문에 상수는 무시한다.
버블 정렬과 선택 정렬 모두 O(N2)이지만 버블 정렬은 선택 정렬보다 두 배 느리다. 같은 시간복잡도(Big O)를 가진 알고리즘이라도 어떤 알고리즘이 더 빠른지 분석해야 한다.
삽입 정렬
1번째 인덱스의 값을 삭제하고 임시 변수에 저장한 후 0번째 인덱스(이전 인덱스)값과 비교하여 임시 변수에 있는 값이 더 작을 경우 0번째 인덱스 값을 비어있는 오른쪽으로 시프트하고 임시 변수의 값을 0번째 인덱스로 옮긴다.
그 다음으로 2번째 인덱스의 값을 삭제하여 임시 변수에 저장하고 1번째 인덱스와 비교하여 임시 변수의 값이 더 작을 경우 1번째 값을 오른쪽으로 시프트, 이후 0번째 값(맨 앞의 인덱스)까지 비교하여 시프트 한다.
위 패스스루 과정을 마지막 인덱스의 값까지 반복한다. 만약 마지막 인덱스의 값이 가장 작다면 마지막 패스스루에서 이전 값들이 한 칸씩 오른쪽으로 시프트하는 과정을 거치며 해당 값이 맨 앞으로 이동하게 된다.
//부트 캠프에서 풀었던 삽입 정렬 문제
//책의 설명과 다르게 기존 배열이 아니라 새로운 sorted 배열에 값을 추가하는 방식으로 구현
const insertionSort = function (arr) {
let sorted = [arr[0]];
for (let i = 1; i < arr.length; i++) {
if (arr[i] >= sorted[i - 1]) {
sorted.push(arr[i]);
} else {
for (let j = 0; j < i; j++) {
if ((arr[i] <= sorted[j]) {
const left = sorted.slice(0, j);
const right = sorted.slice(j);
sorted = left.concat(arr[i], right);
break;
}
}
}
}
return sorted;
};
평균 비교
최악의 시나리오의 경우 선택 정렬이 삽입 정렬보다 빠르지만 여러 시나리오를 비교했을때는 결과가 달라진다. 최선의 시나리오(정렬된 배열), 평균 시나리오(절반이 정렬된 배열), 최악의 시나리오(역순)를 비교하면
최선의 시나리오 평균 시나리오 최악의 시나리오 선택 정렬 N2 / 2 N2 / 2 N2 / 2 삽입 정렬 N N2 / 2 N2
결과가 다르게 나오기 때문에 어느 정도 정렬된 데이터를 다룰 수 있는지 예상할 수 있다면 각각의 시나리오를 고려하여 정렬 알고리즘을 선택해야 한다.
알고리즘 향상
// 두 배열의 교집합을 구하는 함수
function intersection(firstArray, secondArray){
let result = [];
for (let i = 0; i < firstArray.length; i++) {
for (let j = 0; j < secondArray.length; j++) {
if (firstArray[i] == secondArray[j]) {
result.push(firstArray[i]);
}
}
}
return result;
}
//break로 필요없는 비교 단계를 생략하여 개선
function intersection(firstArray, secondArray){
let result = [];
for (let i = 0; i < firstArray.length; i++) {
for (let j = 0; j < secondArray.length; j++) {
if (firstArray[i] == secondArray[j]) {
result.push(firstArray[i]);
break;
}
}
}
return result;
}
두 배열의 교집합을 찾아내는 N2 단계의 함수에서 이미 같은 값을 찾아낸 경우에는 비교가 불필요하므로 break를 추가하여 단계를 줄였다.
짝수의 평균
//배열 내 짝수들의 평균을 구하는 함수
function averageOfEvenNumbers(array) {
let sum = 0;
let countOfEvenNumbers = 0
array.forEach((number) => {
if (number % 2 === 0) {
sum += number;
countOfEvenNumbers ++;
}
})
return sum / countOfEvenNumbers
}
단어 생성기
//문자 배열로부터 두 글자 짜리 모든 문자열 조합을 모으는 함수
function wordBuilder(array) {
let collection = [];
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
if (i !== j) {
collection.push(array[i] + array[j]);
}
}
}
return collection;
}
//세 글자 짜리 모든 문자열 조합을 리턴하는 함수
function wordBuilder(array) {
let collection = [];
for(let i = 0; i < array.length; i++) {
for(let j = 0; j < array.length; j++) {
for(let k = 0; k < array.length; k++) {
if (i !== j && j !== k && i !== k) {
collection.push(array[i] + array[j] + array[k]);
}
}
}
}
return collection;
}
평균 섭씨 온도 구하기
//화씨 온도가 담긴 배열을 섭씨 온도로 변환하여 평균을 구하는 함수
function averageCelsius(fahrenheitReadings) {
const celsiusNumbers = []
fahrenheitReadings.forEach((fahrenheitReading) => {
const celsiusConversion = (fahrenheitReading - 32) / 1.8
celsiusNumbers.push(celsiusConversion)
})
let sum = 0
celsiusNumbers.forEach((celsiusNumber) => {
sum += celsiusNumber
})
return sum / celsiuNumbers.length
}
의류 상표
//의류 품목의 사이즈를 리턴하는 함수
function markInventory(clothingItems){
const clothingOptions = []
for (const item of clothingItems) {
for (let size=1; size<6; size++;) {
clothingOptions.push(item + " Size: " + String(size))
}
}
return clothingOptions
}
1 세기
function countOnes(outerArray) {
let count = 0;
for(const innerArray of outerArray) {
for(const number of innerArray) {
if (number === 1) count ++;
}
}
return count
}
팰린드롬 검사기
function isPalindrome(string) {
let leftIndex = 0;
let rightIndex = string.length - 1;
while (leftIndex < string.length / 2) {
if (string[leftIndex] !== string[rightIndex]) {
return false;
}
leftIndex++;
rightIndex--;
}
return true;
}
모든 곱 구하기
//수 배열을 받아 몯느 두 숫자 조합의 곱을 반환하는 함수
function twoNumberProducts(array) {
let products = [];
for(let i = 0; i < array.length - 1; i++) {
for(let j = i + 1; j < array.length; j++) {
products.push(array[i] * array[j]);
}
}
return products;
}
//두 개의 배열을 받아 한 배열의 모든 수와 다른 한 배열의 모든 수의 곱을 리턴하는 함수
function twoNumberProducts(array1, array2) {
let products = [];
for(let i = 0; i < array1.length; i++) {
for(let j = 0; j < array2.length; j++) {
products.push(array1[i] * array2[j]);
}
}
return products;
}
암호 크래커
def every_password(n)
(("a" * n)..("z" * n)).each do |str|
puts str
end
end
이번에 정리한 내용은 알고리즘 예제를 바탕으로 시간복잡도를 분석하고 같은 시간복잡도라고 하더라도 시나리오에 따라 효율성이 달라질 수 있다는 것을 확인하였다. 이중 중첩 루프를 사용했다고 해서 반드시 N2이 아니고 입력되는 데이터에 따라 단계가 어떻게 변화하는지 파악해야 정확한 분석이 가능하다.