전에 정리해둔거.. 다시 정리하기

<알고리즘 정렬>

1. 선택정렬(Selection Sort)

void selectionSort(int arr[], int size) {
    int minIndex;	// 최소값의 인덱스
    int i, j, temp;
    for (i = 0; i < size - 1; i++) {
        minIndex = i;
        for (j = i + 1; j < size; j++) 	// arr[i] 이후부터 최소값 찾기
            if (arr[j] < arr[minIndex])
                minIndex = j;
         
        //swap(&arr[i], &arr[minIndex]);	// arr[i]와 최소값 자리 바꾸기
        temp = arr[minIndex]; // 최솟값을 저장
        arr[minIndex] = arr[i];
        arr[i] = temp; // 최솟값을 제일 앞으로 보냄
    }
}

=> i 이후의 최소값을 찾아 swap(제일 앞으로)하는 것을 반복

• 최적 n^2 평균 n^2 최악 n^2
• 장점: 간단하다, 30 이하의 작은 수에서는 효과적이다

2. 버블정렬(Bubble Sort)

void bubbleSort(int arr[], int size) {
    int i, j, temp;
    for (i = size - 1; i>0; i--) 
        for (j = 0; j<i; j++) 	// 0~i까지 범위
            if (arr[j]<arr[j + 1]) 
	{
                //swap(&arr[j], &arr[j + 1]);
	    temp = arr[j];
	    arr[j] = arr[j+1];
	    arr[j+1] = temp;
	}
}

=> 0부터 i까지 계속 비교하여 가장 큰 값을 뒤로 보내기

• 최적 n^2 평균 n^2 최악 n^2
• 반복문 2번 중첩, 성능이 가장 안좋은편

3. 삽입정렬(Insert Sort)

void insertionSort(int arr[], int size) {
    int i, j,key;
 
    for (i = 1; i < size; i++) {
        key = arr[i];
        j = i - 1;
        while (j >= 0&&arr[j]>key) {	// 이미 정렬된 숫자들과 비교
            arr[j + 1] = arr[j];		// 한칸씩 뒤로
            j--;
        }
        arr[j + 1] = key;
    }
}

=> 배열 인덱스 1부터 시작(i 이전의 원소를 비교하므로 0부터 x)하는 key를 하나 정해서
key보다 작은 값을 만났을 때 바로 뒤에 삽입
key보다 작은 원소가 없으면 맨 앞에 위치

• 최적 n 평균 n^2 최악 n^2
  (정렬된 원소들로 구성된 배열이 입력으로 들어올 시 n => 반복문 1회 실행하므로)
• 간단하지만 작은 수에서만 효과적인 경우가 많음

4. 합병정렬, 병합정렬(Merge Sort)

var mergeSort = function(array) {
  if (array.length < 2) return array; // 원소가 하나일 때는 그대로 내보냅니다.
  var pivot = Math.floor(array.length / 2); // 대략 반으로 쪼개는 코드
  var left = array.slice(0, pivot); // 쪼갠 왼쪽
  var right = array.slice(pivot, array.length); // 쪼갠 오른쪽
  return merge(mergeSort(left), mergeSort(right)); // 재귀적으로 쪼개고 합칩니다.
}
function merge(left, right) {
  var result = [];
  while (left.length && right.length) {
    if (left[0] <= right[0]) { // 두 배열의 첫 원소를 비교하여
      result.push(left.shift()); // 더 작은 수를 결과에 넣어줍니다.
    } else {
      result.push(right.shift()); // 오른쪽도 마찬가지
    }
  }
  while (left.length) result.push(left.shift()); // 어느 한 배열이 더 많이 남았다면 나머지를 다 넣어줍니다.
  while (right.length) result.push(right.shift()); // 오른쪽도 마찬가지
  return result;
};

=> 반으로 반복적으로 쪼갠(mergesort) 후 마지막에 합침(merge)

• 최선 O(NlogN) 평균 O(NlogN) 최악 O(NlogN)
• 단점: 정렬하는데 추가적인 메모리 필요(result)
• 보통 재귀함수 사용 (반복적으로 쪼갤 때)
• 분할정복 알고리즘

5. 퀵정렬(Quick Sort)

quick[10000001];
void quickSort(int i, int j)
{
	if(i>=j) return;
	int pivot = quick[(i+j)/2];
	int left = i;
	int right = j;
	
	while(left<=right)
	{
		while(quick[left]<pivot) left++;	// 큰값 찾기(왼쪽)
		while(quick[right]>pivot) right--;	// 작은값 찾기(오른쪽)
		if(left<=right)			// left > right면 비교 멈춤
		{
			swap(quick[left],quick[right]);
			left++; right--;
		}
	}
	quickSort(i,right);
	quickSort(left,j);
}
quickSort(0,n-1);

=> 기준을 제외한 가장 왼쪽과 오른쪽의 수를 조작.
왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있습니다.
오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히 있습니다.
이렇게 넘어가다가 왼쪽은 기준보다 크고, 오른쪽은 기준보다 작으면 서로 바꿔줍니다.
(pivot보다 작으면 왼쪽, 크면 오른쪽)
=> 보통 첫번째 원소를 pivot으로 설정하고 사용
pivot을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 뒤 배열을 반으로 나눔

• Merge보다 평균 두배 빠름 / 평균적으로 매우 빠른 수행속도
• 추가 메모리 공간 필요 X
• 최선 O(NlogN) 평균 O(NlogN) 최악 O(n^2)
• 단점: 운이 나쁘면 느리다. 같은 숫자들을 정렬할 경우 순서 섞이는 문제 발생 위험
• 분할 정복 알고리즘, merge와 달리 비균등하게 분할

• 분할 정복 (divide and conquer)
  문제를 2개로 분리하고 각각 해결 후 결과를 모아 원래의 문제를 해결

병합정렬 퀵정렬 힙정렬 셸정렬