정렬 알고리즘

정렬 : 데이터를 특정 기준에 따라 순서대로 나열하는 것

1.선택 정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]
let result;

for (let i = 0; i < array.length; i++) {
	min_index = i
  for (let j = i+1; j < array.length; j++) {
    if (array[min_index] > array[j]) {
    	min_index = j
    }
  }
  result = array[i];
  array[i] = array[min_index];
  array[min_index] = result; //앞에 있는 원소와 가장 작은 값을 바꿈!
 return array
}

• 시간복잡도
  선택정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야함
  빅오 표기법 O(N^2)

2.삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

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

• 삽입 정렬 시간복잡도
  O(N^2), 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어 사용

3.퀵 정렬

• 기준데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법

• 일반적인 상황에서 가장 많이 사용되는 정렬 알고리즘 중 하나

• 병합 정렬과 더불어 대부분의 프로그래밍 언어의 정렬 라이브러리의 근간이 되는 알고리즘

• 첫번째 데이터를 기준 데이터로 설정

• 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할이라고 함

• 시간복잡도
  평균의 경우 O(NlogN)
  최악의 경우 O(N^2) 시간복잡도를 가짐

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

function quick_sort(array, start, end) {
	if (start >= end) {
    	return
    }
   pivot = start,
   left = start + 1,
   right = end
  while (left <= right) {
  	while (left <= end && array[left] <= array[pivot] {
           	left += 1 // 피벗보다 큰 데이터를 찾을 때까지 반복
           }
    while (right > start && array[right] >= array[pivot]) {
    	right -= 1
      if (left > right) {
      	let number = array[right]
        array[right] = array[pivot]
        array[pivot] = number
      }
      let number = array[left]
      array[right] = array[left]
      array[right] = number
    }
  }
  return quickSort(arr, start, right+10),
    quickSort(arr, right+1, end)
}

4.계수정렬

특정한 조건이 부합할 때만 사용할 수 있는 매우 빠르게 동작하는 정렬 알고리즘
데이터의 크기 범위가 제한되어 정수 형태로 표현할 수 있을 때 사용 가능

array = [7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2]
let count[Math.max(array) + 1] // 이부분 나중에 확인!

for (let i = 0; i < array.length; i++) {
	count[array[i]] += 1 // 각 데이터에 해당하는 인덱스 값 증가
for (i = 0; i < count.length; i++) { // 배열에 기록된 정렬 정보 확인
	for (let j = 0; j < count[i]; j++) {
    	console.log(i, end = ' ')
    }
}
}

• 시간복잡도
  계수 정렬의 시간복잡도와 공간복잡도는 모두 O(N+K)
  계수 정렬은 때에 따라서 심각한 비효율성을 초래(데이터가 0과 9999 단 2개만 존재하는 경우)
  계수 정렬은 동일한 값을 가지는 데이터가 여러개 등장할 때 효과적으로 사용

<문제> 두 배열의 원소 교체

두 개의 배열 A와 B를 가지고 있음 , 두 배열은 N개의 원소로 구성되어있으며, 배열의 원소는 모두 자연수
최대 K번의 바꿔치기 연산을 수행할 수 있는데, 바꿔치기 연산이란 배열 A에 있는 원소 하나와 배열 B에 있는 원소 하나를 골라서 두 원소를 서로 바꾸는 걸 말함
배열 A의 모든 원소의 합이 최대가 되도록 하는 것
N, K 긜고 배열 A와 B의 정보가 주어질 때, 최대 K번의 바꿔치기 연산을 수행하며 만들 수 있는 배열 A의 모든 원소의 합의 최댓값을 출력하는 프로그램 작성

매번 배열 A에서 가장 작은 원소를 골라서 배열 B에 가장 큰 원소와 교체
A에 대하여 오름차순 정렬, B에 대해서는 내림차순 정렬
첫번째 인덱스부터 차례대로 확인 A의 원소가 B의 원소보다 작을 떄에만 교체 수행