알고리즘_Sort 정리(1)

공부하면서 문제를 풀어 본 버블정렬, 삽입정렬, 합병정렬을 제외한 다른 정렬들에 대해서 정리해보고자 한다.
정렬의 경우, 알고리즘에서 자주 나오는 개념이며 이후에도 활용하기 좋은 개념이다.

Selection Sort(선택정렬)

선택정렬은 이름 그대로, 배열을 순회하면서 가장 작은 수를 찾아 선택하여, 배열의 맨 앞부터 순회해서 기준 수가 더 작은 경우 그 순회하는 숫자와 자리를 바꿔준다.
선택정렬에 대한 추가 설명(참고 블로그)
해당 정렬은 버블정렬만큼이나 직관적으로 이해하기 쉽지만, 비효율적인 정렬방법이다.
하지만 버블정렬이나 선택정렬같은 경우, 요소의 수가 적을 때는 오히려 더 효율적이다.
1. 배열을 순회하며, 작은 수 찾고
2. 두번째 순회에서 해당 인덱스의 값과 그 가장 작은수의 위치를 바꿔줘야 한다.
(가령 첫번째 순회의 경우, 첫번째 인덱스 값과 그 배열의 가장 작은 수의 위치를 바꿔주면 된다.)

따라서 시간복잡도는 n^2이 될 것이다.

const selectionSort = function(array) {
  for (let i = 0; i < array.length - 1; i++) { 
    // 처음부터 훑되, 가장 마지막 인덱스 돌기전에는 자연스레 오름차순으로 정렬
    //되어있을 테니까 길이의 -1 직전 까지 순회한다.
    for (let j = i + 1; j < array.length; j++) { 
      // 최솟값의 위치를 찾음
      //i+1 부터 시작하는 이유는 내가 현재 위치한 수의 이전까지는 이미 정렬되어있거나
      //자기 자신이므로 크기를 비교할 필요가 없다.
      // 가장 작은 수를 찾기 위한 순회 이므로, 이 경우에는 배열 끝까지 다 돌아야 한다.
      if (array[i] > array[j]) {
        //현재 위치한 인덱스의 수보다(지금은 첫번째 인덱스) 순회도는 인덱스의 수가 작으면
       	let temp = array[j]; // 최솟값을 저장
    	array[j] = array[i];
    	array[i] = temp; // 최솟값을 제일 앞으로 보내기
      }
    }
  }
  return array;
};

Shell 정렬(셸정렬)

삽입정렬을 보완한 알고리즘이다.
블로그에 있는 삽입정렬에 대한 설명
삽입 정렬의 최대 문제점은 요소들이 삽입될 때, 이웃한 위치로만 이동하게 되는데,
만약 삽입되어야 할 위치가 현재 위치에서 상당히 멀리 떨어진 곳이라면
많은 이동을 해야만 제자리로 갈 수 있다. 즉 효율성이 떨어진다.

셸정렬에 대한 추가 설명(참고 블로그)

1. 주어진 배열 중에서, 특정 기준으로 배열을 부분리스트로 나눈다.
   (여기서 gap이라고 한다.)
   -> 가령 10개의 요소를 가진 배열이 있다면, 여기서 gap은 10/2(정렬할 값의 수/2) 이다.
   -> 주어진 배열에서 5개 요소씩 나누어 부분 배열을 만든다. 만약에 5개 안된다면 남은 수 끼리로라도
   (요소가 하나인 부분리스트는 그냥 둔다.)
   (gap은 홀수가 좋다. 따라서 짝수가 나오면 +1을 한다.)
   -> 그리고 나눈 부분리스트의 각 인덱스끼리 크기를 비교 후, 작은 수와 큰 수를 한 쪽으로 몰아 준다.
2. 이렇게 점차 gap을 2씩 줄이면서 정렬을 진행한다.

셸정렬은 gap을 잘못 설정할 경우, 시간복잡도가 n^2가 나온다.

function shellSort(arr) {
  let gap = Math.floor(arr.length / 2);
 //여기서 gap은 무조건 홀수여야 한다.
  while (gap > 0) {
    if(gap%2 ===0){
    	gap += 1
  	}
    for (let i = 0; i < arr.length - gap; i++) {
      //gap을 기준으로 나눈 부분 리스트들을 순회하는 거라서 종료는 길이에서 gap까지
      let currentIndex = i;
      let gapShiftedIndex = i + gap;
      while(currentIndex >=0){
        //해당 반복문을 넣어주고 아래에, 인덱스 교체 작업을 해주는 이유는,
        //전체 배열이 gap으로 완전히 나누어 떨어지지 않는 경우에도 작업을 해주기 위해서이다.
        //부분 리스트의 수가 두개가 아니라 여러개인 경우, 
        //첫번째와 두번째 부분리스트를 비교하고, 두번째와 세번째 부분리스트를 비교하기 위함이다.
      	if (arr[gapShiftedIndex] <= arr[currentIndex]) {
        	const temp = arr[currentIndex];
        	arr[currentIndex] = arr[gapShiftedIndex];
       	 	arr[gapShiftedIndex] = temp;
      	}
        gapShiftedIndex = currentIndex
        currentIndex -=gap
      }
    }
    gap = Math.floor(gap / 2);
  }
  return arr;
}

quick Sort(퀵정렬)

매우 빠른 속도의 정렬 방법이다. 합병정렬과 비슷하게 주어진 배열을 분리하고 크기 비교를 하지만,
균등하게 쪼개지 않고 랜덤하게 하나의 요소를 선택해서 그것을 기준으로 비균등하게 쪼갠다.

주어진 배열에서 랜덤하게 한 수를 뽑고(이를 pivot(피벗)이라 부른다.),
이 수를 기준으로 작은 수는 왼쪽에 큰수는 오른쪽에 둔다.
그리고 이러한 정렬을 재귀로 계속 돌리면서 피벗을 뽑고, 그 기준으로 부분리스트를 나누어 정렬하는 것을 반복한다.
퀵정렬에 대한 추가 설명(참고 블로그)

그렇다면 실제 알고리즘을 푸는 과정은 어떻게 될까?
1. 피벗을 선택한다.(랜덤하게지만, 보통 가장 맨 처음 수 혹은 맨 끝수를 피벗으로 두고 시작.)
2. 피벗을 제외한 요소들을 순회하는데, 왼쪽부터 점차 인덱스가 커지며 수를 점검하면서,
동시에 배열 끝에서부터 역으로 수를 점검한다.
3. 왼쪽에서 점차 커지며 점검하는 경우에, 피벗보다 작으면 그대로 두고/ 반대로 오른쪽에서 역으로 점검하는 경우에, 피벗보다 크면 그대로 둔다.
4. 이 때 왼쪽의 수가 피벗보다 크고, 오른쪽 수가 피벗보다 작은 경우가 나오면 그 두수의 자리를 교체해준다.
5. 그렇게 양쪽에서 점검해주다가, 같은 인덱스로 만난 경우에, 그 인덱스의 수와 피벗의 위치를 바꿔준다. 이때 그 인덱스 수가 피벗보다 작은경우에 피벗은 그 수의 오른쪽에, 큰 경우에는 왼쪽에 위치한다.

const partition = function(array, left, right, pivotIndex) { // 정렬하는 부분
  var temp;
  var pivot = array[pivotIndex];
  while (left <= right) { 
    // 왼쪽 인덱스와 오른쪽 인덱스가 같을때까지, 즉 만날때까지 서로 순회를 돈다
    while (array[left] < pivot)
      //왼쪽에 위치한 수가 피벗보다 작은 경우에만 왼쪽 인덱스를 하나씩 증가하며 순회
      left++;
    while (array[right] > pivot)
      //오른쪽에 위치한 수가 피벗보다 큰 경우에만 오른쪽 인덱스를 하나씩 감소하며 순회
      right--;
    if (left <= right) { 
      // 왼쪽이 기준보다 크고, 오른쪽이 기준보다 작으면
      //위의 while문에서 벗어날 것이다. 이때 여전히 왼쪽 인덱스가 오른쪽 인덱스보다 작을때, 
      //왼쪽이 기분보다 크고, 오른쪽이 작다는 의미가 되므로 자리를 바꿔준다.
      temp = array[left];
      array[left] = array[right];
      array[right] = temp; // 서로 바꿔줍니다.
      left++;
      right--;
    }
  }
  temp = array[left];
  array[left] = array[pivotIndex];
  array[pivotIndex] = temp; 
  // 마지막으로 기준과 만난 수를 바꿔줍니다. 기준의 위치는 이제 left입니다.
  return left;
};

const quickSort = function(array, left, right) { // 재귀하는 부분
  if (!left) left = 0;
  //처음시작하는 경우 왼쪽 오른쪽으로 나누지 않았으니, 임의로 왼쪽인덱스는 0, 
  //그리고 오른쪽 인덱스는 가장 끝 인덱스이다.
  if (!right) right = array.length - 1;
  var pivotIndex = right; 
  // 배열 가장 오른쪽의 수를 기준으로 뽑습니다.
  pivotIndex = partition(array, left, right - 1, pivotIndex); 
  // right - 1을 하는 이유는 기준(현재 right)을 제외하고 정렬하기 위함입니다.
  if (left < pivotIndex - 1)
    quickSort(array, left, pivotIndex - 1); // 기준 왼쪽 부분 재귀
  if (pivotIndex + 1 < right)
    quickSort(array, pivotIndex + 1, right); // 기준 오른쪽 부분 재귀
  return array;
};

퀵정렬의 경우, 위의 코드를 보면 알다시피, 반복문이 두번 돌아간다.
따라서 최악의 경우, 시간 복잡도는 n^2이나, 빠르게 돌면 NlogN의 시간복잡도를 가진다.