선택 정렬, 버블 정렬, 삽입 정렬, 퀵 정렬

1. 선택 정렬(sort)

알고리즘 효율성 차이를 극명하게 보여주는 것이 없다.

 

1. 비효율적인 알고리즘

let arr = [1, 10, 5, 6, 7, 8, 2, 3, 9, 4];

//어떻게 하면 가장 작은 값을 맨 앞으로 보낼 수 있을까?
//알고리즘은 구체적으로 명시해줘야 한다.
//가장 작은 것을 선택해서 제일 앞으로 보내면 어떨까?
//효율성은 낮으나 구현하기 쉽다

let index = 0;
for (let i = 0; i < 10; i++) {
	let minValue = 9999; // 모든 원소보다 큰 값, 최소값을 택하기 위한 변수
    	for (let j = i; j < 10; j++) {
        	if (minValue > arr[j]) {
            	minValue = arr[j];
				index = j;
                }
			}
            let temp = arr[i]; //가장 작은 값을 맨 앞으로 돌린다. 값을 바꾸는 가장 기본적인 부분
            arr[i] = arr[index];
            arr[index] = temp;
}

- 범위를 살펴보고 계속해서 반복한다

- 10개의 길이지만 총 55을 반복하게 된다.

- O(N^2)의 시간 복잡도를 가진다

- 만약 10,000개라면 일 억 번의 계산을 가진다.

 

메서드는 sort() 메서드가 있다.

let arr2 = [1, 10, 5, 6, 7, 8, 2, 3, 9, 4];
arr2.sort((a, b) => a - b);

https://developer.mozilla.org/ko/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

Array.prototype.sort() - JavaScript | MDN

---

2. 버블 정렬 (Bubble)

 

선택 정렬은 가장 작은 값을 앞으로 보내는 것이고 버블 정렬도 직관적인 해결 방법인데 옆에 있는 값과 비교하여

작은 값을 앞으로 보내는 것, 가장 효율성이 떨어지는 알고리즘이 바로 버블정렬

let arr = [4, 1, 10, 9, 2, 3, 5, 6, 7, 8];
// 4와 1을 비교 작은 값 1이 앞으로 그리고 4와 10을 비교..반복..
//그래서 한 번 돌면 가장 큰 값이 맨 뒤로 이동한다
let temp, index = 0;

for (let i = 0; i < arr.length; i++) {
  for (let j = i + 1; j < arr.length; j++) {
    if (arr[i] > arr[j]) {
      //선택정렬에서 사용했던 것처럼 앞에 값과 그 다음값을 바꿔줄 수 있게
      //temp라는 변수를 이용
      temp = arr[j];
      arr[j] = arr[i];
      arr[i] = temp;
    }
  }
}

- O(N^N)의 시간복잡도이지만 더 느린 이유는 당장 옆에 있는것을 비교하고 바로 바꾸기 때문에 작업량이 많다 

---

3. 삽입정렬 (Insertion sort)

 

삽입정렬이란 시간 복잠도는 O(N^2) 와 같다

 각 숫자를 적절한 위치에 삽입하는 방법

 적절한 위치란 필요할 때만 위치를 바꾼다

let arr = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1];
//1은 10보다 작기 때문에 10 앞에 들어가고, 3은 10과 비교하여 작기 때문에 10 앞에 들어간다 반복
let temp;

for (let i = 0; i < arr.length; i++) {
  let j = i;
  while (arr[j] > arr[j + 1]) {
    temp = arr[j];
    arr[j] = arr[j + 1];
    arr[j + 1] = temp;
    j--;
    console.log(j);
  }
  console.log(arr);
}

- 기본적으로 정렬이 되어 있다고 생각하고 확장해나간다

- 결과적으로 시간 복잡도는 같지만 효율적이다. 힙정렬, 퀵 정렬보다 빠를 정도로 거의 정렬된 상태에서는 빠른 상태이다.

---

4. 퀵 정렬

 

선택, 버블, 삽입 정렬은 시간복잡도는 O(N^2)이다.

퀵 정렬은 대표적으로 분할정복 알고리즘을 사용해서 평균 속도가 O(N* logN)이다. logN은 작은 값이다.

처음은 어려운 알고리즘이다

 

특정한 값을 기준으로 큰 숫자와 작은 숫자를 서료 교환한다.

기준 값 피벗이라고 하는데, 오른쪽 왼쪽으로 나눈다.

 

let arr = [3, 10, 1, 5, 6, 8, 7, 9, 2, 4];

가장 앞에 있는 숫자를 피벗값으로 정한다

왼쪽에서 오른쪽으로 이동하면서 큰 값을 찾는다, 오른쪽에서 왼쪽으로 이동하며 작은 값을 찾는데

왼큰오작

10은 3보다 크고, 4는 작지 않다 그러면 한 칸 이동 2는 3보다 작다 서로 교환

 let arr = [3, 2, 1, 5, 6, 8, 7, 9, 10, 4]; 반복

 그럼 왼쪽부터는 3 보다 크지만 오른쪽에서는 3보다 작은 값인 1을 발견하지만

5보다 작은 인덱스에 있고 엇갈린다. 그럼 이때 작은 값인 1과 3과 바꿔준다

 let arr = [1, 2, 3, 5, 6, 8, 7, 9, 10, 4]; 3까지 정렬은 완료

그랬을 때 3의 왼쪽은 작고, 오른쪽은 큰 값으로 나뉜다.

그럼 1부터 다시..2..3...5로 반복

 100만개의 데이터도 빠르게 정렬을 수행할 수 있다.

 

장점은 속도가 빠르다. 앞서 말했지만 O(nlog2 n)을 가지고 있어서 다른 알고리즘에 비교했을 때, 가장 빠르다

또한 추가 메모리 공간을 필요로 하지 않는다 - O(log n)만큼의 메모리를 필요로 한다.

단점은 최악의 경우 O(N^2)가 될수도 있다. 하지만 가장 빠른 부분에서는 퀵정렬을 사용한다.

 

이미 1부터 10까지 정렬되어 있다면 분할 정복을 사용하지 않고, O(N^2)으로 작동한다

하지만 삽입 정렬 같은 경우는 가장 빠르게 풀어 낼 수 있다. 정렬할 데이터의 특성에 맞는 

알고리즘을 사용해야 한다.

 

const swap = function (array, front, back) {
  const temp = array[front];
  array[front] = array[back];
  array[back] = temp;
};

function hoarePartition(array, start, end) {
  const pivot = array[Math.floor((start + end) / 2)];
  //중간지점을 찾아주는 변수
  console.log(array, array[start], array[end], pivot);

  while (start <= end) {
    while (array[start] < pivot) {
      //피벗값보다 작다면 오른쪽으로 ++해주다가 값이 크다면 그곳에서 멈춘다.
      start++;
    }
    while (array[end] > pivot) {
      //위에서 피벗값보다 큰 값이 있는 상태에서 피벗값보다 크다면 왼쪽으로 --해주다가 값이 작다면 그곳에서 멈춘다.
      end--;
    }

    if (start <= end) {
      //혹시 start가 end를 지나치지 않았는지 한 번 더 검사
      //위에서 피벗값보다 큰값과 작은값을 찾았다 그 두 개의 값을 스왑해준다.
      swap(array, start, end);
      start++;
      end--;
    }
  }
  return start;
  //start가 end를 지나칠 때까지 반복하다가 새로 나눌 오른쪽파티션의 첫 번째 값이 들어간다
}

function qucikSorts(array, start = 0, end = array.length - 1) {
  //재귀함수식으로 구현, start는 처음, end는 마지막
  if (start >= end) {
    return;
  }

  let borderIndex = hoarePartition(array, start, end);
  //재귀가 시작되면 받을 파티션을 구현
  qucikSorts(array, start, borderIndex - 1); //border왼쪽부분
  qucikSorts(array, borderIndex, end); //border오른쪽부분

  return array;
}

const arrr = [10, 9, 1, 2, 4, 6, 5, 7, 8, 3];
const result2 = qucikSorts(arrr);