fundamentals of sorting

Sorting(정렬)의 본질은 아이템들의 모음에 순서를 매기는 것이다. 정렬 알고리즘의 종류는 비교하는 방식에 따라 나뉜다.

순서를 매기는 관계 2가지 요소 :

• a<b, a = b, a>b 이중 하나라도 참인 경우(Trichotomy의 법칙)
• 만약 a < b 이고 b < c이면, a < c이다(Transitivity의 법칙)

Sorting 관련 주요 개념
inversion

• 정렬에서 중요한 개념은 inversion(도치)이다. inversion해야 하는 것이 많을 수록 순서가 더 뒤죽박죽이라는 것이다. 정렬 알고리즘은 inversion을 0로 줄이는 일련의 작업들을 말한다.
  stability
• 같은 층위의 요소들의 순서는 그대로 두는 것을 의미한다.
• 수정 전 : [“hello”, “world”, “we”, “are”, “learning, “sorting”]
• 수정 후 : [“we”, “are”, “hello”, “world”, “sorting”, “learning”]
• 내림차순으로 정렬했음에도 여전히 hello, world 순으로 남아있기에 이는 stable하다고 할 수 있다.

Types of Sorting

There are 2 types of sorting:

• comparison sort
  • Bubble Sort
  • Insertion Sort
  • Selection Sort
  • Merge Sort
  • Quick Sort
• Non-comparison sort
  • Counting Sort
  • Radix Sort

Resources

• Visualizing algorithm
  • https://www.bigocheatsheet.com/
  • https://www.toptal.com/developers/sorting-algorithms