# 1. Sorting

A sorting algorithm is said to be stable if two items with equal keys appear in the same order in sorted output as they appear in the input array to be sorted.

Sorting Algorithm의 Stability : 정렬되지 않은 상태에서 같은 key 값을 가진 원소의 순서가 정렬 후에도 유지하느냐

일부 정렬 알고리즘은 삽입 정렬, 병합 정렬, 버블 정렬 등과 같이 본질적으로 안정적입니다. (정렬 후에도 원래의 순서가 유지됨)

• Problem:

  • Given a list of n items, arrange them in a certain order.
    • Ex: non-increasing, non-decreasing, or etc.

• Some criteria for choosing a sorting algorithm

  • How many items will you be sorting? 얼마나 많은 원소를 정렬할 것인가?

  • Will there be duplicate items in the data? 데이터에 중복 항목이 있습니까?

  • What do you know about the data? 데이터에 대해 알고 계십니까?

  • Is the data already partially sorted? 데이터는 이미 부분적으로 정렬되어 있는가?

  • Do you know the distribution of the items? 품목의 분포를 알고 있습니까?

  • Are the keys of items very long or hard to compare? 항목 키가 매우 길거나 비교하기 어렵습니까?

  • Is the range of possible keys very small? 가능한 키의 범위가 매우 작습니까?

  • Do you have to worry about disk accesses? 디스크 액세스에 대해 염려해야 합니까?

  • Do you need a stable sorting algorithm? 안정적인 정렬 알고리즘이 필요한가?

  • How much time do you have to write and debug your routine? 루틴을 작성하고 디버깅하는 데 얼마나 많은 시간이 필요합니까?

• ref. Skiena, Steven S. The Algorithm Design Manual: The CD-ROM. 2 June 1997. 7 Dec. 2005,

  • 원래 링크 깨짐

# A Formal Definition of Sorting

• A partial order on a set S is a relation R such that for each a, b, and c in S:

  • a R a is true (R is reflexive).
  • aRb and bRc imply aRc (R is transitive)
  • aRb and bRa imply a = b (R is antisymmetric)

• A Linear Order or Total Older on a set S is a partial order R on S such that for every pair of elements a, b, either aRb or bRa.

• The sorting problem

  • Given a sequence of n elements a_1, a_2, ..., a_n drawn from a set having a linear order $\preceq $
  • find a permutation \Pi = (\pi_1, \pi_2, ..., \pi_n) of (1,2,...,n) that will map the sequence into a nondecreasing sequence a_{\pi_1}, a_{\pi_2},...,a_{\pi_n} such that a_{\pi_1} \preceq a_{\pi_i+1} for $1 \leq i < n $

• Ex: \leq on \mathbb{Z}, $ $\subseteq $ on sets

• Sorting on data with partial order?

• ref. 이산수학 내용