Sorting

우리말로 “정렬”로 데이터를 정렬하는 것이다.

Sorting은 데이터의 규모가 커질 수록 중요해진다. 작은 데이터일 경우엔 언어에 내장된 메소드를 이용하면되지만 데이터가 10억 규모가 되면 이야기가 달라진다.

(이를 위해 wikipedia에는 수많은 sorting 알고리즘이 있지만 이것은 advanced 알고리즘으로 여기선 기초만 다룬다.)

데이터 규모가 커지면 커질수록 Data Handle에 cost가 기하급수적으로 오르기 때문에 큰 기업들에선 Sorting을 매우 중요하게 생각하며, 같은 이유로 interview에서도 마찬가지로 중요한 주제이다.

직접 scratch로 coding할 일은 없지만 상황에 따라 각 sorting algorithm의 장단점을 따져서 가장 적절한 것을 선택해서 쓸 줄 알아야한다.

아래 페이지에서 각 sorting을 animation으로 볼 수 있다.

https://www.toptal.com/developers/sorting-algorithms

Don’t always trust built in method in your language

built in인 sort method를 항상 믿으면 안된다.

javascript의 경우 문자의 가장 앞자리를 UTF-16의 encoding형태로 서로 비교하여 sorting하기 때문에 원하는 답이 안나올 수도 있다. int가 2자리 이상인 경우도 마찬가지이다.

게다가 문서엔 browser에 따라 처리속도와 필요 메모리가 바뀔 수 있다고 하니 주의해야한다.(javascript의 ECMAscript로 인해 browser에 내장되어 있는 engine에 따라 다르게 작동한다.)

Chrome V8 engine : Quick sort or insertion sort(in small case)

Mozilla firefox engine : Merge sort

javascript의 sort method API document

https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/sort

const months = ['March', 'Jan', 'Feb', 'Dec'];
months.sort();
console.log(months);
// expected output: Array ["Dec", "Feb", "Jan", "March"]

const array1 = [1, 30, 4, 21, 100000];
array1.sort();
console.log(array1);
// expected output: Array [1, 100000, 21, 30, 4]

//이렇게하면 보완이 가능하다.
const array2 = [2, 65, 34, 2, 1, 7, 8]
array2.sort(function(a,b){
	return a - b;
})
// expected output: Array [1, 2, 2, 7, 8, 34, 65]

Bubble sort

양 옆의 갚을 비교 하여 정렬하고 nested loop을 통해 완성한다. [O(n^2)]

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function bubbleSort(array) {
  var length = array.length;
  for(var i = 0; i < length; i++){
    for(var j = 0; j < length-i; j++){
      if(array[j] > array[j+1]){
        var temp = array[j+1]
        array[j+1] = array[j]
        array[j] = temp
      }
    }
  }
  return array;
}

bubbleSort(numbers);
console.log(numbers);

Selection Sort

List를 모두 훑으면서 가장 작은 값을 찾고 그 값을 해당 loop의 순번에 넣는다. 이것을 nested loop로 반복 [O(n^2)]

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function selectionSort(array) {
  for(var i = 0; i<array.length-1;i++){
    for(var j = i+1; j<array.length;j++){
      if(array[i] > array[j]){
        var temp = array[j]
        array[j] = array[i]
        array[i] = temp;
      }
    }
  }
  return array;
}

selectionSort(numbers);

Insertion sort

거의 sorting되어 있고 small data set이면 Insertion sorting이 가장 빠르다.

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function insertionSort(array) {
  const length = array.length;
	for (let i = 0; i < length; i++) {
		if (array[i] < array[0]) {
      //move number to the first position
      array.unshift(array.splice(i,1)[0]);
    } else {
      // only sort number smaller than number on the left of it. This is the part of insertion sort that makes it fast if the array is almost sorted.
      if (array[i] < array[i-1]) {
        //find where number should go
        for (var j = 1; j < i; j++) {
          if (array[i] >= array[j-1] && array[i] < array[j]) {
            //move number to the right spot
            array.splice(j,0,array.splice(i,1)[0]);
          }
        }
      }
    }
	}
}

insertionSort(numbers);
console.log(numbers);

Merge Sort

배열을 반으로 쪼개고 쪼개 1개까지 쪼개서 양옆의 배열의 값과 비교하고 합병하면서 sorting한다.(Divide and Conquer) O(n log(n)), O(n)

위의 sorting보다 빠르다는게 장점이다, 메모리가 더 많이 필요한게 단점

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function mergeSort (array) {
  if (array.length === 1) {
    return array
  }
  // Split Array in into right and left
  const length = array.length;
  const middle = Math.floor(length / 2)
  const left = array.slice(0, middle) 
  const right = array.slice(middle)
  // console.log('left:', left);
  // console.log('right:', right);

  
  return merge(
    mergeSort(left),
    mergeSort(right)
  )
}

function merge(left, right){
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;
  while(leftIndex < left.length && 
        rightIndex < right.length){
     if(left[leftIndex] < right[rightIndex]){
       result.push(left[leftIndex]);
       leftIndex++;
     } else{
       result.push(right[rightIndex]);
       rightIndex++
    }
  }  
  //console.log(left, right)
  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

const answer = mergeSort(numbers);
console.log(answer);

public class MergeSortSoloReview {
	
	int count = 0;
	
	//처음에 쪼개고 쪼개서 하나로 만들고(call stack을 쌓고) 하나를 리턴해서 병합하고 리턴하고 반복...
	public int[] divideAndMerge(int [] a) {
		System.out.println("divide count = " + ++count);
		//a가 하나로 쪼개지면 그대로 리턴한다.(base case)
		if(a.length == 1) {
			System.out.println("return : " + a[0]);
			return a;
		}
		
		int mid = a.length / 2; //오른쪽 파티션의 첫번째 인덱스이다.
		System.out.println("mid = " + mid);
		
		int[] left = new int[mid];
		
		for (int i = 0; i < left.length; i++) {
			left[i] = a[i];
		}
		
		int[] right = new int [a.length - mid];
		
		for (int i = 0; i < right.length; i++) {
			right[i] = a[i+mid];
		}
		
		System.out.println("divided : ");
		scan(left);
		scan(right);
		
		//쪼갰으니 병합해서 리턴해야한다.
		//하나가 남을때까지 반복적으로 쪼개야하므로 이렇게 불러야한다.
		//base case 조건 : array가 하나일 것
		//자신의 작업을 다시 사용할 필요가 없다면 base case조건을 통해 리턴을 유도하는게 중요하다!
		//base case에 다다르면 left와 right는 재귀하지 않고 자신을 리턴할 것이고
		//right도 마찬가지로 자신을 재귀하면 merge를 시작하게 된다. = 마지막 하나일때 merge를 시작함
		//merge를해서 결과를 리턴했으므로 그 전에 불럿던 divdeAndMerge함수하나는 리턴값을 가지고 다시 divide를 부르지 않는다.
		//반대쪽도 마찬가지... 따라서 merge하고 다시 리턴값을 위로 올려서 가장 위에까지 반복....
		return merge(divideAndMerge(left),divideAndMerge(right));
	}
	
	//합치기 위한 함수
	//divde를 재귀하지 않고 리턴하면 merge 함수의 조건이 만족되어서 merge를 하게 된다. = 끝가지 divide반복 후 merge하며 돌아옴
	public int[] merge (int[] left, int []right) {
		System.out.println("merge : ");
		scan(left);
		scan(right);
		int[] result = new int[left.length + right.length];
		int leftindex = 0;
		int rightindex = 0;
		int resultindex = 0;
		while(leftindex <= left.length-1) {
			result[resultindex] = left[leftindex];
			resultindex++;
			leftindex++;
		}
		while(rightindex <= right.length-1) {
			result[resultindex] = right[rightindex];
			resultindex++;
			rightindex++;
		}
		
		//insertion sort
		for (int i = 1; i < result.length; i++) {
			if (result[0] > result[i]) {
				int temp = result[0];
				result[0] = result[i];
				result[i] = temp;
			}
			if(result[i] < result[i-1]) {
				for (int j = i; j >= 0; j--) {
					int temp = result[j];
					result[j] = result[j-1];
					result[j-1] = temp;
					if (result[j-2] < result [j-1] ) {
						break;
					}
				}
			}
		}
		
		System.out.println("merge result : ");
		scan(result);
		return result;
	}
	
	public void scan(int [] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i]+" ");
		}
		System.out.println();
	}
	
	
	public static void main(String[] args) {
		int [] arr = {99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0};
		
		MergeSortSoloReview n = new MergeSortSoloReview();
		int[] result = n.divideAndMerge(arr);
		/*
		 * for (int i = 0; i < result.length; i++) { System.out.println(result[i]+" ");
		 * } System.out.println();
		 */
	}
	
}

Quick Sort

Quick sort는 array에서 pivot이라는 기준을 두어 정렬을 시도한다. O(n log(n)), O(log(n)), merge sort보다 space complexity면에서 우수하다. average속도도 실질적으론 merge보다 빠르다.

pivot의 선정방식은 random이며 여러가지 방법 들이 있다. pivot의 왼쪽은 pivot보다 항상 작아야하고 오른쪽은 항상 크도록 정렬한다.

따라서 pivot을 적절한 위치로 정렬해야하는데 pivot의 정렬방식은 여러가지이다. pivot이 정렬되었으면 array을 둘로 쪼개고 똑같은 작업을 반복한다음 정렬이 끝나면 하나의 array로 합병하여 끝낸다.

하지만 pivot이 가장 크거나 작고 혹은 array 가장 끝에 있으면 O(n^2)이라는 끔찍하게 느린 속도가 나오므로 적절한 pivot 선정이 매우 중요하다.

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function quickSort(array, left, right){
  const len = array.length; 
  let pivot;
  let partitionIndex;

  if(left < right) {
    pivot = right;
    partitionIndex = partition(array, pivot, left, right);
    
    //sort left and right
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }
  return array;
}
   
function partition(array, pivot, left, right){
  let pivotValue = array[pivot];
  let partitionIndex = left;

  for(let i = left; i < right; i++) {
    if(array[i] < pivotValue){
      swap(array, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(array, right, partitionIndex);
  return partitionIndex;
}

function swap(array, firstIndex, secondIndex){
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
}

//Select first and last index as 2nd and 3rd parameters
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);

public class QuickSortSoloReview {
	int count = 0;
	
	public void quicksort(int[] a, int left, int right) {
		//오른쪽 시작위치까지
		int partition = partition(a, left, right);
		
		if(left < partition-1) { // 오른쪽 파티션 시작점 바로 전이 왼쪽파티션의 시작점이면 왼쪽 파티션이 1개남았단 소리로 발동 스킵
			quicksort(a, left, partition-1);	//왼쪽 파티션
		}
		if (right > partition) {	// 파티션 시작점이 가장 끝점이랑 같다면 오른쪽 파티션엔 하나남았던 소리로 발동 스킵
			quicksort(a, partition, right);		//오른쪽 파티션
		}
		
	}
	
	public int partition(int[] a, int left, int right) {
		count++;
		int pivot = (left+right)/2;
		//(피봇과 같아도 오케이기때문에 마지막엔 피봇을 넘겨버린다.)
		System.out.println(count + "번째 " + "pivot = " + a[pivot]);
		doprint(a);
		while(left <= right) {
			//왼쪽에 피봇보다 큰게 있을 떄 까지 index움직임
			while(a[left] < a[pivot]) {
				left++;
			}
			//오른쪽에 피봇보다 작은게 있을 때 까지 index를 움직인다.
			while(a[right] > a[pivot]) {
				right--;
			}
			if (left <= right) {
				System.out.println("left = " + left + " right = " + right);
				System.out.println("swap - left = " + a[left] + " right = "+ a[right]);
				int temp = a[left];
				a[left] = a[right];
				a[right] = temp;
				left++;
				right--;
			}	
		}
		doprint(a);
		System.out.println("return  = " + left);
		
		return left;	//오른쪽 파티션의 시작점을 반환한다.
	}
	
	public void doprint(int[] a) {
		for (int i = 0; i < a.length; i++) {
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		QuickSortSoloReview q = new QuickSortSoloReview();
		
		//int [] arr = {99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0};
		int [] arr = {1,2,3,4,5,6};
		
		q.quicksort(arr, 0 ,arr.length-1);
		
		for (int i = 0; i < arr.length; i++) {
			System.out.print(" " + arr[i]);
		}
		
	}
}

Heap Sort

Merge sort와 비슷한 원리로 sorting한다. space complexity가 merge나 quick보다 좋지만 average속도가 앞의 둘 보다 느리다. O(n log(n)) O(1)

실제로는 quick 사용시 bad case 발견시 heap sort로 전환하여 sorting속도를 높인다고 한다.

원리 animation

https://brilliant.org/wiki/heap-sort/

Quick vs Heap

https://stackoverflow.com/questions/2467751/quicksort-vs-heapsort

non-comparison sort

Sorting에서 O(n log(n))의 속도는 수학적으로 절대 넘을 수 없다. 두개의 값들을 모두 비교(comparison)하기 때문이다.

그렇다면 비교하지 않는다면…? 저 속도를 넘을 수 있을 것이다. radix sort, counting sort가 그것이다.

저 둘은 int가 이진수로 저장되어있는 원리를 이용한 것으로 속도가 radix = O(nk) counting = O(n+k)로 속도가 매우 빨라진다.

하지만 원리의 특성상 특정 자릿수(10조같은 너무 큰 수) 이하의 Integer data type만 사용가능하다.

Radix Sort: https://brilliant.org/wiki/radix-sort/

Radix Sort Animation: https://www.cs.usfca.edu/~galles/visualization/RadixSort.html

Counting Sort: https://brilliant.org/wiki/counting-sort/

Counting Sort Animation: https://www.cs.usfca.edu/~galles/visualization/CountingSort.html