정렬 알고리즘

버블 정렬

내 풀이

function bubble (arr) {
  let temporaryValue;

  for (let i = 1; i < arr.length; i++) {
    for (let j = 0; j < arr.length - 1; j++) {
      if (arr[j] > arr[j+1]) {
        temporaryValue = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = temporaryValue;
      }
    }
  }
  
  return arr;
}

책 풀이

function bubble (arr) {
  let unsortedIndex = arr.length - 1;
  let sorted = false;
  let temporary;

  while (!sorted) {
    sorted = true;
    for (let i = 0; i < unsortedIndex; i++) {
      if (arr[i] > arr[i+1]) {
        temporary = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temporary;
        sorted = false;
      }
    }
    unsortedIndex -= 1; 
  }

  return arr;
}

• 책에선 어떤 교환도 하지 않은 패스스루였을땐 배열이 완전히 정렬된걸로 보고 문제가 해결된걸로 판단하게 코드를 짜라고 했는데, 내 코드는 그런 논리구조가 없어 정렬이 완료 됐는데도 패스스루를 반복하는 코드가 됨.

선택 정렬

내 풀이

function select (arr) {
  let smallestIndex;
  let temporaryValue;
  for (let i = 0; i < arr.length - 1; i++) {
    smallestIndex = i;
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[smallestIndex] > arr[j]) {
        smallestIndex = j;
      }
    }
    if (smallestIndex !== i) {
      temporaryValue = arr[i];
      arr[i] = arr[smallestIndex];
      arr[smallestIndex] = temporaryValue;
    }
  }
  return arr;
}

책 풀이

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;
}

• 내 풀이와 거의 동일하나 lowestNumberIndex 변수와 temp 변수 선언을 해당 변수가 필요한 코드블럭 스코프에서 선언함. 자바스크립트 엔진이 필요한 변수를 찾으러 함수 스코프까지 검색을 할 필요가 없으므로 속도면에서 조금이라도 더 유리한 코드라 생각.
• 생각해보니 위와같이 하면 for 문을 돌때마다 변수를 계속 선언하게 되는데 for문에서 한번 선언된 변수는 실행컨텍스트에 올라가 있어 매 반복마다 선언이 되는게 아닌건지 찾아봐야겠다.

삽입 정렬

내 풀이

function insertion (arr) {
  for (let i = 1; i < arr.length; i++) {
    let tempValue = arr[i];
    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] < tempValue) {
        arr[j+1] = tempValue;
        break;
      }
      arr[j+1] = arr[j];
      if (j === 0) {
        arr[j] = tempValue;
      }
    }
  }
  return arr;
}

책 풀이