자료구조 정렬(버블, 선택, 삽입, 합병, 퀵)

정렬(sorting)

배열 내 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘.

1. 거품정렬(bubble sort): 

서로 인접한 두 원소를 비교하면서 정렬하는 알고리즘

평균 시간 복잡도: O(n^2)

1.인접한 값 비교 => 큰값 교환

2. index N번 

3. N 차례 N-i

 

 //swap함수는 arr를 받고 매개변수 두개를 받아 각각의 인덱스를 받는다.
let swap = function (arr, idx_1, idx_2){
   //원소의 값 교환
   let tmp = arr[idx_1];
   arr[idx_1] = arr[idx_2];
   arr[idx_2] = tmp;
};

let bubbleSort_1 = function (arr){
    for (let i = 0; i < arr.length - 1; i++){  // 총 수행 횟수
        for (let j = 0; j < arr.length - 1; j++){ //인접한 인덱스끼리 비교함
            if(arr[j] > arr[j+1]{
                swap(arr, j, j + 1);
            } 
        }
    }
};

let bubbleSort_2 = function (arr){
    for (let i = 0; i < arr.length - 1; i++){
        for (let j = 0; j < arr.length -i - 1; j++){ // -i 이미 정렬된 부분은 다시 정렬처리 되지 않도록 넘어간다.
            if(arr[j] > arr[j+1]{
                swap(arr, j, j + 1);
            } 
        }
    }
};

let bubbleSort_3 = function (arr){
    let swapped;
    for (let i = 0; i < arr.length - 1; i++){
        swapped = false; //swapped가
        for ( let j= 0; j < arr.length -i - 1; j++){
            if (arr[j] > arr[j + 1]) {
                swap(arr, j, j+1);
                swapped = true; //한번이라도 swapped하면 정렬이 필요한 상태이다.
            }
        }
        if(!swapped) break; //swapped가 한번도 실행되지 않았다하면 이미 정렬되어 있다고 판단 할 수 있다. 
                            //swapped 여부를 통해 swapped를 끝낼지 말지 선택할 수 있다. 
    }
};

 

2. 선택정렬

최솟값을 찾아 데이터 영역의 가장 앞으로 이동하는 방식을 반복하여 전체 데이터 영역을 정렬하는 알고리즘

평균 시간 복잡도: O(n2)

알고리즘 동작 방식

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

let ascending = function (x, y) {
  return x > y;
};

let descending = function (x, y) {
  return x < y;
};

let selectionSort = function (arr, compare) {
  for (let i = 0; i < arr.length; i++) {
    //최솟값 인덱스를 변수k로 지정
    let k = i;
    for (let j = i + 1; j < arr.length; j++) {
      //현재 설정되어있는 k값과 어레이의 j값을 비교해서 k값이 크면 k 자리에 j를 위치한다.
      if (compare(arr[k], arr[j])) k = j;
    }
    swap(arr, i, k);
  }
};

3. 삽입 정렬

이미 정렬된 데이터 영역과 비교하면서, 자신의 위치를 찾아 요소를 삽입하며 정렬하는 알고리즘

평균 시간 복잡도: O(n2)

알고리즘 동작 방식

 

let swap = function (arr, idx_1, idx_2) {
  let tmp = arr[idx_1];
  arr[idx_1] = arr[idx_2];
  arr[idx_2] = tmp;
};

let ascending = function (x, y) {
  return x > y;
};

let descending = function (x, y) {
  return x < y;
};

let insertionSort = function (arr, compare) {
  for (let i = 1; i < arr.length; i++) {
    let tmp = arr[i];
    let j;
    //j+1부터 비교
    for (j = i - 1; j >= 0; j--) {
      arr[j + 1] = arr[j];
      if (compare(tmp, arr[j])) {
        break;
      }
    }
    arr[j + 1] = tmp;
  }
};

4. 병합 정렬

하나의 배열을 두 개의 균등한 크기로 분할하고, 부분 정렬하며, 이를 다시 합하면서 전체를 정렬해가는 알고리즘

평균 시간 복잡도: O(n log n)

알고리즘 동작 방식

각각의 요소가 하나가 될 때 까지 분할한다.

6,5 를 비교하고

앞에 있는 값 기준으로 비교하면서 앞에 넣는다.

각각 2,3 비교

정렬되어있는 각각의 요소를 보면서 비교.

//병합 정렬 구현

let mergeSort = function (arr, compare) {
  //재귀 end 조건
  if (arr.length === 1) return arr;

  //중간에 자를 지점. 나누어 떨어지지 않으면 반올림함
  let m = (arr.length / 2).toFixed(0);
  let left = mergeSort(arr.slice(0, m), compare);
  let right = mergeSort(arr.slice(m), compare);

  let i = 0;
  j = 0;
  k = 0;

  //재귀를 반복하면서 비교함
  while (i < left.length && j < right.length) {
    //참으로 나오면 J값을 k 인덱스에 넣어줌, 아니면 i를 넣는다
    arr[k++] = compare(left[i], right[j]) ? right[j++] : left[i++];
  }
  while (i < left.length) arr[k++] = left[i++];
  while (j < right.length) arr[k++] = right[j++];

  return arr;
};

5. 퀵 정렬

특정한 값을 기준으로 큰 숫자와 작은 숫자를 분할하여 정렬하는 알고리즘

평균 시간 복잡도: O(n log n)

알고리즘 동작 방식

 

// 퀵 정렬
// 세가지 변수 사용
// start : 최초로 비교할 위치
// target: 비교대상
// pivot : 기준점

// 가장 오른쪽을 pivot으로 잡고 start랑 target은 같은 위치에서 시작.
// 피벗 기준으로 왼쪽은 작은 값 오른쪽은 큰 값을 만들어준다.

let quickSort = function (arr, compare, s = 0, e = arr.length - 1) {
  //start 는 index, pivot 은 값이다.
  let start = s;
  let pivot = arr[e];

  //i 루프로 타겟을 변경
  for (let i = s; i <= e; i++) {
    if (compare(pivot, arr[i])) {
      swap(arr, start, i);
      start++;
    }
  }

  swap(arr, start, e);

  //재귀 부분에 조건을 걸었음
  if (start - 1 > s) quickSort(arr, compare, s, start - 1);
  if (start + 1 < e) quickSort(arr, compare, start + 1, e);
};