Sort | 정렬

Github logo Edit on GitHub

정렬 알고리즘

ArrayList를 정의하고 정렬/검색 대상 데이터를 저장한다.

function ArrayList() {
  var array = [];
  this.insert = function(item) {
    array.push(item);
  };
  this.toString = function() {
    return array.join();
  };
}

버블 정렬

버블 정렬은 정렬 알고리즘 중에서 가장 단순하다. 그러나 단순한 만큼 실행 시간이 최악이다.

버블 정렬은 인접한 두 원소를 모두 다 비교하고 그 결과에 따라 두 원소의 위치를 바꾼다.

this.bubbleSort = function() {
  var length = array.length;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - 1; j++) {
      if (array[j] > array[j + 1]) {
        swap(j, j + 1);
      }
    }
  }
};

바깥쪽 루프에서 첫 번쨰 원소부터 마지막 원소까지 순회한다. 그리고 안쪽 루프는 첫 번째 원소부터 끝에서 두 번째 원소까지 순회하면서 현재 원소와 그 다음 원소를 비교한다.

현재 원소가 다음 원소보다 크면 위치를 서로 바꾼다.

var swap = function(index1, index2) {
  var aux = array[index1];
  array[index1] = array[index2];
  array[index2] = aux;
};

버블 정렬 알고리즘에서 굳이 비교할 필요가 없어도 일일이 모든 원소를 비교한다.

개선된 버블 정렬

안쪽 루프에서 바깥쪽 루프의 반복 횟수를 차감하면 불필요한 비교 작업을 줄여준다.

this.modifiedBubbleSort = function() {
  var length = array.length;
  for (var i = 0; i < length; i++) {
    for (var j = 0; j < length - 1 - i; j++) {
      if (array[j] > array[j + 1]) {
        swap(j, j + 1);
      }
    }
  }
};

선택 정렬

선택 정렬은 제자리 정렬 알고리즘의 하나로 최소값을 찾아 맨 앞으로 보내고 그 다음으로 작은 값을 찾아 2번째 위치로 보내닌 식으로 정렬한다.

this.selectionSort = function() {
  var length = array.length,
    indexMin;
  for (var i = 0; i < length - 1; i++) {
    indexMin = i;
    for (var j = i; j < length; j++) {
      if (array[indexMin] > array[j]) {
        indexMin = j;
      }
    }
    if (i !== indexMin) {
      swap(i, indexMin);
    }
  }
};

바깥쪽 루프에서 배열을 순회하면서 i + 1 번째로 작은 값을 찾아야 하는데 안쪽 루프가 시작되기 전 최소값을 가진 원소의 인덱스는 i라고 가정한다.

i에서 length까지 j 인덱스 원소 값을 현재까지의 최소갑솨 비교해 만약 더 작다면 현재 최소값으로 갱신을 한다.

이렇게 찾은 indexMin이 i와 다르다면 위치를 교환한다.

버블 정렬과 마찬가지로 중첩 루프문이 있어서 복잡도는 O(n^2)이다.

삽입 정렬

삽입 정렬은 한번에 한 원소씩 정렬된 배열을 만들어가는 알고리즘이다.

첫 번쨰 원소는 정렬이 끝나다고 가정하고 두 번째 원소와 비교해 첫 번째 원소보다 더 작다면 첫 번쨰 원소 앞으로 옮긴다.

처음 두 원소의 정렬이 끝나면 세 번째 원소와 비교를 계속한다.

this.insertionSort = function() {
  var length = array.length,
    j,
    temp;
  for (var i = 1; i < length; i++) {
    j = i;
    temp = array[i];
    while (j > 0 && array[j - 1] > temp) {
      array[j] = array[j - 1];
      j--;
    }
    array[j] = temp;
  }
};

크기가 작은 배열이라면 삽입 정렬은 선택 정렬, 버블 정렬보다 성능이 우수하다.

병합 정렬

벙합 정렬은 가장 먼저 실전에 응용된 정렬 알고리즘이다.

병합 정렬은 복잡도가 o(nlogN)으로 뛰어난 성능을 자랑한다.

병합 정렬 알고리즘의 핵심을 분할과 정복이다. 정렬할 배열을 원소가 하나뿐인 배열 단위로 나뉠 때까지 분할라고 반대로 이렇게 분할된 배열을 점점 더 큰 배열로 병합하면서 정렬을 완성한다.

분할/정복 이라는 접근 방식 덕분에 재귀 호출은 불가피하다.

this.mergeSort = function() {
  array = mergeSortRec(array);
};
var mergeSortRec = function(array) {
  var length = array.length;
  if (length === 1) {
    return array;
  }
  var mid = Math.floor(length / 2),
    left = array.slice(0, mid),
    right = array.slice(mid, length);
  return merge(mergeSortRec(left), mergeSortRec(right));
};
var merge = function(left, right) {
  var result = [],
    il = 0,
    ir = 0;
  while (il < left.length && ir < right.length) {
    if (left[il] < right[ir]) {
      result.push(left[il++]);
    } else {
      result.push(right[ir++]);
    }
  }
  while (il < left.length) {
    result.push(left[il++]);
  }
  while (ir < right.legth) {
    result.push(right[ir++]);
  }
  return result;
};

merge 함수는 분할된 두 배열을 합쳐 큰 배열로 만든다. 병합을 하면서 정렬도 동시에 수행한다.

이 알고리즘의 전반전은 원소가 하나뿐인 배열 단위로 나뉠 때까지 분할을 계속하는 작업이다.

그리고 후반전에서는 역으로 병합을하면서 정렬을 수행한다.

퀵 정렬

복잡도는 O(n log n)이고 복잡도가 동일한 여타 정렬 알고리즘보다 성능이 낫다.

병합 정렬과 마찬가지로 분할/정복 방식으로 접근한다.

  1. 배열의 중간 지점에 위치한 원소(피봇)를 선택한다.

  2. 배열의 첫 번째 원소를 가리키는 포인터(좌측 포인터)와 마지막 원소를 가리키는 포인터(우측 포인터)를 생성한다. 피봇보다 더 큰 우너소가 나올때까지 좌측 포인터를 움직이고 피봇보다 작은 원소가 나올 때까지 우측 포인터를 움직인다. 두 포인터에 해당하는 원소를 서로 교환한다. 이 과정을 좌측 포인터가 우측 포인터 보다 클때까지 반복한다. 이렇게 함으로써 피봇보다 작은 원소는 좌측에 큰 원소는 우측에 나열된다. 이 작업을 파티션이라고 한다.

  3. 피봇을 중심으로 나눈 두 서브배열에 대해 정렬이 끝날때까지 재귀적으로 반복한다.

this.quickSort = function() {
  return quick(array, 0, array.length - 1);
};
var quick = function(array, left, right) {
  var index;
  if (array.length > 1) {
    index = partition(array, left, right);
    if (left < index - 1) {
      quick(array, left, index - 1);
    }
    if (index < right) {
      quick(array, index, right);
    }
  }
};
var partition = function(array, left, right) {
  var pivot = array[Math.floor((right + left) / 2)],
    i = left,
    j = right;
  while (i <= j) {
    while (array[i] < pivot) {
      i++;
    }
    while (array[j] > pivot) {
      j--;
    }
    if (i <= j) {
      swapQuickSort(array, i, j);
      i++;
      j--;
    }
  }
  return i;
};
var swapQuickSort = function(array, index1, index2) {
  var aux = array[index1];
  array[index1] = array[index2];
  array[index2] = aux;
};

가장 먼저 pivot을 정해야 하는데 가장 간단하게 배열의 첫 번쨰 원소도 가능하다 하지만 거의 정렬된 상태인 배열에서 성능상 가장 나쁘기 때문에

무작위로 집어내거나 맨 끝의 원소를 선택하는 방법도 있는데 가운데 원소를 pivot을 잡는다.

i와 j의 위치가 역전될때까지 파티션을 반복한다.

파티션 과정이 끝나면 좌측 포인터 변수를 반환하고 이 값을 받아 서브배열 생성시 사용한다.

검색 알고리즘

순차 검색

순차 검색또는 선형 검색은 가장 기본적인 검색 알고리즘으로 원하는 원소를 찾을 떄까지 자료 구조 전체를 뒤져보는 가장 비효율적인 알고리즘이다.

this.sequentialSearch = function(item) {
  for (var i = 0; i < array.length; i++) {
    if (item === array[i]) {
      return i;
    }
  }
  return -1;
};

루프를 반복하면서 찾고자 하는 원소와 똑같은지 비교하고 일치하면 인덱스를 반환하고 실패하면 -1을 반환한다.

이진 검색

이 알고리즘은 먼저 자료 구조의 정렬이 끝났다는 전제하에 다음 과정을 밟는다.

  1. 배열 중에서 원소를 하나 선택한다.

  2. 이 원소가 검새갈 원소와 일치하면 검색은 끝난다.

  3. 검색할 원소가 선택한 원소보다 작다면 선택한 원소의 좌측 원소에서 다시 찾는다.

  4. 검색할 원소가 선택한 원소보다 크담면 선택한 원소의 우측 원소에서 찾는다.

this.binarySearch = function() {
  this.quickSort();
  var low = 0,
    high = array.length - 1,
    mid,
    element;
  while (low <= high) {
    mid = Math.floor((low + high) / 2);
    element = array[mid];
    if (element < item) {
      low = mid + 1;
    } else if (element > item) {
      high = mid - 1;
    } else {
      return mid;
    }
  }
  return -1;
};
Previous
LinkedList | 연결리스트
Next
Tree | 트리